傳教士野人過河問題-兩種解法思路

1、實(shí)驗(yàn)傳教士野人過河問題37030602 王世婷一、實(shí)驗(yàn)問題傳教士和食人者問題(The Missionaries and Cannibals Problem )。在河的左岸有 3 個(gè)傳教士、1條船和3個(gè)食人者，傳教士們想用這條船將所有的成員運(yùn)過河去，但是受 到以下條件的限制：(1)傳教士和食人者都會(huì)劃船，但船一次最多只能裝運(yùn)兩個(gè)；(2)在任何岸邊食人者數(shù)目都不得超過傳教士，否則傳教士就會(huì)遭遇危險(xiǎn)：被食人者攻擊甚至被吃掉。止匕外，假定食人者會(huì)服從任何一種過河安排，試規(guī)劃出一個(gè)確保全部成員安 全過河的計(jì)劃。二、解答步驟(1)設(shè)置狀態(tài)變量并確定值域B為船數(shù)，要求 M>=ca M+C <=

2、3, L表示左岸,目標(biāo)狀態(tài)M為傳教士人數(shù)，C為野人人數(shù), R表水右岸。初始狀態(tài)R000(2)確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集用三元組來表示 Sf： (ML, CL , BL )(均為左岸狀態(tài))其中 0 WML W3,0 WCL W3,BL C 0 , 1S0: (3,3 , 1)Sg : (0,0,0)初始狀態(tài)表示全部成員在河的的左岸；目標(biāo)狀態(tài)表示全部成員從河的左岸全部渡河完畢。(3)定義并確定規(guī)則集合仍然以河的左岸為基點(diǎn)來考慮，把船從左岸劃向右岸定義為Pij操作。其中，第下標(biāo)i表示船載的傳教士數(shù)，第二下標(biāo) j表示船載的食人者數(shù)；同理，從右岸將船劃回 左岸稱之為Qij操作，下標(biāo)的定義

3、同前。則共有 10種操作，操作集為F=P01,P10, P11,P02,P20, Q01,Q10,Q11,Q02,Q20P0if ( ML ,CL , BL=1)then (ML- 1, CL,BL-1 )Riif ( ML ,CL , BL=1 ) then ( ML , CL- 1 , BL - 1 )Riif ( ML ,CL , BL=1)then (ML- 1, CL- 1, BL- 1 )F2oif ( ML ,CL , BL=1)then (ML- 2, CL,BL-1 )P)2if ( ML ,CL , BL=1 )then (ML , CL-2 , BL - 1)Q。if (

4、 ML ,CL , BL=0 )then (ML+1 , CL , BL+1 )Q1if ( ML ,CL , BL=0 )then (ML , CL+1 , BL +1 )Q1if ( ML ,CL , BL=0 )then (ML+1 , CL +1, BL +1)Q0 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）當(dāng)狀態(tài)數(shù)量不是很大時(shí)，畫出合理的狀態(tài)空間圖（3.仇 0）11, 1)J f=2 Qii2, 1)I f=£t

5、o(o，Z Q)1 f=3 Qdl圖1狀態(tài)空間圖箭頭旁邊所標(biāo)的數(shù)字表示了 P或Q操作的下標(biāo)，即分別表示船載的傳教士數(shù)和食人者數(shù)。三、算法設(shè)計(jì)方法一：樹的遍歷根據(jù)規(guī)則由根（初始狀態(tài)）擴(kuò)展出整顆樹，檢測(cè)每個(gè)結(jié)點(diǎn)的“可擴(kuò)展標(biāo)記”，為“ -1的即目標(biāo)結(jié)點(diǎn)。由目標(biāo)結(jié)點(diǎn)上溯出路徑。見源程序1。方法二：?jiǎn)l(fā)式搜索構(gòu)造啟發(fā)式函數(shù)為：工C6.01 -ML CL滿足規(guī)則時(shí) f 二、 其它選擇較大值的結(jié)點(diǎn)先擴(kuò)展。見源程序2。四、實(shí)驗(yàn)結(jié)果 方法一的實(shí)驗(yàn)結(jié)果：傳教士野人過河問題第1種方法：1人，野人過去1人 1人，野人過去0人 0人，野人過去2人 0人，野人過去1人 2人，野人過去0人 1人，野人過去1人 2人，野人過

6、去0人 0人，野人過去1人 0人，野人過去2人第10次：右岸到左岸，傳教士過去0人，野人過去1人第11次：左岸到右岸，傳教士過去0人，野人過去2人第2種方法:第1次：左岸到右岸，傳教士過去 第2次：右岸到左岸，傳教士過去 第3次：左岸到右岸，傳教士過去 第4次：右岸到左岸，傳教士過去 第5次：左岸到右岸，傳教士過去 第6次：右岸到左岸，傳教士過去 第7次：左岸到右岸，傳教士過去 第8次：右岸到左岸，傳教士過去 第9次：左岸到右岸，傳教士過去1人，野人過去1人 1人，野人過去0人 0人，野人過去2人 0人，野人過去1人 2人，野人過去0人 1人，野人過去1人 2人，野人過去0人 0人，野人過去1

7、人 0人，野人過去2人第10次：右岸到左岸，傳教士過去第11次：左岸到右岸，傳教士過去1人，野人過去0人1人，野人過去1人第3種方法:第1次：左岸到右岸，傳教士過去 第2次：右岸到左岸，傳教士過去 第3次：左岸到右岸，傳教士過去 第4次：右岸到左岸，傳教士過去 第5次：左岸到右岸，傳教士過去 第6次：右岸到左岸，傳教士過去0人，野人過去2人0人，野人過去1人0人，野人過去2人0人，野人過去1人2人，野人過去0人1人，野人過去1人第1次：左岸到右岸，傳教士過去 第2次：右岸到左岸，傳教士過去 第3次：左岸到右岸，傳教士過去 第4次：右岸到左岸，傳教士過去 第5次：左岸到右岸，傳教士過去 第6次：

8、右岸到左岸，傳教士過去 第7次：左岸到右岸，傳教士過去 第8次：右岸到左岸，傳教士過去 第9次：左岸到右岸，傳教士過去第7次：左岸到右岸，傳教士過去 第8次：右岸到左岸，傳教士過去 第9次：左岸到右岸，傳教士過去 第10次：右岸到左岸，傳教士過去 第11次：左岸到右岸，傳教士過去 第4種方法: 第1次：左岸到右岸，傳教士過去 第2次：右岸到左岸，傳教士過去 第3次：左岸到右岸，傳教士過去 第4次：右岸到左岸，傳教士過去 第5次：左岸到右岸，傳教士過去 第6次：右岸到左岸，傳教士過去 第7次：左岸到右岸，傳教士過去 第8次：右岸到左岸，傳教士過去 第9次：左岸到右岸，傳教士過去 第10次：右岸到

9、左岸，傳教士過去第11次：左岸到右岸，傳教士過去 方法二的實(shí)驗(yàn)結(jié)果：傳教士野人過河問題方法如下2人，野人過去0人0人，野人過去1人0人，野人過去2人0人，野人過去1人0人，野人過去2人0人，野人過去2人0人，野人過去1人0人，野人過去2人0人，野人過去1人2人，野人過去0人1人，野人過去1人2人，野人過去0人0人，野人過去1人0人，野人過去2人1人，野人過去0人1人，野人過去1人1人，野人過去1人，野人過去0人，野人過去0人，野人過去2人，野人過去1人，野人過去2人，野人過去0人，野人過去0人，野人過去0人，野人過去0人，野人過去1 人 l:2r,2y r:1r,1y0 人 l:3r,2y r

10、:0r,1y2 人 l:3r,0y r:0r,3y1 人 l:3r,1y r:0r,2y0 人 l:1r,1y r:2r,2y1 人 l:2r,2y r:1r,1y0 人 l:0r,2y r:3r,1y1 人 l:0r,3y r:3r,0y2 人 l:0r,1y r:3r,2y1 人 l:0r,2y r:3r,1y2 人 l:0r,0y r:3r,3y第1次：左岸到右岸，傳教士過去 第2次：右岸到左岸，傳教士過去 第3次：左岸到右岸，傳教士過去 第4次：右岸到左岸，傳教士過去 第5次：左岸到右岸，傳教士過去 第6次：右岸到左岸，傳教士過去 第7次：左岸到右岸，傳教士過去 第8次：右岸到左岸，傳

11、教士過去 第9次：左岸到右岸，傳教士過去 第10次：右岸到左岸，傳教士過去 第11次：左岸到右岸，傳教士過去 問題結(jié)束 由結(jié)果可以看出，方法二的結(jié)果為方法一的第一種結(jié)果，兩者具有一致性。五、總結(jié)與教訓(xùn)：最開始時(shí)采用的方法為：用向量A=X0,X1,X2, X3,X4,X5,X6表示狀態(tài)，其X。X2表示三個(gè)傳教士的位置， X3X5表示三個(gè)野人的位置，X6表示船的位置表示在河左岸，1表示已渡過了河，在河右岸。設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為：S:So =0,0,0,0,0,0,0G:Sg =1,1,111,1,1但在描述規(guī)則時(shí)發(fā)現(xiàn)這樣定義會(huì)造成規(guī)則麻煩、不清晰，原因在于此題并不關(guān)心是哪幾個(gè)傳教士和野人在船

12、上，僅關(guān)心其人數(shù)，故沒有必要將每個(gè)人都設(shè)置變量，分別將傳教 士、野人、船作為一類即可。四、源代碼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左岸傳教士數(shù)2左岸野人數(shù)3船(1為左岸，0為右岸)%4是否可擴(kuò)展(1為可擴(kuò)展)5父節(jié)點(diǎn)號(hào)(-1表示無父節(jié)點(diǎn)，

13、即為初始節(jié)點(diǎn))j=1;% for j=1:nwhile (1)if j>nbreakendif node(j,4)=1 %判斷結(jié)點(diǎn)是否可擴(kuò)展if node(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 &&

14、 node(j,1)=node(j,2)forward(j,1,1);endif (node(j,1)=0 | node(j,1)=3)&& node(j,2)>=2 forward(j,0,2);endif (node(j,1)=2 && node(j,2)=2 | node(j,1)=3 && node(j,2)=1) forward(j,2,0);endelseif node(j,3)=0% 船在右岸if ( (node(j,1)=0) | (node(j,1)=3) )&&(node(j,2)<=2) afte

15、rward(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)<=1 afterward(j,0,2);endif (node(j,1)=1 && node(j,2)=1

16、| node(j,1)=0 && node(j,2)=2) afterward(j,2,0);endendendj=j+1；endfprintf('傳教士野人過河問題n');for t=1:nj=1;k=t;StepNum=1;if node(k,4)=-1while (k=-1) result(j)=k; k=node(k,5);j=j+1;endj=j-1;fprintf('第曲中方法：n',solveNum);while j>1BoatPriNum=node(result(j),1)-node(result(j-1),1);BoatW

17、ildNum=node(result(j),2)-node(result(j-1),2);if node(result(j),3)=1fprintf('第次：左岸到右岸，傳教士過去 d人，野人過去人n',StepNum,abs(BoatPriNum),abs(BoatWildNum);StepNum=StepNum+1; endif node(result(j),3)=0fprintf('第次：右岸到左岸，傳教士過去d人，野人過去人n',StepNum,abs(BoatPriNum),abs(BoatWildNum);StepNum=StepNum+1;endj

18、=j-1； end pause(0.2); fprintf('n'); solveNum=solveNum+1;endendfprintf(' 問題結(jié)束)；%從左岸到右岸，船上傳教士 x個(gè)，野人y個(gè)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)return endnode(z,4)=0;node(n,4)=1;node(n,5)=z;s=destination();if snode(

19、n,4)=-1;endn=n+1;%呱右岸到左岸，船上傳教士 x個(gè)，野人y個(gè)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 snode(n,4)=-1;endn=n+1;%function r=search(x)global n node;i=x;while node(i,5)=

20、-1if node(i,1)=node(n,1) && node(i,2)=node(n,2) && node(i,3)=node(n,3) r=0;returnendi=node(i,5);end%艮初始節(jié)點(diǎn)比較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

21、(n,2)=0 && node(n,3)=0 s=1;returnends=0;2.運(yùn)用啟發(fā)式函數(shù)%野人和傳教士過河問題%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左岸傳教士數(shù)2左岸野人數(shù)3船(1為左岸，0為右岸)%4是否可擴(kuò)展(1為可擴(kuò)展)5父節(jié)點(diǎn)號(hào)(-1表示無父節(jié)點(diǎn)，即為初始

22、節(jié)點(diǎn))index=1;open_list=1,0.01;% 節(jié)點(diǎn)號(hào)啟發(fā)函數(shù)值while (1)row,尸size(open_list);if row=0fprintf('all the nodes in open list have been expanded.'); returnendfor i1=1:rowopen_list(i1,2)=6.01-node(open_list(i1,1),1)-node(open_list(i1,1),2);%定義啟發(fā)函數(shù)if node(open_list(i1,1),4)=-1%如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則打印結(jié)果fprintf('傳

23、教士野人過河問題n');j=1;k=open_list(i1,1);StepNum=1;while (k=-1)result(j)=k;k=node(k,5);j=j+1；endj=j-1；fprintf('方法如下 n');while j>1BoatPriNum=node(result(j),1)-node(result(j-1),1);BoatWildNum=node(result(j),2)-node(result(j-1),2);if node(result(j),3)=1fprintf('第次：左岸到右岸，傳教士過去d人，野人過去人n',

24、StepNum,abs(BoatPriNum),abs(BoatWildNum);StepNum=StepNum+1;endif node(result(j),3)=0fprintf('第次：右岸到左岸，傳教士過去d人，野人過去人n',StepNum,abs(BoatPriNum),abs(BoatWildNum);StepNum=StepNum+1;endj=j-1；endpause(0.2);fprintf('問題結(jié)束 n');returnendendr_row,，尸find(open_list(:,2)=max(open_list(:,2);j=open_

25、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);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 |

26、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);endelseif node(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 | n

27、ode(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);endend%display(open_list);open_list(r_row(1),:)=;index=index-1;%open 表個(gè)數(shù)減 1%display(open_list);end%從左岸到右岸，船上傳教士 x個(gè)，野人y個(gè)function =forward(z,x