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

.

实验 传教士野人过河问题

37030602 王世婷

一、实验问题

传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

二、解答步骤

(1) 设置状态变量并确定值域

M为传教士人数，C 为野人人数，B为船数，要求M>=C且M+C <= 3，L表示左岸，R表示右岸。

初始状态 目标状态

L R L R

M 3 0 M 0 3

C 3 0 C 0 3

B 1 0 B 0 1

(2) 确定状态组，分别列出初始状态集和目标状态集

用三元组来表示Sf：（ML , CL , BL）（均为左岸状态）

其中0ML3,0CL3,BL ∈{ 0 , 1}

S0：(3 , 3 , 1)

Sg： (0 , 0 , 0)

初始状态表示全部成员在河的的左岸；

目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合

仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为

F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}

P10 if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 )

P01 if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 )

P11 if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 )

P20 if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 )

P02 if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 )

Q10

if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )

Q01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )

Q11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )

.

.

Q20

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) 当状态数量不是很大时，画出合理的状态空间图

图1 状态空间图

箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。

三、算法设计

方法一: 树的遍历

根据规则由根（初始状态）扩展出整颗树，检测每个结点的“可扩展标记”，为“-1”的即目标结点。由目标结点上溯出路径。

见源程序1。

.

.

方法二：启发式搜索

构造启发式函数为：

6.01MLCL满足规则时

f-其它选择较大值的结点先扩展。

见源程序2。

四、实验结果

方法一的实验结果：

传教士野人过河问题

第1种方法：

第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次：右岸到左岸，传教士过去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次：左岸到右岸，传教士过去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次：右岸到左岸，传教士过去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人，野人过去2人

第10次：右岸到左岸，传教士过去1人，野人过去0人

第11次：左岸到右岸，传教士过去1人，野人过去1人

方法二的实验结果：

传教士野人过河问题

方法如下

第1次：左岸到右岸，传教士过去1人，野人过去1人 l:2r,2y r:1r,1y

第2次：右岸到左岸，传教士过去1人，野人过去0人 l:3r,2y r:0r,1y

第3次：左岸到右岸，传教士过去0人，野人过去2人 l:3r,0y r:0r,3y

第4次：右岸到左岸，传教士过去0人，野人过去1人 l:3r,1y r:0r,2y

第5次：左岸到右岸，传教士过去2人，野人过去0人 l:1r,1y r:2r,2y

第6次：右岸到左岸，传教士过去1人，野人过去1人 l:2r,2y r:1r,1y

第7次：左岸到右岸，传教士过去2人，野人过去0人 l:0r,2y r:3r,1y

第8次：右岸到左岸，传教士过去0人，野人过去1人 l:0r,3y r:3r,0y

第9次：左岸到右岸，传教士过去0人，野人过去2人 l:0r,1y r:3r,2y

第10次：右岸到左岸，传教士过去0人，野人过去1人 l:0r,2y r:3r,1y

第11次：左岸到右岸，传教士过去0人，野人过去2人 l:0r,0y r:3r,3y

问题结束

由结果可以看出，方法二的结果为方法一的第一种结果，两者具有一致性。

五、总结与教训:

最开始时采用的方法为：用向量A{X0,X1,X2,X3,X4,X5,X6}表示状态，其中X0~X2表示三个传教士的位置，X3~X5表示三个野人的位置，X6表示船的位置。0表示在河左岸，1表示已渡过了河，在河右岸。

设初始状态和目标状态分别为：

.

.

S:S0{0,0,0,0,0,0,0}

G:Sg{1,1,1,1,1,1,1}

但在描述规则时发现这样定义会造成规则麻烦、不清晰，原因在于此题并不关心是哪几个传教士和野人在船上，仅关心其人数，故没有必要将每个人都设置变量，分别将传教士、野人、船作为一类即可。

四、源代码

1. 源程序1：树的遍历

%野人和传教士过河问题

%date:2010/12/14

%author:wang shi ting

function [ ]=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左岸传教士数 2左岸野人数 3船（1为左岸，0为右岸）

%4是否可扩展(1为可扩展) 5父节点号（-1表示无父节点，即为初始节点）

j=1;

% for j=1:n

while (1)

if j>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

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

end

j=j+1;

end

fprintf('传教士野人过河问题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(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;

end

end

fprintf('问题结束');

%%

%从左岸到右岸,船上传教士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)

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+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)

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+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;

return

end

r=1;%均不相同

%%

.

.

function s=destination()

global n node;

if node(n,1)==0 && node(n,2)==0 && node(n,3)==0

s=1;

return

end

s=0;

2. 运用启发式函数

%%

%野人和传教士过河问题

%date:2010/12/15

%author:wang shi ting

function [ ]=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.');

return

end

for 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 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次：左岸到右岸，传教士过去%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

end

end

[r_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)

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+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)

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+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(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;

return

end

r=1;%均不相同

%%

function s=destination()

global n node;

if node(n,1)==0 && node(n,2)==0 && node(n,3)==0

s=1;

return

end

s=0;

.