商人过河问题.doc

商人过河问题一、三名商人各带一名随从的情况 1. 问题(略) 2. 模型假设 1当一边岸满足随从数大于商人数,但商人数为 0时仍为一种安全状态; 2小船至多可容纳 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 程序 如下: 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; in