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

实验 传教士野人过河问题 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。二、解答步骤(1) 设置状态变量并确定值域M为传教士人数，C 为野人人数，B为船数，要求M=C且M+C 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 if (node(j,1)=0 | node(j,1)=3)& node(j,2)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次：右岸到左岸，传教士过去%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)global 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)=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,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;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 expanded.); 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(方法如下n); while j1 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次：右岸到左岸，传教士过去%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) )&(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 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;global node open_list index;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;endindex=index+1;open_list(index,1)=n;n=n+1;%从右岸到左岸,船上传教士x个，野人y个 function =afterward(z,x,y)global n;global node open_list index;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();if s node(n,4)=-1;endindex=index+1;open_list(index,1)=n;n=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