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

1、实验 传教士野人过河问题37030602 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。二、解答步骤(1) 设置状态变量并确定值域M为传教士人数，C 为野人人数，B为船数，要求M>=C且

2、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种操

3、作，操作集为 F=P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20P10if ( ML ,CL , BL=1 ) then ( ML1 , CL , BL 1 ) P01if ( ML ,CL , BL=1 ) then ( ML , CL1 , BL 1 ) P11if ( ML ,CL , BL=1 ) then ( ML1 , CL1 , BL 1 ) P20if ( ML ,CL , BL=1 ) then ( ML2 , CL , BL 1 ) P02if ( ML ,CL , BL=1 ) then ( ML , CL2 , BL 1 ) Q10 if

4、 ( 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 状态空间图箭头旁边所标的数字表示了或

5、操作的下标，即分别表示船载的传教士数和食人者数。三、算法设计方法一: 树的遍历根据规则由根（初始状态）扩展出整颗树，检测每个结点的“可扩展标记”，为“-1”的即目标结点。由目标结点上溯出路径。见源程序1。方法二：启发式搜索构造启发式函数为：选择较大值的结点先扩展。见源程序2。四、实验结果方法一的实验结果：传教士野人过河问题第1种方法：第1次：左岸到右岸，传教士过去1人，野人过去1人第2次：右岸到左岸，传教士过去1人，野人过去0人第3次：左岸到右岸，传教士过去0人，野人过去2人第4次：右岸到左岸，传教士过去0人，野人过去1人第5次：左岸到右岸，传教士过去2人，野人过去0人第6次：右岸到左岸，传教

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

7、人，野人过去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人，野人

8、过去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人

9、第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:2

10、r,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问题结束由结果可以看出，方法二的结果为方法一的第一种结果，两者具有一致性。五、总结与教训:最开始时采用的方法为：用向量表示状态，其中表示三个传教士的位置，表示三个野人的位置

11、，表示船的位置。表示在河左岸，表示已渡过了河，在河右岸。设初始状态和目标状态分别为：但在描述规则时发现这样定义会造成规则麻烦、不清晰，原因在于此题并不关心是哪几个传教士和野人在船上，仅关心其人数，故没有必要将每个人都设置变量，分别将传教士、野人、船作为一类即可。 四、源代码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

12、(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 &&

13、; 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) for

14、ward(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

15、f (node(j,1)=0 | node(j,1)=3)&& node(j,2)<=1 afterward(j,0,2); end if (node(j,1)=1 && node(j,2)=1 | node(j,1)=0 && node(j,2)=2) afterward(j,2,0); end end end j=j+1;endfprintf('传教士野人过河问题n');for t=1:n j=1; k=t; StepNum=1; if node(k,4)=-1 while (k=-1) result(j)=k; k=n

16、ode(k,5); j=j+1; end j=j-1; fprintf('第%d种方法：n',solveNum); while j>1 BoatPriNum=node(result(j),1)-node(result(j-1),1); BoatWildNum=node(result(j),2)-node(result(j-1),2); if node(result(j),3)=1 fprintf('第%d次：左岸到右岸，传教士过去%d人，野人过去%d人n',. StepNum,abs(BoatPriNum),abs(BoatWildNum); StepNu

17、m=StepNum+1; end if node(result(j),3)=0 fprintf('第%d次：右岸到左岸，传教士过去%d人，野人过去%d人n',. StepNum,abs(BoatPriNum),abs(BoatWildNum); StepNum=StepNum+1; end j=j-1; end pause(0.2); fprintf('n'); solveNum=solveNum+1; endendfprintf('问题结束');%从左岸到右岸,船上传教士x个，野人y个 function =forward(z,x,y)globa

18、l n;global node;node(n,1)=node(z,1)-x;node(n,2)=node(z,2)-y;node(n,3)=0;r=search(z);if(r) returnendnode(z,4)=0;node(n,4)=1;node(n,5)=z;s=destination();if s node(n,4)=-1;endn=n+1;%从右岸到左岸,船上传教士x个，野人y个 function =afterward(z,x,y)global n;global node;node(n,1)=node(z,1)+x;node(n,2)=node(z,2)+y;node(n,3)=

19、1;r=search(z);if(r) returnendnode(z,4)=0;node(n,4)=1;node(n,5)=z;s=destination();if s node(n,4)=-1;endn=n+1;%function r=search(x)global n node;i=x;while node(i,5)=-1 if node(i,1)=node(n,1) && node(i,2)=node(n,2) && node(i,3)=node(n,3) r=0; return end i=node(i,5);end%跟初始节点比较if node(i,

20、1)=node(n,1) && node(i,2)=node(n,2) && node(i,3)=node(n,3) r=0; returnendr=1;%均不相同%function s=destination()global n node;if node(n,1)=0 && node(n,2)=0 && node(n,3)=0 s=1; returnends=0;2. 运用启发式函数%野人和传教士过河问题%date:2010/12/15%author:wang shi tingfunction =guohe()clear all

21、;close all;global n node open_list index;n=2;result=zeros(100,1);node=zeros(100,5);node(1,:)=3,3,1,1,-1;%初始化%1左岸传教士数 2左岸野人数 3船（1为左岸，0为右岸）%4是否可扩展(1为可扩展) 5父节点号（-1表示无父节点，即为初始节点）index=1;open_list=1,0.01;%节点号 启发函数值while (1)row,=size(open_list);if row=0 fprintf('all the nodes in open list have been ex

22、panded.'); returnendfor i1=1:row open_list(i1,2)=6.01-node(open_list(i1,1),1)-node(open_list(i1,1),2);%定义启发函数 if node(open_list(i1,1),4)=-1%如果该结点是目标结点，则打印结果 fprintf('传教士野人过河问题n'); j=1; k=open_list(i1,1); StepNum=1; while (k=-1) result(j)=k; k=node(k,5); j=j+1; end j=j-1; fprintf('方法如

23、下n'); while j>1 BoatPriNum=node(result(j),1)-node(result(j-1),1); BoatWildNum=node(result(j),2)-node(result(j-1),2); if node(result(j),3)=1 fprintf('第%d次：左岸到右岸，传教士过去%d人，野人过去%d人n',. StepNum,abs(BoatPriNum),abs(BoatWildNum); StepNum=StepNum+1; end if node(result(j),3)=0 fprintf('第%d

24、次：右岸到左岸，传教士过去%d人，野人过去%d人n',. StepNum,abs(BoatPriNum),abs(BoatWildNum); StepNum=StepNum+1; end j=j-1; end pause(0.2); fprintf('问题结束n'); return endendr_row,=find(open_list(:,2)=max(open_list(:,2);j=open_list(r_row(1,1),1); if node(j,3)=1 %船在左岸 if ( (node(j,1)=0) | (node(j,1)=3) )&&

25、(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 &

26、amp;& 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,

27、1)<=2 && node(j,1)=node(j,2) afterward(j,1,1); end if (node(j,1)=0 | node(j,1)=3)&& node(j,2)<=1 afterward(j,0,2); end if (node(j,1)=1 && node(j,2)=1 | node(j,1)=0 && node(j,2)=2) afterward(j,2,0); end end%display(open_list);open_list(r_row(1),:)= ;index=index-1;%open表个数减1%display(open_list); end%从左岸到右岸,船上传教士x个，野人y个 function =forward(z,x,y)global n;glob