传教士野人过河问题-两种解法思路
-
实验
传教士野人过河问题
37030602
王世婷
一、实验问题
传教士和食人者问题（
The Missionaries
and Cannibals Problem
）
。在河的左岸
有
3
个传教士、
1
条船和
3
个食人者，传教士们想用这条船将所有的成员运过
河去，但是受
到以下条件的限制：
（
1
）传教士和食人者都会划船，但船一次最多只能装运两个；
（<
/p>
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)
确定状态组，分别列出初始状态集和目标状态集
用三元组来表示
S
f
：
（
ML , CL ,
BL
）
（均为左岸状态）
其中
0
ML
3,0
CL
3
,BL
∈
{ 0 , 1}
S
0
：
(3
, 3 , 1)
S
g
：
(0
, 0 , 0)
初始状态表示全部成员在河的的左岸；
目标状态表示全部成员从河的左岸全部渡河完毕。
(3)
定义并确定规则集合
仍然以河的左岸
为基点来考虑，把船从左岸划向右岸定义为
Pij
操作。其中，
第一
下标
i
表示船载的传教士数，第二
下标
j
表示船载的食人者数；同理，从右岸将船划回
左岸称之为
Qij
操作，下标的定义同前。则共有
10
种操作，操作集为
F={P01
，
P10<
/p>
，
P11
，
P0
2
，
P20
，
Q01
，
Q10
，
Q11
，
Q02
，
Q20}
P
10
if ( ML ,CL , BL=1 ) then (
ML
–
1 , CL , BL
–
1 )
P
01
if
( ML ,CL , BL=1 ) then ( ML ,
CL
–
1 , BL
–
1 )
P
11
if
( ML ,CL , BL=1 ) then (
ML
–
1 ,
CL
–
1 , BL
–
1 )
P
20
if
( ML ,CL , BL=1 ) then (
ML
–
2 , CL , BL
–
1 )
P
02
if
( ML ,CL , BL=1 ) then ( ML ,
CL
–
2 , BL
–
1 )
Q
10
if ( ML ,CL , BL=0 ) then ( ML+1 , CL
, BL+1 )
Q
01
if ( ML ,CL , BL=0 ) then ( ML , CL+1
, BL +1 )
Q
11
if ( ML ,CL , BL=0 ) then ( ML+1 , CL
+1, BL +1 )
Q
20
if ( ML ,CL , BL=0 ) then ( ML+2 , CL
+2, BL +1 )
Q
02
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<
/p>
人，野人过去
1
人
第
5
次：左岸到右岸，传教士过去
2
人，野人过去
0
人
第
6
次：右岸到左岸，传教士过去
1
人，野人过去
< br>1
人
第
7
次：左岸到右岸，传教士过去
2
人
，野人过去
0
人
第
8
次：右岸到左岸，传教士过去
0
人，野人过去
1
人
< br>
第
9
次：左岸到右岸，传教士
过去
0
人，野人过去
2
人
第
10
< br>次：右岸到左岸，传教士过去
0
人，野人过去
1
人
第
11
次：左岸到右岸，传教士过去
0
< br>人，野人过去
2
人
第
2
种方法：
第
1
次：左岸到右岸，传教士过去
1
人，野人过去
1
人
第
2
次：
右岸到左岸，传教士过去
1
人，野人过去
0
人
第
3
次：左岸到右岸，传教士过去
0
人，野
人过去
2
人
第
4
次：右岸到左岸，传教士过去
0<
/p>
人，野人过去
1
人
第
5
次：左岸到右岸，传教士过去
2
人，野人过去
0
人
第
6
次：右岸到左岸，传教士过去
1
人，野人过去
< br>1
人
第
7
次：左岸到右岸，传教士过去
2
人
，野人过去
0
人
第
8
次：右岸到左岸，传教士过去
0
人，野人过去
1
人
< br>
第
9
次：左岸到右岸，传教士
过去
0
人，野人过去
2
人
第
10
< br>次：右岸到左岸，传教士过去
1
人，野人过去
0
人
第
11
次：左岸到右岸，传教士过去
1
< br>人，野人过去
1
人
第
3
种方法：
第
1
次：左岸到右岸，传教士过去
0
人，野人过去
2
人
第
2
次：
右岸到左岸，传教士过去
0
人，野人过去
1
人
第
3
次：左岸到右岸，传教士过去
0
人，野
人过去
2
人
第
4
次：右岸到左岸，传教士过去
0<
/p>
人，野人过去
1
人
第
5
次：左岸到右岸，传教士过去
2
人，野人过去
0
人
第
6
次：右岸到左岸，传教士过去
1
人，野人过去
< br>1
人
第
7
次：左岸到右岸，传教士过去
2
人
，野人过去
0
人
第
8
次：右岸到左岸，传教士过去
0
人，野人过去
1
人
< br>
第
9
次：左岸到右岸，传教士
过去
0
人，野人过去
2
人
第
10
< br>次：右岸到左岸，传教士过去
0
人，野人过去
1
人
第
11
次：左岸到右岸，传教士过去
0
< br>人，野人过去
2
人
第
4
种方法：
第
1
次：左岸到右岸，传教士过去
0
人，野人过去
2
人
第
2
次：
右岸到左岸，传教士过去
0
人，野人过去
1
人
第
3
次：左岸到右岸，传教士过去
0
人，野
人过去
2
人
第
4
次：右岸到左岸，传教士过去
0<
/p>
人，野人过去
1
人
第
5
次：左岸到右岸，传教士过去
2
人，野人过去
0
人
第
6
次：右岸到左岸，传教士过去
1
人，野人过去
< br>1
人
第
7
次：左岸到右岸，传教士过去
2
人
，野人过去
0
人
第
8
次：右岸到左岸，传教士过去
0
人，野人过去
1
人
< br>
第
9
次：左岸到右岸，传教士
过去
0
人，野人过去
2
人
第
10
< br>次：右岸到左岸，传教士过去
1
人，野人过去
0
人
第
11
次：左岸到右岸，传教士过去
1
< br>人，野人过去
1
人
方法二的实验结果：
传教士野人过河问题
方法如下
第
1
次：左岸到右岸，传教士过去
1
人，
野人过去
1
人
第
2
次：右岸到左岸，传教士过去
1
人，野人过去
0
人
第
3
次：左岸到右岸，传教士过
去
0
人，野人过去
2
< br>人
第
4
次：右岸到左岸，传教士过去
0
人，野人过去
1
人
第
5
次：左岸到右岸，传教士过去
2
人，野人过去
0
人
< br>第
6
次：右岸到左岸，传教士过去
1
人，野人过去
1
人
第
7
次：左岸到右岸，传教
士过去
2
人，野人过去
0
人
第
8
< br>次：右岸到左岸，传教士过去
0
人，野人过去
1
人
第
9
次：左岸到右岸，传教士过去
0
人，野人过去
2
人
第
10
次：右岸到左岸，传教士过去
0
人，野人过去
1
人
第
11
次：左岸到右
岸，传教士过去
0
人，野人过去
2
人
问题结束
由结果可以看出，方法二的结果为方法一的第一种结果，两者
具有一致性。
五、总结与教训
:
最开始时采用的方
法为：
用向量
A
{
X
0
,
X
1
,
X
2<
/p>
,
X
3
,
X
4
,
X
5
,
X
6
}
表示状态，其中
X
0
~
X
2
表示三个传教
士的位置，
X
3
~
X
5
表示三个野人的位置，
X
6
表示船的位置。
0
表示在河左岸，
1
表示已渡过了河，在河右岸。
设初始状态和目标状态分别为：
S
:
S
0
{0,0,0,0,0,0,0}
G
:
S
g
{
1
,1
,
1
,1
,1
,1
,1
}
但在描述规则时发现这样定
义会造成规则麻烦、不清晰，
原因在于此题并不关心是哪几
个传
教士和野人在船上，仅关心其人数，故没有必要将每个人都设置变量，分别将传教
士、野
人、船作为一类即可。
四、源代码
1.
< br>源程序
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
fp
rintf('
传教士野人过河问题
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