传教士野人过河问题两种解法思路.docx

细心整理试验 传教士野人过河问题37030602 王世婷一、试验问题传教士和食人者问题〔The Missionaries and Cannibals Problem〕在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将全部的成员运过河去，但是受到以下条件的限制：〔1〕传教士和食人者都会划船，但船一次最多只能装运两个；〔2〕在任何岸边食人者数目都不得超过传教士，否那么传教士就会遭遇紧急：被食人者攻击甚至被吃掉此外，假定食人者会听从任何一种过河支配，试规划出一个确保全部成员平安过河的准备二、解答步骤(1) 设置状态变量并确定值域M为传教士人数，C 为野人人数，B为船数，要求M>=C且M+C <= 3，L表示左岸，R表示右岸初始状态 目标状态L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(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}P10 if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 ) P01 if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 ) P11 if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) P20 if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 ) P02 if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 ) Q10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) Q01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) Q11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 ) Q02 if ( 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次：左岸到右岸，传教士过去0人，野人过去2人第4种方法：第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次：右岸到左岸，传教士过去1人，野人过去0人第11次：左岸到右岸，传教士过去1人，野人过去1人方法二的试验结果：传教士野人过河问题方法如下第1次：左岸到右岸，传教士过去1人，野人过去1人 l:2r,2y r:1r,1y第2次：右岸到左岸，传教士过去1人，野人过去0人 l:3r,2y r:0r,1y第3次：左岸到右岸，传教士过去0人，野人过去2人 l:3r,0y r:0r,3y第4次：右岸到左岸，传教士过去0人，野人过去1人 l:3r,1y r:0r,2y第5次：左岸到右岸，传教士过去2人，野人过去0人 l:1r,1y r:2r,2y第6次：右岸到左岸，传教士过去1人，野人过去1人 l:2r,2y r:1r,1y第7次：左岸到右岸，传教士过去2人，野人过去0人 l:0r,2y r:3r,1y第8次：右岸到左岸，传教士过去0人，野人过去1人 l:0r,3y r:3r,0y第9次：左岸到右岸，传教士过去0人，野人过去2人 l:0r,1y r:3r,2y第10次：右岸到左岸，传教士过去0人，野人过去1人 l:0r,2y r:3r,1y第11次：左岸到右岸，传教士过去0人，野人过去2人 l:0r,0y r:3r,3y问题完毕由结果可以看出，方法二的结果为方法一的第一种结果，两者具有一样性。

五、总结与教训:最起先时接受的方法为：用向量表示状态，其中表示三个传教士的位置，表示三个野人的位置，表示船的位置表示在河左岸，表示已渡过了河，在河右岸设初始状态和目标状态分别为：但在描述规那么时发觉这样定义会造成规那么麻烦、不清晰，缘由在于此题并不关怀是哪几个传教士和野人在船上，仅关怀其人数，故没有必要将每个人都设置变量，分别将传教士、野人、船作为一类即可 四、源代码1. 源程序1：树的遍历%野人和传教士过河问题%date:2010/12/14%author:wang shi tingfunction [ ]=guohe()clear all;close all;global n node;n=2;solveNum=1; %问题的解法result=zeros(100,1);node=zeros(300,5);node(1,:)=[3,3,1,1,-1];%初始化%1左岸传教士数 2左岸野人数 3船〔1为左岸，0为右岸〕%4是否可扩展(1为可扩展) 5父节点号〔-1表示无父节点，即为初始节点〕j=1;% for j=1:nwhile (1) if j>n break end if node(j,4)==1 %判定结点是否可扩展 if node(j,3)==1 %船在左岸 if ( (node(j,1)==0) || (node(j,1)==3) )&&(node(j,2)>=1) forward(j,0,1); end if (node(j,1)==1 && node(j,2)==1 || node(j,1)==3 && node(j,2)==2) forward(j,1,0); end if (node(j,1)>=1 && node(j,1)==node(j,2)) forward(j,1,1); end if (node(j,1)==0 || node(j,1)==3)&& node(j,2)>=2 forward(j,0,2); end if (node(j,1)==2 && node(j,2)==2 || node(j,1)==3 && node(j,2)==1) forward(j,2,0); end elseif node(j,3)==0%船在右岸 if ( (node(j,1)==0) || (node(j,1)==3) )&&(node(j,2)<=2) afterward(j,0,1); end if (node(j,1)==2 && node(j,2)==2 || node(j,1)==0 && node(j,2)==1) afterward(j,1,0); end if (node(j,1)<=2 && node(j,1)==node(j,2)) afterward(j,1,1); end i。