商人随从过河

题目：商人随从过河

姓名：*** 姓名：*** 姓名：王 *

2011年08月25日

队员：

商人过河问题

摘要

本文针对商人渡河的问题，建立分步决策模型，采用Dijkstra算法解决了商人和随从渡河问题。

根据题意用三维向量表示商人、随从和船的状态，并且定义此岸允许状态集合、彼岸允许状态集合及决策变量集合。然后把此岸允许状态集合和彼岸允许状态集合中的每个元素视为节点，按照状态转移规律连接这些节点构成了一个连通图，寻找安全的渡河方案最终转化为从起始状态（节点）到最终状态（节点）的路径，用图论的Dijkstra算法找出所有路径，每一条路径对应一种渡河方案，整体方案如图1（实心点代表此岸，空心点代表彼岸，人数均为此岸人数），由图可知共有四种渡河方案。

图1 整体渡河方案

关键词: 分步决策 Dijkstra算法 三维向量 连通图

1 问题重述

三名商人各带一名随从过河，随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?（如果推广到四名商人四个随从又如何？）

2 模型假设

（1）商人和仆人都会划船，并且仆人听从商人的调度 （2）商人和仆人每次渡船都能安全到达

（3）船的质量很好，在多次满载情况也能正常运作

3 符号说明

(1) sk第k次渡河前此岸商人和仆人的数量称为状态向量；

第k次渡河前彼岸商人和仆人的数量称为状态向量； (2) sk(3) S所有安全渡河条件下状态向量的集合； (4) S所有安全渡河条件下状态向量的集合； (5) dk第k次渡河船上商人和仆人的数称为决策向量； (6) D所有安全渡河条件下决策向量的集合； (7) xk 第k次渡河前此岸的商人数；

 第k次渡河前彼岸的商人数； (8) xk(9) yk 第k次渡河前此岸的仆人数；

 第k次渡河前此岸的仆人数； (10) yk(11) uk 第k次渡船上的商人数； (12) vk第k次渡船上的仆人数。

4 模型的建立与求解

4.1 模型的建立

用三维向量(xk,yk,1)，表示安全渡河条件下此岸商人、随从和船的状态，用

''表,yk,0)，表示安全渡河条件下彼岸商人、随从和船的状态。xk,xk三维向量(xk表示随从数，xk,yk的取值范围是{0,1,2,3}； 示商人数，yk,yk记第k次渡河前此岸的商人数为xk，随从数为yk，k1,2,，

xk,yk0,1,2,3。将三维向量sk(xk,yk,1)定义为此岸状态，安全渡河条件下此岸

状态集合称为此岸允许状态集合，记作S。

S{(x,y,1)|x0或x3,y0,1,2,3;xy1,2} (1)

记第k次渡河前彼岸的商人数为xk'，随从数为yk'，k1,2,，

'''''xk,yk0,1,2,3。将三维向量sk(xk,yk,0)定义为彼岸状态，安全渡河条件下彼

岸状态集合称为彼岸允许状态集合，记作S'。

S'{(x',y',0)|x3或x0,y0,1,2,3;xy1,2} (2)

记第k次渡船上的商人数为uk，随从人数为vk，将二维向量dk(uk,vk)定义为决策变量。允许决策集合记作D，由船的容量可知

D{(u,v)|1uv2,u,v0,1,2} (3)

这样状态转移时满足以下规律

'',yk,0)时此岸和彼岸人数1．当k为奇数时，船从此岸到彼岸，即(xk,yk,1)(xk变化为

xk1xkuk (4) yyvkkk1''xk1xkuk (5) ''yk1ykvk'',yk,0)(xk,yk,1)时彼岸和此岸人数变2.当k为偶数时，船从彼岸到此岸，即(xk化为

''xk1xkuk (6) ''yk1ykvkxk1xkuk (7) yyvkkk1(4)(7)式称为状态转移规律。这样制定安全渡河方案归结为多步骤决策模型。

4.2 模型求解

求解多步决策模型，即求决策变量dkD(k1,2,,n)，使状态skS且

S按照转移规律(4)sk'sk(3,3,0)。

(7)式，由初始状态s1(3,3,1)经有限步到达状态

把此岸允许状态集合S的每一个元素（状态）都当作是一个节点，同理把彼岸允许状态集合S的每一个元素（状态）也都当作是一个节点，从状态s1(3,3,1)开始，在彼岸S集合中找到满足公式(5)的节点（状态），如果在S中找到能找

,s2,s3到了相应的节点（状态），假设为s1,s2,s3然后分别从s1,s2,s3则把s1和s1用线段连接起来；

出发按(6)~(7)式在S中找出满足(7)式的节点（元素），如

,s2,s3则把节点s1果在S中找到能找到了相应的节点（状态），假设为s2,s3别和相应s2,s3分

'(3,3,0)节点。 用线段连接，如此循环，直到到达sk这样经过以上循环S中的节点（状态）都和S中的节点（状态）相连接，却

构成一个连通图如图2所示。

图2 渡河连通图

这样寻找安全的渡河方案就是要在图2中找到从节点s1(3,3,1)到节点

'sk(3,3,0)的所有路径；问题转化为图论的求路径的问题，编程采用Dijkstra

算法可以求得。

5 结果分析

根据(1)~(7)式编写matlab程序（见附录1），用Dijkstra算法求得四组可行解，如下表所示：

表1

方案一 此岸 (3,3,1) (3,1,1) (3,2,1) (3,0,1) (3,1,1) (1,1,1) (2,2,1) (0,2,1) (0,3,1) (0,1,1) (0,2,1) 船上 (0,2) （0,1） （0,2） （0,1） （2,0） （1,1） （2,0） （0,1） （0,2） （0,1） （0,2） 表 2

方案二 彼岸 (0,2,0) （0,1,0） （0,3,0） （0,2,0） （2,2,0） （1,1,0） （3,1,0） （3,0,0） （3,2,0） （3,1,0） （3,3,0） 此岸 船上 彼岸 （3，3，1） （0，2） （0，0，0） （3，1，1） （0，1） （0，2，0） （3，2，1） （0，2） （0，1，0） （3，0，1） （0，1） （0，3，0） （3，1，1） （2，0） （0，2，0） （1，1，1） （1，1） （2，2，0） （2，2，1） （2，0） （1，1，0） （0，2，1） （0，1） （3，1，0） （0，3，1） （0，2） （3，0，0） （0，1，1） （1，0） （3，2，0） （1，1，1） （1，1） （2，2，0） 表 3

方案三 此岸 船上 彼岸 （3，3，1） （1，1） （0，0，0） （2，2，1） （1，0） （1，1，0） （3，2，1） （0，2） （0，1，0） （3，0，1） （0，1） （0，3，0） （3，1，1） （2，0） （0，2，0） （1，1，1） （1，1） （2，2，0） （2，2，1） （2，0） （1，1，0） （0，2，1） （0，1） （3，1，0） 表 4

方案四 此岸 船上 彼岸 （3，3，1） （1，1） （0，0，0） （2，2，1） （1，0） （1，1，0） （3，2，1） （0，2） （0，1，0） （3，0，1） （0，1） （0，3，0） （3，1，1） （2，0） （0，2，0） （1，1，1） （1，1） （2，2，0） （2，2，1） （2，0） （1，1，0） （0，2，1） （0，1） （3，1，0） （0，3，1） （0，2） （3，0，0） （0，3，1） （0，2） （3，0，0） （0，1，1） （0，1） （3，2，0） （0，1，1） （1，0） （3，2，0） （0，2，1） （0，2） （3，1，0） （1，1，1） （1，1） （2，2，0）

由结果可得，第一次渡船只能分两种情况，两个随从、一个商人一个随从。对表1进行分析如下：

去2随从 回1随从

（3商人3随从）此岸—————→（0商人2随从）彼岸—————→ 去2随从 回1随从

（3商人2随从）此岸—————→（0商人3随从）彼岸—————→ 去2商人 回1商人1随从

（3商人1随从）此岸—————→（2商人2随从）彼岸—————→ 去2商人 回1随从

（2商人2随从）此岸—————→（3商人1随从）彼岸—————→ 去2随从 回1随从

（0商人3随从）此岸—————→（3商人2随从）彼岸—————→ 去2随从

（0商人2随从）此岸—————→（3商人3随从）（渡河成功） 同理，表2、表3、表4也可得到渡河方案。

6 模型评价与改进

6.1 模型评价

本文通过合理的假设，巧妙的利用三维向量表示了商人、随从、船的状态，定义此岸允许状态集合、彼岸允许状态集合及决策变量集合，把此岸允许状态集合和彼岸允许状态集合的元素视为节点，这样把抽象的多步骤决策问题转化为图论的求从起始节点到最终节点的所有路径的问题简化了模型。当然模型也存在一些不足之处，如只考虑了3个商人和3个随从的问题，没有考虑跟多人数的情况，对此我们将在以后的模型改进部分加以完善。 6.2 模型改进

考虑m个商人m个随从，船的最大容量为n且nm，建立相应的模型给出m和n应该满足什么条件是才能保证商人安全渡河，使模型梗具有一般性。经过验证当m4,n2时商人无法安全到达彼岸，当m5,n3时商人能安全到达彼

岸，m5，n3时商人无法安全到达彼岸。 参考文献

[1]姜启源等.数学模型[M].北京：高等教育出版社，2003. [2]周义仓，郝孝量.数学建模实验[M]，西安：西安交通大学出版社，2007. [3]韩中庚.数学建模获奖论文精选与点评[M].北京：科学出版社，2007.

附录

clear clc n=3; nn=3; nnn=2;

for i=0:nnn

for j=0:nnn if (i+j<=nnn)&&(i+j>0) % 满足条D={(u,v)|1<=u+v<=nnn,u,v=0,1,2}

d(jc,1:3)=[i,j,1];%生成一个决策向量立刻扩充为三维； d(jc+1,1:3)=[-i,-j,-1]; % 同时生成他的负向量；

jc=jc+2; % 由于生成两个决策向量，则jc要向下移动两个； end end end kx=1;

for i=n:-1:0 for j=nn:-1:0

if ((i>=j)&&((n-i)>=(nn-j)))||((i==0)||(i==n)) A(kx,1:3)=[i,j,1]; A(kx+1,1:3)=[i,j,0];

kx=kx+2; end end end

k=(1/2)*size(A,1); CX=zeros(2*k,2*k); a=size(d,1);

for i=1:2*k for j=1:a

c=A(i,:)+d(j,:);

x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))); v(i,x)=1;

end end

% dijstra算法

x=1; y=size(A,1); m=size(v,1);

T=zeros(m,1); T=T.^-1;

lmd=T; P=T;

S=zeros(m,1); S(x)=1; P(x)=0; lmd(x)=0; k=x; while 1

a=find(S==0); aa=find(S==1);

if size(aa,1)==m break end

for j=1:size(a,1) pp=a(j,1); if v(k,pp)~=0

if T(pp)>P(k)+v(k,pp) T(pp)=P(k)+v(k,pp); lmd(pp)=k; end end end

mi=min(T(a));

if mi==inf break; else

d=find(T==mi); d=d(1); P(d)=mi;

T(d)=inf; k=d;

S(d)=1; end end

if lmd(y)==inf

jueche='can not reach'; return; end

jueche(1)=y; g=2; h=y;

while 1 if h==x break; end

jueche(g)=lmd(h); g=g+1; h=lmd(h); end

jueche=A(jueche,:); jueche(:,3)=[];