商人过河问题
-
商人过河问题
一、三名商人各带一名随从的情况
1
．
问题（略）
2
．
模型假设
①
当一边岸满足随从数大于商人数，但商人数为
0
时仍为一种安全状态；
②
小船至多可容纳
2
人，且渡河时由随从
（或者商人）来划船。
3
．
分析与建模
商人过河需要一步一步实
现，比如第一步：两个仆人过河，第二步：一个仆
人驾船回来，第三步：又是两个仆人过
河，第四步：……
其中每一步都使当前状态发生变化，
而且是从一种安全状态变为另一种安全
状态。
如果我们把每一种安全状态看成一个点，
又如果存在某种过河方式使状态
a
变到状态
b
，则在点
a
和点
b
之间连一条
边，这样我们把商人过河问题和图联
系起来，有可能用图论方法来解决商人过河问题。<
/p>
建模步骤：
⑪首先要确定过河过程中的
所有安全状态，
我们用二元数组
(
x<
/p>
,
y
)
表示一个
安全状态（不管此岸还是彼岸）
，其中
x
表示留在此岸的主人数，
y
表
示留在
此岸的随从数。两岸各有十种安全状态：
(0,0),(0,
1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3)
⑫在两岸的安全状态之间，
如存在一
种渡河方法能使一种状态变为另一种安
全状态，则在这两种状态之间连一条边。这样，得
到如下一个二部图（图
1
）
，
其中下方顶点表示此岸状态，
上方顶点表示彼岸状态。
< br>我们的目的是要找出一条
从此岸
(3,3)
到彼岸
(0,0)
的最短路。
⑬观察发现此岸的状态
(0,0)
，
(3,0)
和彼岸的状态
(0,3)
，
(3,3)
都是孤立点，
在求最短路的过程中不涉及这些点，
把它们删去。
两岸的点用
1,2,
……，
16
重新
标号。
（
3,3
）
（
3,2
）
（
3,1
）
（
3,0
）
（
1,1
）
（
2,2
）
（
0,3
）
（
0,2
）
（
0,3
）
（
0,0
）
12
○
14
○
16
○
②
④
⑥
⑧
⑩
○
○
11
○
13
○
15
○
①
③
⑤
○
⑦
⑨
○
（
3,3
）
（
3,2
）
（
3,1
）
（
3,0
）
（
1,1
）
（
2,2
）
（
0,3
）
（
0,2
）
（
0,3
）
（
0,0
）
(
图
1)
4
．
模型求解
求最短路程的
matlab
程序
sroute.m
如下：
function
route=sroute(G,opt)
%
求图的最短路的
Dijkstra
算法程序，规定起点为
1
，顶点连续编号
%G
是给定图的邻接矩阵或弧表矩阵，程序能够自动识别
%
当
opt=0
（或缺省）时求无
向图的最短路，当
opt=1
时求有向图的最短路
%d
——标记最短距离
%route
是一个矩阵，第一行标记顶点，第二行标记
1
到该点的最短路，第三行标记最短路上该点
的先驱顶点
while
1
%
此循环自动识别或由弧表矩阵生成邻接矩阵
if
G(1,1)==0
A=G;
break
else
e=G
n=max([e(:,1);e(:,2)]);
%
顶点数
m=size(e,1);
%
边数
M=sum(e(:,3));
%
代表无穷大
A=M*ones(n,n);
for
k=1:m
A(e(k,1),e(k,2))=e(k,3);
if
opt==0
A(e(k,2),e(k,1))=e(k,3);
%
形成无向图的邻接矩阵
end
end
A=A-M*eye(n)
%
形成图的邻接矩阵
end
break
end
pb(1:length(A))=0;pb(1)=1;
index1=1;
index2=ones(1,length(A));
d(1:length(A))=M;d(1)=0;
%
标记距离
temp=1;
while
的命令窗口输入图（ 16 ）变为（
0,2 <
br>）变为（
sum(pb)
tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+A(temp,tb));
%
更新距离
temp=find(d(tb)==min(d(tb)));
%
确定新最小距离点
temp=tb(temp(1));
pb(temp)=1;
index1=[index1,temp];
in
dex=index1(find(d(index1)==d(temp)-A(temp,index1))
);
if
length(index)>=2
index=index(1);
end
index2(temp)=index;
%
记录前驱顶点
end
route=[1:n;d;index2];
在
matlab
1
）的弧表矩阵
e:
e=[1
2;1
4;1
10;3
4;3
6;3
10;5
6;5
8;7
14;7
16;9
8;9
12;11
12;11
14;13
14;13
16;15 16];
e=[e,ones(17,1)];
%
边权都设为
1
调用程序
sroute.m
：
route=sroute(e,0)
运行结果：
e =
1
2
1
1
4
1
1
10
1
3
4
1
3
6
1
3
10
1
5
6
1
5
8
1
7
14
1
7
16
1
9
8
1
9
12
1
11
12
1
11
14
1
13
14
1
13
16
1
15
16
1
route =
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
1
2
1
4
3
10
5
6
1
8
7
10
9
12
11
1
1
4
1
6
3
14
5
8
1
12
9
14
11
16
7
这表示存在一条从
1
到
的长度为
11
的路：
1
4
3
6
5
8
9
12
11
14
7
16
，此路对应商人成功渡河的一个方案：
（
3,3
3,1
）变为（
3,2<
/p>
）变为（
3,0
）变为（
3,1
）变为（
1,1
）变为
（
2,2
）
变为（
）变为（
0,3
）变为（<
/p>
0,1
）变为（
1,1
0,0
）
即：两个仆人过河，一个仆人回来；有两个仆人过河，一个仆
人回来；两个主人
过河，一主一仆回来；有两个主人过河，一个仆人回来；两个仆人过河
，一个仆-