人狼羊菜渡河問題(含Matlab程序)人狼羊菜渡河問題(含Matlab程序)人狼羊菜渡河問題(含Matlab程序)人狼羊菜渡河問題(含Matlab程序)編制僅供參考審核批準生效日期地址：電話：傳真:郵編:人、狼、羊、菜安全渡河問題安全渡河問題又稱作“人狼羊菜”問題，其具體描述為：一個人帶著一條狼、一只羊、一筐白菜過河但由于船太小，人一次只能帶一樣東西乘船過河。狼和羊、羊和白菜不能單獨留在同岸，否則羊或白菜會被吃掉。該問題可使用圖論中的最短路算法進行求解。問題分析根據題意，人不在場時，狼要吃羊，羊要吃菜，因此，人不在場時，不能將狼與羊、羊與菜留在河的任一岸。可用四維向量v=（m，n，p，q）來表示狀態，m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,q∈{0,1},0代表在對岸，1代表在此岸。例如，狀態（0,1,1,0）表示人和菜在對岸，而狼和羊在此岸，這時人不在場，狼要吃羊，因此，這個狀態是不可行的。通過窮舉法將所有可行的狀態列舉出來，可行的狀態有（1,1,1,1）,（1,1,1,0）,（1,1,0,1）,（1,0,1,1）,（1,0,1,0）,（0,1,0,1）,（0,1,0,0）,（0,0,1,0）,（0,0,0,1）,（0,0,0,0）。可行狀態共有十種。每一次的渡河行為改變現有的狀態。現構造賦權圖G=(V,E,W),其中頂點集V={v1,…,v10}中的頂點（按照上面的順序編號）分別表示上述１０個可行狀態，當且僅當對應的兩個可行狀態之間存在一個可行轉移時兩頂點之間才有邊連接，并且對應的權重取為１，當兩個頂點之間不存在可行轉移時，可以把相應的權重取為∞。因此問題變為在圖Ｇ中尋找一條由初始狀態（１,１,１,１）出發，經最小次數轉移到達最終狀態（０,０,０,０）的轉移過程，即求從狀態（１,１,１,１）到狀態（０,０,０,０）的最短路徑。該問題難點在于計算鄰接矩陣，由于擺渡一次就改變現有狀態，為此再引入一個四維狀態轉移向量，用它來反映擺渡情況。用１表示過河，０表示未過河。例如，（１,１,０,０）表示人帶狼過河。狀態轉移只有四種情況，用如下向量表示：（１,０,０,０），（１,１,０,０），（１,０,１,０），（１,０,０,１）現在規定狀態向量與轉移向量之間的運算為0+0=0,1+0=1,0+1=1,1+1=0通過上面的定義，如果某一個可行狀態加上轉移向量得到的新向量還屬于可行狀態，則這兩個可行狀態對應的頂點之間就存在一條邊。用計算機編程時，可以利用普通向量的異或運算實現，具體的Matlab程序如下：clc,cleara=[1111;1110;1101;1011;1010;0101;0100;0010;0001;0000];%每一行是一個可行狀態b=[1000;1100;1010;1001];%每一行是一個轉移狀態w=zeros(10);%鄰接矩陣初始化fori=1:9forj=i+1:10fork=1:4iffindstr(xor(a(i,:),b(k,:)),a(j,:))w(i,j)=1;endendendendw=w，；%變成下三角矩陣c=sparse(w);%構造稀疏矩陣［x,y,z］=graphshortestpath(c,1,10,’Directed’,0)%該圖是無向圖，Directed屬性值為0h=view(biograph(c,[],’ShowArrows’,’off’,’ShowWeights’,’off’));%畫出無向圖Edges=getedgesbynodeid(h);%提取句柄ｈ中的邊集set(Edges,’LineColor’,[000];%為例將來打印清除，邊畫成黑色set(Edges,’LineWidth’,;%線型寬度設置為賦權圖Ｇ之間的狀態轉移關系如下圖所示：圖可行狀態之間的轉移最終求得的狀態轉移順序之一為：63728510對應方案為：經過7次渡河就可以把狼、羊、蔬菜運過河，第一次運羊過河，空船返回；第二次運菜過河，帶羊返回；第三次運狼過河，空船返回；第四次運羊過河。另一種方案同理可由圖得，請讀者自行寫出。參考文獻[1]司守奎,孫璽菁.數