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

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