商人过河问题

1、商人过河问题一、三名商人各带一名随从的情况1 问题(略)2. 模型假设 当一边岸满足随从数大于商人数,但商人数为0时仍为一种平安状态； 小船至多可容纳2人,且渡河时由随从(或者商人)来划船.3. 分析与建模商人过河需要一步一步实现,比方第一步：两个仆人过河,第二步：一个仆 人驾船回来,第三步：又是两个仆人过河,第四步：其中每一步都使当前状态发生变化,而且是从一种平安状态变为另一种平安 状态.如果我们把每一种平安状态看成一个点,又如果存在某种过河方式使状态 a变到状态b,那么在点a和点b之间连一条边,这样我们把商人过河问题和图联 系起来,有可能用图论方法来解决商人过河问题.建模步骤：首先要确定过

2、河过程中的所有平安状态,我们用二元数组(x,y) 表示一个平安状态(不管此岸还是此岸),其中x表示留在此岸的主人数,y表 示留在此岸的随从数.两岸各有十种平安状态：(0,0),(0,1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3) U在两岸的平安状态之间,如存在一种渡河方法能使一种状态变为另一种安 全状态,那么在这两种状态之间连一条边.这样,得到如下一个二部图(图 1 ), 其中下方顶点表示此岸状态,上方顶点表示此岸状态.我们的目的是要找出一条 从此岸(3,3)到此岸(0,0)的最短路.观察发现此岸的状态(0,0),(3,0)和此岸的状态(0

3、,3),(3,3)都是孤立点,16 重在求最短路的过程中不涉及这些点,把它们删去.两岸的点用 1,2, 新标号.3,3)3,23,13,01,12,20,30,20,3 0,0oo1o21o41o6o1o11o31o5o3,3)3,23,13,01,1 2,2 0,3 0,20,3 0,0(图 1)4 模型求解求最短路程的 matlab 程序sroute.m 如下：function route=sroute(G,opt) % 求图的最短路的 Dijkstra 算法程序,规定起点为 1,顶点连续编号 %G 是给定图的邻接矩阵或弧表矩阵,程序能够自动识别%当 opt=0 或缺省时求无向图的最短路,

4、当opt=1 时求有向图的最短路%d 标记最短距离%route 是一个矩阵,第一行标记顶点,第二行标记 1 到该点的最短路,第三行标记最短路上该点的先驱顶点while 1%此循环自动识别或由弧表矩阵生成邻接矩阵if G(1,1)=0A=G;breakelse-可编辑修改 -e=G-可编辑修改 -n=max(e(:,1);e(:,2);m=size(e,1);M=sum(e(:,3);A=M*ones(n,n);for k=1:mA(e(k,1),e(k,2)=e(k,3);if opt=0A(e(k,2),e(k,1)=e(k,3);% 顶点数%边数%代表无穷大%形成无向图的邻接矩阵enden

5、dA=A-M*eye(n)endbreakendpb(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)<length(A) tb=find(pb=0);%形成图的邻接矩阵%标记距离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)

6、;if length(index)>=2index=index(1);endindex2(temp)=index;%记录前驱顶点endroute=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;1314;13 16;15 16;e=e,ones(17,1);% 边权都设为 1调用程序 sroute.m ：route=sroute(e,0)运行结果：214110141611016181141161811211211411

7、411611611113335577991111131315 route =-可编辑修改 -1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1601214310561871091211114163145811291411167这表示存在一条从 1 到 16 的长度为 11 的路： 1 4 3 6 5 8 912 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即：两个仆人过河,一个仆人回来；有两个仆人过河,一个仆人回来；两个主人过河,一

8、主一仆回来；有两个主人过河,一个仆人回来；两个仆人过河,一个仆人回来；最后两个仆人过河.这样,商人平安过河.假设把刚刚的最短路上的边权全部改大, 如取 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,05 图解法将十种平安状态的点在直角坐标系中标出,如下列图0,0,0,1,0,2,0,3,2,2,1,1,3,0,3,1,3,2,3,3实线表示才此岸开往此岸,虚线表示才此岸开往此岸Sn+1图中di到du给出了商人平安渡河的一条路径.二、

9、四名商人各带一名随从1问题：四名商人各带一名随从时,就附加说明条件才能实现平安渡河.2. 原模型求解改编程序sroute.m重新运行,或用递归的方法程序运行,结果运行出现错 误或死机,这说明模型无解,即四名商人各带一名随从在原条件下无平安状态渡 河.所以我们需附加一定的条件,使模型有解.由第一问中的条件可知：商人渡河的限制条件是在任何一边岸商人数一定要比随从数多且小船最多只能载2人,而平安状态即商人数比随从数多是最其本的前提条件,因此我们考虑更改小 船的容量来实现平安渡河.3. 新模型及求解当小船的容量为5或大于5时,显然一种平安渡河方式为：先4名随从渡河, 1名随从回来；随后4名商人与回来的

10、那名随从一起渡河.当小船容量为4时, 一种渡河方案为：先4名随从渡河,1名随从回来；再3名商人渡河,1名商人 和1名随从回来；最后2名商人和2名随从一起渡河.现在我们考虑小船容量为3时的情况：在这我们用图解法来完成01234x图即：第一步先三名随从过河,一名随从回来；再两名商人过河,一名商人和一名 随从回来；再三名商人过河,一名随从回来；再三名随从过河,一名随从回来； 最后两名随从过河.11步度河方案如图所示：图即：第一步先一名商人和一名随从过河,一名商人回来；再三名随从过河,一名 随从回来；再三名商人过河,一名商人和一名随从回来；再两名商人过河,一名 随从回来；最后三名随从一起过河.13步渡河方案如图所示：01234x图-可编辑修改-即：第一步先一