实验传教士野人过河问题37030602王世婷一、实验问题传教士和食人者问题（TheMissionariesandCannibalsProblem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。二、解答步骤(1)设置状态变量并确定值域M为传教士人数，C为野人人数，B为船数，要求M>=C且M+C<=3，L表示左岸，R表示右岸。初始状态目标状态LRLRM30M03C30C03B10B01(2)确定状态组，分别列出初始状态集和目标状态集用三元组来表示：（ML,CL,BL）（均为左岸状态）其中,BL∈{0,1}：(3,3,1)：(0,0,0)初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。(3)定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P10if(ML,CL,BL=1)then(ML–1,CL,BL–1)P01if(ML,CL,BL=1)then(ML,CL–1,BL–1)P11if(ML,CL,BL=1)then(ML–1,CL–1,BL–1)P20if(ML,CL,BL=1)then(ML–2,CL,BL–1)P02if(ML,CL,BL=1)then(ML,CL–2,BL–1)Q10if(ML,CL,BL=0)then(ML+1,CL,BL+1)Q01if(ML,CL,BL=0)then(ML,CL+1,BL+1)Q11if(ML,CL,BL=0)then(ML+1,CL+1,BL+1)Q20if(ML,CL,BL=0)then(ML+2,CL+2,BL+1)Q02if(ML,CL,BL=0)then(ML,CL+2,BL+1)(4)当状态数量不是很大时，画出合理的状态空间图图1状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。三、算法设计方法一:树的遍历根据规则由根（初始状态）扩展出整颗树，检测每个结点的“可扩展标记”，为“-1”的即目标结点。由目标结点上溯出路径。见源程序1。方法二：启发式搜索构造启发式函数为：选择较大值的结点先扩展。见源程序2。四、实验结果方法一的实验结果：传教士野人过河问题第1种方法：第1次：左岸到右岸，传教士过去1人，野人过去1人第2次：右岸到左岸，传教士过去1人，野人过去0人第3次：左岸到右岸，传教士过去0人，野人过去2人第4次：右岸到左岸，传教士过去0人，野人过去1人第5次：左岸到右岸，传教士过去2人，野人过去0人第6次：右岸到左岸，传教士过去1人，野人过去1人第7次：左岸到右岸，传教士过去2人，野人过去0人第8次：右岸到左岸，传教士过去0人，野人过去1人第9次：左岸到右岸，传教士过去0人，野人过去2人第10次：右岸到左岸，传教士过去0人，野人过去1人第11次：左岸到右岸，传教士过去0人，野人过去2人第2种方法：第1次：左岸到右岸，传教士过去1人，野人过去1人第2次：右岸到左岸，传教士过去1人，野人过去0人第3次：左岸到右岸，传教士过去0人，野人过去2人第4次：右岸到左岸，传教士过去0人，野人过去1人第5次：左岸到右岸，传教士过去2人，野人过去0人第6次：右岸到左岸，传教士过去1人，野人过去1人第7次：左岸到右岸，传教士过去2人，野人过去0人第8次：右岸到左岸，传教士过去0人，野人过去1人第9次：左岸到右岸，传教士过去0人，野人过去2人第10次：右岸到左岸，传教士过去1人，野人过去0人第11次：左岸到右岸，传教士过去1人，野人过去1人第3种方法：第1次：左岸到右岸，传教士过去0人，野人过去2人第2次：右岸到左岸，传教士过去0人，野人过去1人第3次：左岸到右岸，传教士过去0人，野人过去2人第4次：右岸到左岸，传教士过去0人，野人过去1人第5次：左岸到右岸，传教士过去2人，野人过去0人第6次：右岸到左岸，传教士过去1人，野人过去1人第7次：左岸到右岸，传教士过去2人，野人过去0人第8次：右岸到左岸，传教士过去0人，野人过去1人第9次：左岸到右岸，传教士过去0人，野人过去2人第10次：右岸到左岸，传教士过去0人，野人过去1人第11次：左岸到...
