最新商人过河matlab程序以及解析

重庆大学

（商仆过河模型）

开课课程：数学模型 指导教师：黄光辉

小组成员：庄楚斌（20134760）自动化07班

张俊铭（20133227）材料加工01班 吴慧（20131966）数学01班

时间：2015年3月8日

精品文档

精品文档

一、问题提出

3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？

二、问题分析

商人与随从过河问题可以视为是一个多步决策的过程，通过多次

优化，从而得到一个全局最优的决策方案。决策的每一步，即船从此岸到达彼岸，都要对船上的商人和仆人数做出决策。在保证河的任一岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下，经有限步使所有人员到达彼岸。

三、模型假设

商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，

可以保证很多次安全的运载商人和随从。

四、模型建立

xk~第k次渡河前此岸的商人数，yk~第k次渡河前此岸的随从数

xk, yk=0,1,2,3; k=1,2,… …

Sk=(xk, yk, ck )~过程的状态，其中xk, yk, ck 分别表示对应时刻此

精品文档

精品文档

岸的商人，仆人数以及船的行进方向，其中c取值1表示即将向彼岸运行，为0表示即将向此岸运行

S ~ 允许状态集合，S={(x , y)| x=0, y=0,1,2,3; x=3 ,y=0,1,2,3; x=y=1,2}

uk~第k次渡船上的商人数 vk~第k次渡船上的随从数

dk=(uk, vk)~决策，D={(u , v)| 1uv2,uk, vk=0,1,2} ~允许决策集

合

k=1,2,… …

因为k为奇数时船从此岸驶向彼岸，k为偶数时船从彼岸驶向此岸，所以状态Sk随决策dk的变化规律是

Sk1=Sk+(1)kdk~状态转移律

求dk∈D(k=1,2, …n), 使Sk∈S, 并按转移律由S1=(3,3,1)到达状态Sn1=(0,0,0(1))。

精品文档

精品文档

五、模型求解

本模型使用MATLAB软件编程， 通过穷举法获得所有可能的决策方案如下(完整matlab程序详见附录):

第一种： 第二种：

第三种： 精品文档

第四种：

精品文档

六、模型的推广

该商人、随从过河模型可以完美解决此类商仆过河的决策问题，并且该模型还可推广至解决m个商人和n个随从过河，以及小船的最大载重人数改变时的问题，只需适当地改变相关的语句即可轻松实现模型的转换。

如当商人数和随从数均为4，小船最大载重人数为2时，matlab程序运行的结果如下(程序改动详见附录):

推广过程只需要将其中的 (x,y)（限定范围）改成相对应的情况即可，例如，商人基于仆人数都为4时允许状态集合，S={(x , y)| x=0, y=0,1,2,3,4; x=4 ,y=0,1,2,3,4; x=y=1,2,3}

精品文档

精品文档

总结

本程序相对于网上各种结构体，堆栈形式的程序来说简单很多，没有用到那些高级的函数，简单易懂, 核心要点:

（1）就是巧妙地将z(a,b)加上了c变成(a,b,c),c用来判断此时船的行进方向，在后面判断是否有重复时非常重要，因为在船行进方向不同时，就算此岸人员分布一样也不是一种情况

（2）就是设置了m数组，以便于在后面的穷举过程中，记录每一步所采用的决策方案，以防止后面重复或者遗漏

（3）成功找出所有可能的情况，相对于网络上只能找出一种有效情况来说是个巨大的进步，这得益于其中while函数的使用，回溯思想的建立，以及每次找到成功的路线之后，在将路线输出之后，以未成功的方式继续穷举，向下运行到找到第二条成功路线以及更多的方案到所有的可能进程都被检验为止。

精品文档

精品文档

附录

Matlab源代码

1、三个商人三个随从

%businessman_3b_3s.m ——商人过河MATLAB程序，3商人，3仆人

%本程序相对于网上各种结构体，堆栈形式的程序来说简单很多，没有用到那些高级的函数，简单易懂 %核心要点（1）就是巧妙地将z(a,b)加上了c变成(a,b,c),c用来判断此时船的行进方向，在后面判断是否有重复时非常重要，因为在船行进方向不同时，就算此岸人员分布一样也不是一种情况

%核心要点（2）就是设置了m数组，以便于在后面的穷举过程中，记录每一步所采用的决策方案，以防止后面重复或者遗漏

%核心要点（3）成功找出所有可能的情况，相对于网络上只能找出一种有效情况来说是个巨大的进步

z=zeros(30,3); %z为由(a,b,c)的列向量组成的3行30列数组，初始化为0矩阵，a,b,c代表此刻此岸的商人，仆人数量以及船的运行状态，c=1表示即将向彼岸运行

m=zeros(1,20); %m为一维行向量，初始化为1矩阵，用于在后面的程序中判断第k次选择的乘船方案

d=[0,1,1;0,2,1;1,0,1;1,1,1;2,0,1]; %共有5种可以选择的乘船方案，最后面一列全为1，即用于在后面表示使得z(k,3)的取值保持随着k的奇偶性保持着0-1变换.

z(1,:)=[3,3,1]; %初始状态为[3,3,1] k=1;

m(k)=1; %第一次默认的乘船方案为决策1——d(1)

flag=1; %用于在后面判断是否成功找到方案 answer=0; %用于在后面判断是否找到答案 while k>0 %保持k>0 if m(k)>5 flag=0; break; end p=0;

z(k+1,:)=z(k,:)+(-1)^k*d(m(k),:); %每一次的运算规则都是z(k+1)=z(k)-(-1)^k*d(m(k),:),d(m(k),:)表示决策方案

a=z(k+1,1); %将当前情况的矩阵数值复制给a商人,b仆人

b=z(k+1,2); c=z(k+1,3); if

精品文档

精品文档

(a==3&&(b==0||b==1||b==2||b==3))||(a==1&&b==1)||(a==2&&b==2)||(a==0&&(b==0||b==1||b==2||b==3)) %判断(a,b)是否符合限定情况 for j=1:k %判断是否此岸a,b,c与之前有重复，如果是，结束此次循环，重新选择乘船方案

if a==z(j,1)&&b==z(j,2)&&c==z(j,3) if m(k)~=5 %决策方案只有5种，所以m(k)<=5， m(k)=m(k)+1; %因为有重复，所以换下一种决策方案

else while (m(k)==5)&&(k>1)

k=k-1; %回溯，这一步骤已经把所有决策取尽，无可用解法，于是将后退一步，同时换下一种决策方案

end %while循环的目的是防止前面几步的决策都是5，导致k=k-1,m(k)=m(k)+1后数组越界，一直找到前面不是m(k)=5的步骤

m(k)=m(k)+1; end p=1; break; else

p=0; end end

if p==1 %程序在跳出内层for循环之后，因为要换成决策方案，所以同时跳出，直接进入下一次while循环， continue; end

if a==0&&b==0 %判断是否达到目标情况 answer=1;

fprintf('Successfully found!\\n每一次的此岸人员分布：商人 仆人\\n')

for i=1:100

fprintf(' 第%2d次 %d %d \\n',i,z(i,1),z(i,2))

if z(i,1)==0&&z(i,2)==0 break; end

end %如果不是，进入下一步骤，计算z(k+2) if m(k)~=5

m(k)=m(k)+1; %这是正常的进入下一次，所以仍从d1乘船决策1开始 else

while (m(k)==5)&&(k>1) k=k-1;

精品文档

精品文档

end;

m(k)=m(k)+1; end

continue;

else

k=k+1; %如果不是，进入下一步骤，计算z(k+2)

m(k)=1; %这是正常的进入下一次，所以仍从d1乘船决策1开始

continue;

end else

if m(k)~=5

m(k)=m(k)+1; %如果没有符合限定情况，结束该次循环，改变上一次的乘船方案

else

while (m(k)==5)&&(k>1)

k=k-1; end

m(k)=m(k)+1; %回溯，这一步骤已经把所有决策取尽，无可用解法，于是将后退一步，同时换下一种决策方案

continue; end end end

if answer==0&&flag==0

fprintf(' No Answer!\\n') end

2、模型推广——4个商人和4个随从

只需将将上面程序中判断(a,b)是否符合限定情况的条件改为

if

精品文档

精品文档

(a==4&&(b==0||b==1||b==2||b==3||b==4))||(a==1&&b==1)||(a==2&&b==2)||(a==3&&b==3)||(a==0&&(b==0||b==1||b==2||b==3||b==4))

其它保持不变，运行即可得到想要的答案。

精品文档