传教士与野人过河问题实验报告
1
问题定义
河的两岸有三个传教士和三个野人需要过河,目前只有一条能装下两个人的船,在河
的任何一方或者船上,如果野人的人数大于传教士的人数,那么传教士就会被野人攻击?/p>
怎么找出一种安全的渡河方案呢?
2
算法分析
首先,先来看看问题的初始状态和目标状态,定义河的两岸分别为左岸和右岸,设?/p>
状态集合为(左岸传教士人数,右岸野人数,右岸传教士人数,右岸野人数,船的位置)
?/p>
船的位置?/p>
-1
表示船在左岸?/p>
1
表示船在右岸?/p>
初始状态:
?/p>
3,3,0,0,0
?/p>
-1
?/p>
目标状态:
?/p>
0
?/p>
0
?/p>
3
?/p>
3
?/p>
1
?/p>
然后,整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问?/p>
状态的改变是通过划船渡河来引发的,所以合理的渡河操作就成了通常所说的算符,根?/p>
题目要求,可以得出以?/p>
5
个算符(按照渡船方向的不同,也可以理解为
10
个算符)
?/p>
?/p>
1
野人、渡
1
传教士、渡
1
野人
1
传教士、渡
2
野人、渡
2
传教?/p>
根据船的位置,向左移或向右移通过递归依次执行
5
种算符,判断是否找到所求,?