1、精品好資料學習推薦 14 / 13 實驗 傳教士野人過河問題 37030602 王世婷 一、實驗問題 傳教士和食人者問題(The Missionaries and Cannibals Problem)。在河的左岸有3 個傳教士、1條船和3個食人者，傳教士們想用這條船將所有的成員運過河去，但是受 到以下條件的限制：(1)傳教士和食人者都會劃船，但船一次最多只能裝運兩個；(2) 在任何岸邊食人者數目都不得超過傳教士，否則傳教士就會遭遇危險：彼食人者攻擊甚 至被吃掉。此外，假定食人者會服從任何一種過河安排，試規劃出一個確保全部成員安 全過河的計劃。 二、解答步驟 (1) 設置狀態變量并確定值域 M為

2、傳教士人數，C為野人人數，B為船數，要求MHCJ1M+C = 3, L表示左岸， R表示右岸。 (2) 確定狀態組，分別列出初始狀態集和目標狀態集 用三元組來表示S：(ML , CL , BL)(均為左岸狀態) 其中0ML3,0CL 1) (3, 0, 0) J f=2 Qoi 3, 1, 1) + f=4 Pzo n break end 辻node(j, 4)=1 %判斷結點是否可擴展 if node (j, 3)=1 %船在左岸 if ( (node(j, 1)=0) I I (node(j, 1)=3) ) end if (node(j, 1)=1 end if (node (j, 1)

3、=1 end if (node (j, l)=0 node (j, 1)=3) end if (node(j, 1)=2 end elseif node (j, 3)=0%船在右岸 if ( (node(j, 1)=0) I (node(j, 1)=3) ) end if (node(j, 1)=2 end if (node (j, 1)=2 end if (node (j, l)=0 node(j, 1)=3) BoatWildNum=node (result (j), 2)-node (result (jT), 2); if node(result(j), 3)=1 fprintf(第%d

4、次：左岸到右岸，傳教士過去d人，野人過去d人 n， StepNum, abs(BoatPriNum), abs(BoatWi1dNum); S t epNum= S t epNum*1; end if node(result(j), 3)=0 fprintf(*第%d次：右岸到左岸，傳教士過去%d人，野人過去%d人 n， StepNum, abs(BoatPriNum), abs(BoatWi1dNum); StepNum=StepNum+1; end j 二 jT； end pause (0. 2); fprintf(，n); solveNum=solveNum+l; end end fpr

5、intfC問題結束)； $從左岸到右岸，船上傳教士 x個，野人y個 function =forward(z, x, y) global n; global node; node (n, l)=node (z, l)x; node(n, 2)=node(z, 2)-y; node(n,3)=0; r=search (z); 辻(r) return end node(z, 4)=0; node (n, 4)=1; node(n,5)=z; s=destination(); if s node (n, 4)=_1; end n=n+l; % 觥從右岸到左岸，船上傳教士 x個，野人y個 functio

6、n =afterward(z, x, y) global n; global node; node (n, l)=node (z, l)+x; node(n,2)=node(z, 2)+y; node(n, 3)=1; r=search (z); 辻(r) return end node(z, 4)=0; node(n, 4)=1; node (n, 5)=z; s=destination(); if s node (n, 4)=T; end n=n+l; % function r=search(x) global n node; i=x; while node(i, 5)=1 if node

7、(i, 1) =node(n, 1) return end i=node(i, 5); end 弔跟初始節點比較 if node(i, l)=node(n, 1) return end r=l;%均不相同 % function s=destination。 global n node; if node (n, 1)=0 return end s=0; 2.運用啟發式函數 % %野人和傳教士過河問題 %date:2010/12/15 %author:wang shi ting function =guohe() clear all; close all; global n node open_l

8、ist index; n=2; result=zeros(100,1); node=zeros(100,5); node(l, :) = 3, 3,1, 1,-lJ ；%初始化 沁左岸傳教士數2左岸野人數3船(1為左岸，0為右岸) $4是否可擴展(1為可擴展)5父節點號(-1表示無父節點，即為初始節點) index=l; open_list=l, 0. 01J :%節點號 啟發函數值 while (1) Erow, 二size(open_list); if row=0 fprintf C all the nodes in open list have been expanded)； retur

9、n end for il=l:row open_list(il, 2)=6 01-node(open_list(il, 1), l)-node(open_list(il, 1), 2);% 定義啟發函數 if node(open_list (il, 1), 4)=1%如果該結點是目標結點，則打印結果 fprintf (*傳教士野人過河問題n); J=l； k=open_list(il, 1); StepNum 二1; while (k=-l) result(j)=k; k=node(k,5); j二j+l; end fprintf(方法如下n); while jl BoatPriNum=nod

10、e(result(j), 1)node(result(jl),1); BoatWildNum=node (result (j), 2)-node (result (jT), 2); if node(result(j), 3)=1 fprintfC第d次：左岸到右岸，傳教士過去d人，野人過去d人 n， StepNum, abs(BoatPriNum), abs(BoatWi1dNum); S t epNum= S t epNum*1; end if node(result(j), 3)=0 fprintfC第%d次：右岸到左岸，傳教士過去%d人，野人過去%d人 n， StepNum, abs(B

11、oatPriNum), abs(BoatWi1dNum); S t epNum= S t epNum1; end end pause (0.2); fprintfC問題結束n); return end end r_row,=find(open_list(:, 2)=max(open_list (:,2); j=open_list(r_row(l, 1), 1); if node (j, 3)=1 %船在左岸 if ( (node(j, 1)=0)| (node (j, 1)=3) ) end if (node(j, 1)=1 end if (node (j, 1)=1 end if (node

12、 (j, l)=0 node (j, 1)=3) end if (node(j, 1)=2 end elseif node (j, 3)=0%船在右岸 if ( (node (j, 1)=0)| (node (j, 1)=3) ) end if (node(j, 1)=2 end if (node (j, 1)=2 end if (node (j, l)=0 node (j, 1)=3) end if (node (j, 1)=1 end end %display(open_list); open_list(r_row(l),:)=E ; index=indexl; %open 表個數減 1

13、%display (open_list); end % $從左岸到右岸，船上傳教士 x個，野人y個 function L=forward(z, x, y) global n; global node open_list index; node (n, l)=node (z, l)x; node(n,2)=node(z, 2)-y; node (n, 3)=0; r=search (z); 辻(F return end node(z, 4)=0; node (n, 4)=1; node (n, 5)=z; s二destination (); if s node (n, 4)=-1; end in

14、dex=index+l; open_list(index, l)=n; n=n+l; % 眥從右岸到左岸，船上傳教士 X個，野人y個 function =afterward(z, x, y) global n; global node open_list index; node (n, l)=node (z, l)+x; node(n,2)=node(z, 2)+y; node (n, 3)=1; r=search(z); 辻(F return end node(z, 4)=0; node (n, 4)=1; node(n, 5)=z; s=destination(); if s node (n, 4)=-1; end index=index+l; open_list(index, l)=n; n=n+l; % function r=sear