商人过河问题

别妄想泡我
537次浏览
2021年02月23日 09:19
最佳经验
本文由作者推荐

-

2021年2月23日发(作者:美丽说刷心)


商人过河问题



一、三名商人各带一名随从的情况



1


.



问题(略)



2


.



模型假设



①



当一边岸满足随从数大于商人数,但商人数为


0


时仍为一种安全状态;



②



小船至多可容纳


2


人,且渡河时由随从 (或者商人)来划船。



3


.



分析与建模



商人过河需要一步一步实 现,比如第一步:两个仆人过河,第二步:一个仆


人驾船回来,第三步:又是两个仆人过 河,第四步:……



其中每一步都使当前状态发生变化,


而且是从一种安全状态变为另一种安全


状态。


如果我们把每一种安全状态看成一个点,


又如果存在某种过河方式使状态


a


变到状态


b


,则在点


a


和点


b


之间连一条 边,这样我们把商人过河问题和图联


系起来,有可能用图论方法来解决商人过河问题。< /p>



建模步骤:


⑪首先要确定过河过程中的 所有安全状态,


我们用二元数组


(


x< /p>


,


y


)


表示一个 安全状态(不管此岸还是彼岸)


,其中


x


表示留在此岸的主人数,


y


表


示留在 此岸的随从数。两岸各有十种安全状态:



(0,0),(0, 1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3)



⑫在两岸的安全状态之间,


如存在一 种渡河方法能使一种状态变为另一种安


全状态,则在这两种状态之间连一条边。这样,得 到如下一个二部图(图


1


)


,


其中下方顶点表示此岸状态,


上方顶点表示彼岸状态。

< br>我们的目的是要找出一条


从此岸


(3,3)


到彼岸


(0,0)


的最短路。



⑬观察发现此岸的状态


(0,0)


,


(3,0)


和彼岸的状态


(0,3)


,


(3,3)


都是孤立点,

< p>
在求最短路的过程中不涉及这些点,


把它们删去。


两岸的点用


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


程序


sroute.m


如下:



function


route=sroute(G,opt)


%


求图的最短路的


Dijkstra


算法程序,规定起点为


1


,顶点连续编号



%G

< p>
是给定图的邻接矩阵或弧表矩阵,程序能够自动识别


%


当


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;



index1=1;



index2=ones(1,length(A));



d(1:length(A))=M;d(1)=0; %


标记距离



temp=1;



while


sum(pb)



tb=find(pb==0);



d(tb)=min(d(tb),d(temp)+A(temp,tb)); %


更新距离



temp=find(d(tb)==min(d(tb))); %


确定新最小距离点



temp=tb(temp(1));



pb(temp)=1;



index1=[index1,temp];



in dex=index1(find(d(index1)==d(temp)-A(temp,index1)) );




if


length(index)>=2



index=index(1);




end



index2(temp)=index; %


记录前驱顶点



end



route=[1:n;d;index2];




在


matlab

的命令窗口输入图(


1


)的弧表矩阵


e:


e=[1


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;13


14;13


16;15 16];


e=[e,ones(17,1)];








%


边权都设为


1



调用程序


sroute.m


:



route=sroute(e,0)



运行结果:




e =








1






2






1







1






4






1







1





10






1







3






4






1







3






6






1







3





10






1







5






6






1







5






8






1







7





14






1







7





16






1







9






8






1







9





12






1






11





12






1






11





14






1






13





14






1






13





16






1






15





16






1


route =



1




2




3




4




5




6




7




8




9



10



11



12



13



14



15



16


0




1




2




1




4




3



10




5




6




1




8




7



10




9



12




11


1




1




4




1




6




3



14




5




8




1



12




9



14



11



16




7







这表示存在一条从


1


到

16


的长度为


11


的路:


1



4



3



6



5



8



9




12




11



14



7



16


,此路对应商人成功渡河的一个方案:



(


3,3

)变为(


3,1


)变为(


3,2< /p>


)变为(


3,0


)变为(


3,1


)变为(


1,1


)变为 (


2,2


)


变为(

0,2


)变为(


0,3


)变为(< /p>


0,1


)变为(


1,1

< br>)变为(


0,0


)




即:两个仆人过河,一个仆人回来;有两个仆人过河,一个仆 人回来;两个主人


过河,一主一仆回来;有两个主人过河,一个仆人回来;两个仆人过河 ,一个仆

-


-


-


-


-


-


-


-