商人过河问题.docx

商人过河问题
一、三名商人各带一名随从的情况
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)
O ② ④ ⑥ ⑧ ⑩ O ⑫ ⑭ O
① ③ ⑤ O ⑦ ⑨ ⑪ O 迤 O
(3,3) (3,2) (3,1) (3,0) (1,1) (2,2) (0,3) (0,2) (0,3) (0,0)
(图 1)
4． 模型求解
求最短路程的 matlab 程序 sroute、m 如下 :
function route=sroute(G,opt)
%求图的最短路的 Dijkstra 算法程序 ,规定起点为 1, 顶点连续编号
%(就是给定图的邻接矩阵或弧表矩阵 ，程序能够自动识别
%当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