商人过河问题一、三名商人各带一名随从的情况1． 问题（略）2． 模型假设① 当一边岸满足随从数大于商人数，但商人数为0 时仍为一种安全状态；② 小船至多可容纳 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)n⑵在两岸的安全状态之间， 如存在一种渡河方法能使一种状态变为另一种安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图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;breakelse e=G n=max([e(:,1);e(:,2)]...
