商人过河问题

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

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

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)O O OOOGO(3,3)(3,2)(3,1)(3,0)(1,1)(2,2)(0,3)(0,2)(0,3)(0,0)(图1)4模型求解求最短路程的matlab程序如下：function route=sroute(G, opt)%求图的最短路的Dijkstra算法程序，规定起点为1,顶点连续编号%G是给定图的邻接矩阵或弧表矩阵，程序能够自动识别%当。20 (或缺省)时求无向图的最短路，当

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

5、(n)endbreakendpb (1: length (A)=0;pb (1) =1;%形成图的邻接矩阵indcxl=l; index2=ones(1, length(A);d (1: length (A)=M;d (1) =0; temp=l;%标记距离while sum(pb)=2index二index；end%记录前驱顶点index2(temp)=index;endroute=1:n;d;index2;在matlab的命令窗口输入图(1)的弧表矩阵e:e=l 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;

6、13 14;13 16;15 16;e=e, ones(17,1);%边权都设为 1调用程序： route=sroute(e, 0)运行结果：e =121141110134136131015615817141716198191211112111141131411316115161route =1234567891011 121314151601214310561871091211114163145811291411167这表示存在一条从1到16的长度为11的路：14 3 6 51211 14 7 16,此路对应商人成功渡河的一个方案:(3,3)变为(3,1)变为(3,2)变为(3,0)变为(3

7、,1)变为(1,1) 变为(2,2)变为(0,2)变为(0,3)变为(0,1)变为(1,1)变为(0,0)即：两个仆人过河，一个仆人回来；有两个仆人过河，一个仆人回来；两 个主人过河，一主一仆回来；有两个主人过河，一个仆人回来；两个仆人过河, 一个仆人回来；最后两个仆人过河。这样，商人安全过河。若把刚才的最短路上的边权全部改大，如取2或3,重新运行程序，得到同 样的结果，但实际上还有另外一种安全渡河状态：(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.图解法

8、将十种安全状态的点在直角坐标系中标出，如下图(0,0), (0,1), (0,2), (0,3), (2,2), (1,1), (3,0), (3,1), (3,2), (3,3) (实线表示才此岸开往彼岸，虚线表示才彼岸开往此岸)Sti图中4到右给出了商人安全渡河的一条路径。二、四名商人各带一名随从1问题：四名商人各带一名随从时，就附加说明条件才能实现安全渡河。2.原模型求解改编程序重新运行，或用递归的方法程序运行，结果运行出现错误或死机, 这说明模型无解，即四名商人各带一名随从在原条件下无安全状态渡河。所以我们需附加一定的条件，使模型有解。由第一问中的条件可知：商人 渡河的限制条件是在任何

9、一边岸商人数一定要比随从数多且小船最多只能载2 人，而安全状态(即商人数比随从数多)是最其本的前提条件，因此我们考虑 更改小船的容量来实现安全渡河。3.新模型及求解当小船的容量为5或大于5时，显然一种安全渡河方式为：先4名随从渡 河，1名随从回来；随后4名商人与回来的那名随从一起渡河。当小船容量为4 时，一种渡河方案为：先4名随从渡河，1名随从回来；再3名商人渡河，1名 商人和1名随从回来；最后2名商人和2名随从一起渡河。现在我们考虑小船容量为3时的情况：（在这我们用图解法来完成） 9步渡河方案（如图所示）：01234图即：第一步先三名随从过河，一名随从回来；再两名商人过河，一名商人 和一名随从回来；再三名商人过河，一名随从回来；再三名随从过河，一名随 从回来；最后两名随从过河。 11步度河方案（如图所示）:01234x图即：第一步先一名商人和一名随从过河，一名商人回来；再三名随从过河, 一名随从回来；再三名商人过河，一名商人和一名随从回来；再两名商人过河, 一名随从回来；最后