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

实验传教士野人过河问题37030602王世婷一、实验问题传教士和食人者问题（TheMissionariesandCannibalsProblem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。二、解答步骤(1)设置状态变量并确定值域M为传教士人数，C为野人人数，B为船数，要求M=C且M+C=3，L表示左岸，R表示右岸。初始状态目标状态LRLRM30M03C30C03B10B01(2)确定状态组，分别列出初始状态集和目标状态集用三元组来表示fS：（ML,CL,BL）（均为左岸状态）其中03,03MLCL,BL∈{0,1}0S：(3,3,1)gS：(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。方法二：启发式搜索构造启发式函数为：6.01-MLCLf满足规则时其它选择较大值的结点先扩展。见源程序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人第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人问题结束由结果可以看出，方法二的结果为方法一的第一种结果，两者具有一致性。五、总结与教训:最开始时采用的方法为：用向量0123456{,,,,,,}AXXXXXXX表示状态，其中02~XX表示三个传教士的位置，35~XX表示三个野人的位置，6X表示船的位置。0表示在河左岸，1表示已渡过了河，在河右岸。设初始状态和目标状态分别为：0:{0,0,0,0,0,0,0}SS:{1,1,1,1,1,1,1}gGS但在描述规则时发现这样定义会造成规则麻烦、不清晰，原因在于此题并不关心是哪几个传教士和野人在船上，仅关心其人数，故没有必要将每个人都设置变量，分别将传教士、野人、船作为一类即可。四、源代码1.源程序1：树的遍历%野人和传教士过河问题%date:2010/12/14%author:wangshitingfunction[]=guohe()clearall;closeall;globalnnode;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;%forj=1:nwhile(1)ifjnbreakendifnode(j,4)==1%判断结点是否可扩展ifnode(j,3)==1%船在左岸if((node(j,1)==0)||(node(j,1)==3))&&(node(j,2)=1)forward(j,0,1);endif(node(j,1)==1&&node(j,2)==1||node(j,1)==3&&node(j,2)==2)forward(j,1,0);endif(node(j,1)=1&&node(j,1)==node(j,2))forward(j,1,1);endif(node(j,1)==0||node(j,1)==3)&&node(j,2)=2forward(j,0,2);endif(node(j,1)==2&&node(j,2)==2||node(j,1)==3&&node(j,2)==1)forward(j,2,0);endelseifnode(j,3)==0%船在右岸if((node(j,1)==0)||(node(j,1)==3))&&(node(j,2)=2)afterward(j,0,1);endif(node(j,1)==2&&node(j,2)==2||node(j,1)==0&&node(j,2)==1)afterward(j,1,0);endif(node(j,1)=2&&node(j,1)==node(j,2))afterward(j,1,1);endif(node(j,1)==0||node(j,1)==3)&&node(j,2)=1afterward(j,0,2);endif(node(j,1)==1&&node(j,2)==1||node(j,1)==0&&node(j,2)==2)afterward(j,2,0);endendendj=j+1;endfprintf('传教士野人过河问题\n');fort=1:nj=1;k=t;StepNum=1;ifnode(k,4)==-1while(k~=-1)result(j)=k;k=node(k,5);j=j+1;endj=j-1;fprintf('第%d种方法：\n',solveNum);whilej1BoatPriNum=node(result(j),1)-node(result(j-1),1);BoatWildNum=node(result(j),2)-node(result(j-1),2);ifnode(result(j),3)==1fprintf('第%d次：左岸到右岸，传教士过去%d人，野人过去%d人\n',...StepNum,abs(BoatPriNum),abs(BoatWildNum));StepNum=StepNum+1;endifnode(result(j),3)==0fprintf('第%d次：右岸到左岸，传教士过去%d人，野人过去%d人\n',...StepNum,abs(BoatPriNum),abs(BoatWildNum));StepNum=StepNum+1;endj=j-1;endpause(0.2);fprintf('\n');solveNum=solveNum+1;endendfprintf('问题结束');%%%从左岸到右岸,船上传教士x个，野人y个function[]=forward(z,x,y)globaln;globalnode;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();ifsnode(n,4)=-1;endn=n+1;%%%%从右岸到左岸,船上传教士x个，野人y个function[]=afterward(z,x,y)globaln;globalnode;node(n,1)=node(z,1)+x;node(n,2)=node(z,2)+y;node(n,3)=1;r=search(z);if(~r)returnendnode(z,4)=0;node(n,4)=1;node(n,5)=z;s=destination();ifsn