商人过河问题

商人过河问题

一、三名商人各带一名随从的情况

1． 问题（略）

2． 模型假设

① 当一边岸满足随从数大于商人数，但商人数为0时仍为一种安全状态； ② 小船至多可容纳2人，且渡河时由随从（或者商人）来划船。

3． 分析与建模

商人过河需要一步一步实现，比如第一步：两个仆人过河，第二步：一个仆人驾船回来，第三步：又是两个仆人过河，第四步：……

其中每一步都使当前状态发生变化，而且是从一种安全状态变为另一种安全状态。如果我们把每一种安全状态看成一个点，又如果存在某种过河方式使状态a 变到状态b ，则在点a 和点b 之间连一条边，这样我们把商人过河问题和图联系起来，有可能用图论方法来解决商人过河问题。

建模步骤：⑪首先要确定过河过程中的所有安全状态，我们用二元数组(x , y ) 表示一个安全状态（不管此岸还是彼岸），其中x 表示留在此岸的主人数，y 表示留在此岸的随从数。两岸各有十种安全状态：

(0,0),(0,1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3)

⑫在两岸的安全状态之间，如存在一种渡河方法能使一种状态变为另一种安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图1），其中下方顶点表示此岸状态，上方顶点表示彼岸状态。我们的目的是要找出一条从此岸(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 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];

index=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到16的长度为11的路：1 4 3 6 5 8 9 12 11 14 7 16，此路对应商人成功渡河的一个方案：

（3,3）变为（3,1）变为（3,2）变为（3,0）变为（3,1）变为（1,1）变为（2,2）变为（0,2）变为（0,3）变为（0,1）变为（1,1）变为（0,0）

即：两个仆人过河，一个仆人回来；有两个仆人过河，一个仆人回来；两个主人过河，一主一仆回来；有两个主人过河，一个仆人回来；两个仆人过河，一个仆

人回来；最后两个仆人过河。这样，商人安全过河。

若把刚才的最短路上的边权全部改大，如取2或3，重新运行程序sroute.m ，得到同样的结果，但实际上还有另外一种安全渡河状态：

(3,3)变为(2,2)变为(3,2)变为(3,0)变为(3,1)变为(1,1)变为(2,2)变为(0,2)变为(0,3)变为(0,1)变为(0,2)变为(0,0)

5． 图解法

将十种安全状态的点在直角坐标系中标出，如下图

（0,0），（0,1），（0,2），（0,3），（2,2），（1,1），（3,0），（3,1），（3,2），（3,3） （实线表示才此岸开往彼岸，虚线表示才彼岸开往此岸）

s n +1

图中d 1到d 11给出了商人安全渡河的一条路径。

二、四名商人各带一名随从

1. 问题：四名商人各带一名随从时，就附加说明条件才能实现安全渡河。

2. 原模型求解

改编程序sroute.m 重新运行，或用递归的方法程序运行，结果运行出现错误或死机，这说明模型无解，即四名商人各带一名随从在原条件下无安全状态渡河。

所以我们需附加一定的条件，使模型有解。由第一问中的条件可知：商人渡河的限制条件是在任何一边岸商人数一定要比随从数多且小船最多只能载2人，而安全状态（即商人数比随从数多）是最其本的前提条件，因此我们考虑更改小船的容量来实现安全渡河。

3. 新模型及求解

当小船的容量为5或大于5时，显然一种安全渡河方式为：先4名随从渡河，1名随从回来；随后4名商人与回来的那名随从一起渡河。当小船容量为4时，一种渡河方案为：先4名随从渡河，1名随从回来；再3名商人渡河，1名商人

和1名随从回来；最后2名商人和2名随从一起渡河。

现在我们考虑小船容量为3时的情况：（在这我们用图解法来完成）

①9步渡河方案（如图⑪所示）：

1 2 3 4 x

图⑪

即：第一步先三名随从过河，一名随从回来；再两名商人过河，一名商人和一名随从回来；再三名商人过河，一名随从回来；再三名随从过河，一名随从回来；最后两名随从过河。

②11步度河方案（如图⑫所示）：

0 1 2 3 4 x

图⑫

即：第一步先一名商人和一名随从过河，一名商人回来；再三名随从过河，一名随从回来；再三名商人过河，一名商人和一名随从回来；再两名商人过河，一名随从回来；最后三名随从一起过河。

③13步渡河方案（如图⑬所示）：

1 2 3 4 x

图⑬

即：第一步先一名商人和一名随从过河，一名商人回来；再两名随从过河，一名随从回来；再两名随从过河，一名随从回来；在三名商人过河，一名商人和一名随从回来；再两名商人过河，两名随从回来；再三名随从过河，一名随从回来；最后三名随从一起过河。