




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn) 傳教士野人過河問題 王世婷一、實(shí)驗(yàn)問題傳教士和食人者問題(The Missionaries and Cannibals Problem)。在河的左岸有3個傳教士、1條船和3個食人者,傳教士們想用這條船將所有的成員運(yùn)過河去,但是受到以下條件的限制:(1)傳教士和食人者都會劃船,但船一次最多只能裝運(yùn)兩個;(2)在任何岸邊食人者數(shù)目都不得超過傳教士,否則傳教士就會遭遇危險:被食人者攻擊甚至被吃掉。此外,假定食人者會服從任何一種過河安排,試規(guī)劃出一個確保全部成員安全過河的計劃。二、解答步驟(1) 設(shè)置狀態(tài)變量并確定值域M為傳教士人數(shù),C 為野人人數(shù),B為船數(shù),要求M&g
2、t;=C且M+C <= 3,L表示左岸,R表示右岸。初始狀態(tài)目標(biāo)狀態(tài)LRLRM30M03C30C03B10B01(2) 確定狀態(tài)組,分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集用三元組來表示:(ML , CL , BL)(均為左岸狀態(tài))其中,BL 0 , 1 :(3 , 3 , 1) : (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,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 ) Q
4、10 if ( 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) 當(dāng)狀態(tài)數(shù)量不是很大時,畫出合理的狀態(tài)空間圖 圖1 狀態(tài)空間圖箭頭旁邊所標(biāo)的數(shù)
5、字表示了或操作的下標(biāo),即分別表示船載的傳教士數(shù)和食人者數(shù)。三、算法設(shè)計方法一: 樹的遍歷根據(jù)規(guī)則由根(初始狀態(tài))擴(kuò)展出整顆樹,檢測每個結(jié)點(diǎn)的“可擴(kuò)展標(biāo)記”,為“-1”的即目標(biāo)結(jié)點(diǎn)。由目標(biāo)結(jié)點(diǎn)上溯出路徑。見源程序1。方法二:啟發(fā)式搜索構(gòu)造啟發(fā)式函數(shù)為:選擇較大值的結(jié)點(diǎn)先擴(kuò)展。見源程序2。四、實(shí)驗(yàn)結(jié)果方法一的實(shí)驗(yàn)結(jié)果:傳教士野人過河問題第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次:左岸到右岸,傳
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次:右岸到左岸,傳教士過去
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人,野
9、人過去2人第10次:右岸到左岸,傳教士過去1人,野人過去0人第11次:左岸到右岸,傳教士過去1人,野人過去1人方法二的實(shí)驗(yàn)結(jié)果:傳教士野人過河問題方法如下第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次:右岸
10、到左岸,傳教士過去0人,野人過去1人第11次:左岸到右岸,傳教士過去0人,野人過去2人問題結(jié)束由結(jié)果可以看出,方法二的結(jié)果為方法一的第一種結(jié)果,兩者具有一致性。五、總結(jié)與教訓(xùn):最開始時采用的方法為:用向量表示狀態(tài),其中表示三個傳教士的位置,表示三個野人的位置,表示船的位置。表示在河左岸,表示已渡過了河,在河右岸。設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為:但在描述規(guī)則時發(fā)現(xiàn)這樣定義會造成規(guī)則麻煩、不清晰,原因在于此題并不關(guān)心是哪幾個傳教士和野人在船上,僅關(guān)心其人數(shù),故沒有必要將每個人都設(shè)置變量,分別將傳教士、野人、船作為一類即可。 四、源代碼1. 源程序1:樹的遍歷%野人和傳教士過河問題%date:2010/
11、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)號(-1表示無父節(jié)點(diǎn),即為初始節(jié)點(diǎn))j=1;% for j=1:nwhile (1) if j>n break end if node(j,4)=1 %判斷結(jié)點(diǎn)是否可擴(kuò)展 i
12、f 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)=
13、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 | nod
14、e(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)
15、; 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=node(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(
16、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(
17、0.2); fprintf('n'); solveNum=solveNum+1; endendfprintf('問題結(jié)束');%從左岸到右岸,船上傳教士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;en
18、dn=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 no
19、de(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%跟初始節(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(n,2
20、)=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)號(-1表示無父節(jié)點(diǎn),即為初始
21、節(jié)點(diǎn))index=1;open_list=1,0.01;%節(jié)點(diǎn)號 啟發(fā)函數(shù)值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);%定義啟發(fā)函數(shù) if node(open_list(i1,1),4)=-1%如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn),則打印結(jié)果 fprintf(
22、39;傳教士野人過河問題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 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次:左岸到右岸,
23、傳教士過去%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('問題結(jié)束n'); return endendr_row,=find
24、(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(
25、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) aft
26、erward(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表個數(shù)減1%display(open_list); end%從左岸到右岸,船上傳教士x個,野人y個 function =forward(z,x,y)global n;global node open_list index;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年行業(yè)職業(yè)技能考試試卷及答案
- 氣候?yàn)?zāi)害鏈?zhǔn)椒磻?yīng)-洞察及研究
- 2025年數(shù)字化轉(zhuǎn)型與管理模型考試試卷及答案
- 2025年食品衛(wèi)生檢驗(yàn)員資格考試試題及答案
- 2025年社會行為與心理適應(yīng)性的考試試題及答案
- 2025年數(shù)學(xué)建模大賽選手備考試卷及答案
- 2025年社交媒體營銷與傳播考試試題及答案
- 新農(nóng)人電商培育-洞察及研究
- 2025年汽車工程專業(yè)執(zhí)業(yè)資格考試試卷及答案
- 2025年教師資格證面試試題及答案
- 2025至2030年中國豆角絲行業(yè)投資前景及策略咨詢報告
- 消防心理測試題或答案及答案
- 全國中級注冊安全工程師考試《其他安全》真題卷(2025年)
- 南開大學(xué)-商業(yè)健康保險與醫(yī)藥產(chǎn)業(yè)高質(zhì)量協(xié)同發(fā)展-團(tuán)體補(bǔ)充醫(yī)療保險改革新視角-2025年3月20日
- 弱電安防施工安全培訓(xùn)
- 電梯維保半年工作總結(jié)
- 12《尋找生活中的標(biāo)志》(教學(xué)設(shè)計)-2023-2024學(xué)年二年級上冊綜合實(shí)踐活動魯科版
- 七年級道法下冊 第二學(xué)期 期末綜合測試卷(人教海南版 2025年春)
- 《隱身復(fù)合材料》課件
- 架橋機(jī)常見安全隱患
- 學(xué)校保潔服務(wù)投標(biāo)方案(技術(shù)標(biāo))
評論
0/150
提交評論