農(nóng)夫攜物過河程序

1、題目內(nèi)容：有一農(nóng)夫要將自己的羊、蔬菜和狼等3件物品運過河。但農(nóng)夫過河時所用的船每 次最多只能裝英中的一件物品，而這3件物品之間又存在一左的制約關系：羊不能單獨和狼 以及不能和蔬菜在一起，因為狼要吃羊，羊也能吃蔬菜。試構造出問題模式以編程實現(xiàn)這一 問題的求解。1、問題分析和任務定義：根據(jù)對象的狀態(tài)分為過河（1）和不過河（0）,此對象集合就構成了一個狀態(tài)空間。問 題就是在這個狀態(tài)空間內(nèi)搜索一條從開始狀態(tài)到結束狀態(tài)的安全路徑。顯然，其初始狀態(tài)為 四對象都不過河，結束狀態(tài)為四對象全部過河。這里用無向圖來處理，并采用鄰接矩陣存儲。 對于農(nóng)夫，狼，羊，蔬菜組成一個4位向量，即圖的頂點（F,叭S, V）,狀

2、態(tài)空間為16, 初始狀態(tài)為（0000）,目標為（1111）。解決問題的方法是，找到所有的安全狀態(tài)，并在其 中搜索岀一條（0000）到（1111）的路徑。對當前對象是否安全的判斷，若當農(nóng)夫與羊不在 一起時，狼與羊或羊與蔬菜在一起是不安全的，英他情況是安全的。搜索一條可行路徑時， 采用深度優(yōu)先搜索DFS_path,每個時刻探索一條路徑，并記錄訪問過的合法狀態(tài)，一直向 前探視，直到疋不通時回溯。顯然，應該用數(shù)組來保存訪問過的狀態(tài)，以便回溯。顯然農(nóng)夫 每次狀態(tài)都在改變，最多也就能帶一件東西過河，故搜索條件是，在頂點（F, W, S, V）的 轉換中，狼，羊，蔬菜三者的狀態(tài)不能大于一個，即只有一個發(fā)生改

3、變或者都不變。 數(shù)拯的輸入形式和輸入值的范用：本程序不需要輸入數(shù)據(jù)，故不存在輸入形式和輸入值的范用。 結果的輸出形式：在屏幕上顯示安全狀態(tài)的轉換，即一條安全路徑。2、數(shù)據(jù)結構的選擇概要設計數(shù)據(jù)結構的選擇：本程序采用無向圖處理。#define MaxNumVertices 10 /最大頂點數(shù)typedef struct /圖的頂點類型int Farmer, Wolf, Sheep, Veget; /存儲農(nóng)夫，狼，羊，蔬菜的狀態(tài)VexType;typedef struct/圖的各項信息VexType VerticesList LMaxNumVertices;/頂點向量(代表頂點)int Edge

4、MaxNumVertices MaxNumVertices;/鄰接矩陣/用于存儲圖中的邊，苴矩陣元素個數(shù)取決于頂點個數(shù)，與邊數(shù)無關AdjGraph;為了實現(xiàn)上述程序的功能，需要：生成所有安全的圖的頂點：査找頂點的位 置：判斷目前(F, W. S, V)是否安全，安全返回1,否則返回0：判斷頂點i和 頂點j之間是否可轉換，可轉換返回真，否則假：深度優(yōu)先搜索從u到v的簡單路徑; 輸出從u到v的簡單路徑，即頂點序列中不重復出現(xiàn)的路徑。本程序包含7個函數(shù)： 主函數(shù)main () 生成所有安全的圖的頂點函數(shù)CreateG () 査找頂點位置函數(shù)locate () 判斷目前狀態(tài)(F, W, S, V)是否

5、安全的函數(shù)is.safe () 判斷頂點i和頂點j之間是否可轉換的函數(shù)is_connected () 深度優(yōu)先搜索從u到v的簡單路徑的函數(shù)DFS_path 輸出從u到v的簡單路徑，即頂點序列中不重復岀現(xiàn)的路徑print_path ()各函數(shù)關系如下:圖1各函數(shù)關系圖3、詳細設計和編碼實現(xiàn)概要設計中左義的所有數(shù)據(jù)類型，對每個操作作出偽碼算法。數(shù)據(jù)結構define MaxNumVertices 10 /最大頂點數(shù)typedef struct /圖的頂點類型int Farmer, Wolf, Sheep, Veget;VexType;typedef structint Vert exNum, Cur

6、rentEdges;/圖的當前頂點數(shù)和邊數(shù)VexType VerticesList MaxNumVerticesl;/頂點向量（代表頂點）int EdgeMaxNumVertices MaxNumVertices;/鄰接矩陣/用于存儲圖中的邊，其矩陣元素個數(shù)取決于頂點個數(shù)，與邊數(shù)無關AdjGraph;圖的基本操作1. 査找頂點(F, W, S, V)在圖中的位宜int locate (AdjGraph *G, int F, int W, int S, int V)int i;for(i=0;iVertexNum;i+)if(G-VerticesListi. Farmer二二F & G-Vert

7、icesListi. Wolf=W &G-VerticesList i. SheepS & G-VerticesList iL Veget=V)return(i) ;/返回當前位置return (-1); 沒有找到此頂點2. 判斷目前的(F, W, S, V)是否安全當農(nóng)夫與羊不在一起時，狼與羊或羊與白菜在一起是不安全的，否則安全int is_safe(int F, int W, int S, int V)if(F!=S& (W=S S=V)return (0);/不安全返回0elsereturn (1);/安全返回 13. 判斷狀態(tài)i與狀態(tài)j之間是否可轉換顯然每次轉換農(nóng)夫都在移動，而農(nóng)夫移動

8、時最多只能攜帶一個物件，故每次狀態(tài)轉 換，其他3件只能有一件移動或都不移動，能轉換時返回1,不能轉換時返回0,代碼 如下：int is_connected(AdjGraph *G, int i, int j)int k=0;k+;if(G-VerticesListi Sheep!=G-VerticesListj Sheep)k+;if(G-VerticesListli Veget!=G-VerticesListj Veget)k+;if(G-VerticesList Fanner!二G-VerticesListj Farmer & kEdgeij=G-Edgej i=l; 即初始化鄰接矩陣。v

9、oid CreateG(AdjGraph*G)int i, j, F,W,S,V;i 二0;for (F二0: F=1; F+)/生成所有安全的圖的頂點for(W=0;W=l;W+)/因為只有0和1倆個狀態(tài)故循環(huán)都時從0開始1結束for(S=0;S=l;S+)for(V=0;VVerticesList Li Farmer二F;G-VerticesListi.Wolf=W;G-VerticesList Li Sheep二S;G-VerticesList Li Veget二V;i+;/統(tǒng)計安全頂點個數(shù)G-VertexNum=i;for(i=0;iVertexNum; i+) 鄰接矩陣初始化即建立鄰

10、接矩陣for (jO; jVertexNum; j+)if(is_connected(G, i, j)/狀態(tài)i與狀態(tài)j之間可轉化，初始化為1,否則為0G-Edgei j=G-EdgejelseG-Edgeij=G-Edgeji=O;return;5. 深度優(yōu)先搜索u到v的簡單路徑深度優(yōu)先：每個時刻探索一條路徑，并記錄訪問過的合法狀態(tài)，一直向前探視，直 到走不通時回溯。顯然，應該用堆棧來保存訪問過的狀態(tài)，以便回溯。具體分析如下： 首先訪問u,并標記； 訪問下一個與u可轉換的頂點vl,并標記，將vl存儲起來： 再從vl開始，選取下一個可以與vl轉換的頂點v2訪問，標記，并存儲； 重復直到某頂點vi

11、沒有可以轉換的頂點，此時退后一步查找vi-1可有可以轉換的 頂點： 以上任何時刻訪問到了 V即停止，直至到V。詳細代碼如下:void DFS_path(AdjGraph *G, int u, int v)int j;vis i ted u二TRUE; /標記已訪問過的頂點for(j=0;jVertexNum;j+)if(G-Edgeuj & !visitedjj & !visitedv)/u, j可轉換，且j, V都未被訪問過pathu=j;/將頂點j保存DFS_path (G, j, v);6. 輸岀u到v的簡單路徑路徑的保存是用前一個頂點u的序號作為數(shù)組path的下標即pathEu保存下一

12、個頂點j 的，故在輸出時，先將k二u,然后輸出u的狀態(tài)，再將k=pathk,輸出當前頂點狀態(tài)，以 此循環(huán)直到k二v,最后輸出v的狀態(tài)。void print_path (AdjGraph *G, int u, int v)/輸出從u到V的簡單路徑，即頂點序列中不重復出現(xiàn)的路徑int k;k=u;while(k!=v)cout/z (/G-VerticesList kzzG-VerticesList k WolfVerticesList k. SheepVerticesList k. Vegetz，);coutendl;k=pathk;VerticesListk. SheepVerticesLis

13、tk. Veget*) *:coutendl;7. 主函數(shù)void mainOcout，/0表示本岸，1表示對岸n;cout(農(nóng)夫，狼，羊,蔬菜)n;int i, j;AdjGraph graph;CreateG(& graph);for(i=0;igraph. VertexNum;i+)visitedi二 FALSE; /置初值i二locate (&graph, 0, 0, 0, 0) ;/找到最初狀態(tài)的頂點位置j二locate(&graph, 1, 1, 1, 1) ;/全部過河后的狀態(tài)的頂點位苣DFS_path(&graph, i, j);深度優(yōu)先搜索從開始狀態(tài)到全部過河的一條安全路徑i

14、f (visited】 j)/若搜索到了一條安全路徑則打印出安全路徑print_path(&graph, i, j);return;4、上機調試經(jīng)分析可知，該問題總共有2種路徑可行，分別是：帶羊到對岸，空手回本岸， 帶狼到對岸，帶羊回本岸，帶菜到對岸，空手回本岸，帶羊到對岸：帶羊到對岸，空手 回本岸，帶菜到對岸，帶羊回本岸，帶狼到對岸，空手回本岸，帶羊到對岸。本程序輸出的路徑是前一種方案，具體見測試結果截圖部分。本來想要2種方案都輸出的，但是還沒 能如愿解決。另外本程序在搜索路徑是采用的是DFS即深度優(yōu)先搜索，還可用BFS即廣度優(yōu) 先搜索。深度優(yōu)先：每個時刻探索一條路徑，并記錄訪問過的合法狀態(tài)

15、，一直向前探視，直 到走不通時回溯。顯然，應該用堆棧來保存訪問過的狀態(tài)，以便回溯。廣度優(yōu)先：在所有可能的路徑上齊頭并進，同時探索可能性。這樣，在某個位置會有 多個分支，他們都要進行處理，因此需要一個緩沖隊列，把他們進對保存，在依次岀對處理。 這樣才能應付所有的狀態(tài)。在創(chuàng)建安全圖時需要創(chuàng)建鄰接矩陣來存儲圖，時間復雜度為0 () , n為頂點數(shù)， 在深度優(yōu)先搜索安全路徑時，時間復雜度為0 (n+e),亡為邊數(shù)，其他相關的操作的算法的 時間復雜度均要比前二者小，故本程序的時間復雜度為T (n) = 0 (n=)。5、用戶使用說明在vc+6. 0下運行程序即可得到解決問題的方案，不需要其他操作6、測試

16、結果圖2測試結果圖7、參考文獻 王昆侖，李紅.數(shù)據(jù)結構與算法北京：中國鐵道出版社，2006年5月。2胡學綱.數(shù)據(jù)結構與算法設計指導.北京：淸華大學出版社，1999.8、附錄#include #define MaxNumVertices 10 /最大頂點數(shù)typedef enum FALSE, TRUE Boolean;typedef struct /圖的頂點類型int Farmer, Wolf, Sheep, Veget;VexType;typedef structint VertexNum, CurrentEdges; /圖的當前頂點數(shù)和邊數(shù)VexType VerticesList MaxN

17、umVertices;/頂點向量(代表頂點)int Edge iMaxNumVerticesl LMaxNumVertices ;/鄰接矩陣/用于存儲圖中的邊，其矩陣元素個數(shù)取決于頂點個數(shù)，與邊數(shù)無關AdjGraph; /左義圖的鄰接矩陣存儲結構Boolean visitedMaxNumVertices;/對已訪問的頂點進行標記(圖的遍歷)int pathMaxNumVertices ;/保存DFS搜索到的路徑，即與某頂點到F頂點的路徑int locate (AdjGraph *G, int F, int W, int S, int V)/查找頂點(F, W, S, V)在頂點向量中的位置in

18、t i;for(i=0;iVertexNum;i+)if(G-VerticesListi.Farmer=F & G-VerticesListi. Wolf=W &G-VerticesListiSheep=S & G-VerticesListiVeget=V)return(i);/返回當前位置int is_safe (int F, int W, int S, int V)/判斷目前的(F, W, S, V)是否安全辻(F!=S & (W=S S=V)return (0);當農(nóng)夫與羊不在一起時，狼與羊或羊與白菜在一起是不安全的else 否則安全return (1) ;/安全返回 1int is_c

19、onnected(AdjGraph *G,int i, int j)/判斷狀態(tài)i與狀態(tài)j之間是否可轉換int k=0;if(G-VerticesListi. Wolf!=G-VerticesListj Wolf)k+;if(G-VerticesListi Sheep!=G-VerticesListj Sheep)k+;if(G-VerticesListi Veget!二G-VerticesList j Veget)k+;if(G-VerticesListi Farmer!二G一VerticesListj Farmer & k=l)/以上三個條件不同時滿足兩個且農(nóng)夫狀態(tài)改變時，返回真/也即農(nóng)夫每

20、次只能帶一件東西過橋return(l);elsereturn(0);void CreateG(AdjGraph*G)int i,j,F,W,S,V;i 二0;for(F=0;F=l;F+)/生成所有安全的圖的頂點for(W=0;W=l;W44-)for(S=0;S=l;S+)for(V=0;VVerticesListi Farmer=F;G-VerticesListi. Wolf=W;G-VerticesListi Sheep=S;G-VerticesListi Veget=V;i+；G-VertexNum=i;for(i=0;iVertexNum; i+)/鄰接矩陣初始化即建立鄰接矩陣for(j=0;j Vert exNum;j +)if (is_connected(G, i, j)G-Edgeij=G-Edgeji=l;狀態(tài)i與狀態(tài)j之間可轉化，初始化為1,否則為0elseG-Edgeij=G-Edgeji=0;return;void print_path(AdjGraph *G, int u, int v)/輸出從u到V的簡單路徑，即頂點序列中不重復岀現(xiàn)的路徑int k;k=u;while(k!=v)cou