资源描述：
《商人过河问题培训讲学.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、精品好文档，推荐学习交流商人过河问题一、三名商人各带一名随从的情况1．问题（略）2．模型假设①当一边岸满足随从数大于商人数，但商人数为0时仍为一种安全状态；②小船至多可容纳2人，且渡河时由随从（或者商人）来划船。3．分析与建模商人过河需要一步一步实现，比如第一步：两个仆人过河，第二步：一个仆人驾船回来，第三步：又是两个仆人过河，第四步：……其中每一步都使当前状态发生变化，而且是从一种安全状态变为另一种安全状态。如果我们把每一种安全状态看成一个点，又如果存在某种过河方式使状态变到状态，则在点和点之间连一条边，这样我们把商人过河问题和图联系起来，有可能用图论方法来解决商人过河问题。建模步骤：⑴首先
2、要确定过河过程中的所有安全状态，我们用二元数组表示一个安全状态（不管此岸还是彼岸），其中x表示留在此岸的主人数，表示留在此岸的随从数。两岸各有十种安全状态：⑵在两岸的安全状态之间，如存在一种渡河方法能使一种状态变为另一种安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图1），其中下方顶点表示此岸状态，上方顶点表示彼岸状态。我们的目的是要找出一条从此岸到彼岸的最短路。⑶观察发现此岸的状态，和彼岸的状态，都是孤立点，在求最短路的过程中不涉及这些点，把它们删去。两岸的点用1,2,……，16重新标号。（3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,
3、3）（0,0）○②④⑥⑧⑩○①③⑤○⑦⑨○（3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0）(图1)仅供学习与交流，如有侵权请联系网站删除谢谢7精品好文档，推荐学习交流1．模型求解求最短路程的matlab程序sroute.m如下：functionroute=sroute(G,opt)%求图的最短路的Dijkstra算法程序，规定起点为1，顶点连续编号%G是给定图的邻接矩阵或弧表矩阵，程序能够自动识别%当opt=0（或缺省）时求无向图的最短路，当opt=1时求有向图的最短路%d——标记最短距离%route是一个矩阵，第一行标记顶点，第二行标记1到
4、该点的最短路，第三行标记最短路上该点的先驱顶点while1%此循环自动识别或由弧表矩阵生成邻接矩阵ifG(1,1)==0A=G;breakelsee=Gn=max([e(:,1);e(:,2)]);%顶点数m=size(e,1);%边数M=sum(e(:,3));%代表无穷大A=M*ones(n,n);fork=1:mA(e(k,1),e(k,2))=e(k,3);ifopt==0A(e(k,2),e(k,1))=e(k,3);%形成无向图的邻接矩阵endendA=A-M*eye(n)%形成图的邻接矩阵endbreakendpb(1:length(A))=0;pb(1)=1;index1=1;
5、index2=ones(1,length(A));d(1:length(A))=M;d(1)=0;%标记距离temp=1;whilesum(pb)=2in
6、dex=index(1);end仅供学习与交流，如有侵权请联系网站删除谢谢7精品好文档，推荐学习交流index2(temp)=index;%记录前驱顶点endroute=[1:n;d;index2];在matlab的命令窗口输入图（1）的弧表矩阵e:e=[12;14;110;34;36;310;56;58;714;716;98;912;1112;1114;1314;1316;1516];e=[e,ones(17,1)];%边权都设为1调用程序sroute.m：route=sroute(e,0)运行结果：e=12114111013413613101561581714171619819121111
7、2111141131411316115161route=1234567891011121314151601214310561871091211114163145811291411167这表示存在一条从1到16的长度为11的路：1436589121114716，此路对应商人成功渡河的一个方案：仅供学习与交流，如有侵权请联系网站删除谢谢7精品好文档，推荐学习交流（3,3）变为（3,1）变为（3,2）变
