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

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

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

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

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

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

6、rentEdges;/圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)VexType VerticesList MaxNumVerticesl;/頂點(diǎn)向量（代表頂點(diǎn)）int EdgeMaxNumVertices MaxNumVertices;/鄰接矩陣/用于存儲(chǔ)圖中的邊，其矩陣元素個(gè)數(shù)取決于頂點(diǎn)個(gè)數(shù)，與邊數(shù)無(wú)關(guān)AdjGraph;圖的基本操作1. 査找頂點(diǎn)(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) ;/返回當(dāng)前位置return (-1); 沒(méi)有找到此頂點(diǎn)2. 判斷目前的(F, W, S, V)是否安全當(dāng)農(nóng)夫與羊不在一起時(shí)，狼與羊或羊與白菜在一起是不安全的，否則安全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之間是否可轉(zhuǎn)換顯然每次轉(zhuǎn)換農(nóng)夫都在移動(dòng)，而農(nóng)夫移動(dòng)

8、時(shí)最多只能攜帶一個(gè)物件，故每次狀態(tài)轉(zhuǎn) 換，其他3件只能有一件移動(dòng)或都不移動(dòng)，能轉(zhuǎn)換時(shí)返回1,不能轉(zhuǎn)換時(shí)返回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+)/生成所有安全的圖的頂點(diǎn)for(W=0;W=l;W+)/因?yàn)橹挥?和1倆個(gè)狀態(tài)故循環(huán)都時(shí)從0開(kāi)始1結(jié)束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)計(jì)安全頂點(diǎn)個(gè)數(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之間可轉(zhuǎn)化，初始化為1,否則為0G-Edgei j=G-EdgejelseG-Edgeij=G-Edgeji=O;return;5. 深度優(yōu)先搜索u到v的簡(jiǎn)單路徑深度優(yōu)先：每個(gè)時(shí)刻探索一條路徑，并記錄訪問(wèn)過(guò)的合法狀態(tài)，一直向前探視，直 到走不通時(shí)回溯。顯然，應(yīng)該用堆棧來(lái)保存訪問(wèn)過(guò)的狀態(tài)，以便回溯。具體分析如下： 首先訪問(wèn)u,并標(biāo)記； 訪問(wèn)下一個(gè)與u可轉(zhuǎn)換的頂點(diǎn)vl,并標(biāo)記，將vl存儲(chǔ)起來(lái)： 再?gòu)膙l開(kāi)始，選取下一個(gè)可以與vl轉(zhuǎn)換的頂點(diǎn)v2訪問(wèn)，標(biāo)記，并存儲(chǔ)； 重復(fù)直到某頂點(diǎn)vi

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

12、個(gè)頂點(diǎn)j 的，故在輸出時(shí)，先將k二u,然后輸出u的狀態(tài)，再將k=pathk,輸出當(dāng)前頂點(diǎn)狀態(tài)，以 此循環(huán)直到k二v,最后輸出v的狀態(tài)。void print_path (AdjGraph *G, int u, int v)/輸出從u到V的簡(jiǎn)單路徑，即頂點(diǎn)序列中不重復(fù)出現(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表示對(duì)岸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)的頂點(diǎn)位置j二locate(&graph, 1, 1, 1, 1) ;/全部過(guò)河后的狀態(tài)的頂點(diǎn)位苣DFS_path(&graph, i, j);深度優(yōu)先搜索從開(kāi)始狀態(tài)到全部過(guò)河的一條安全路徑i

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

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

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

17、umVertices;/頂點(diǎn)向量(代表頂點(diǎn))int Edge iMaxNumVerticesl LMaxNumVertices ;/鄰接矩陣/用于存儲(chǔ)圖中的邊，其矩陣元素個(gè)數(shù)取決于頂點(diǎn)個(gè)數(shù)，與邊數(shù)無(wú)關(guān)AdjGraph; /左義圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)Boolean visitedMaxNumVertices;/對(duì)已訪問(wèn)的頂點(diǎn)進(jìn)行標(biāo)記(圖的遍歷)int pathMaxNumVertices ;/保存DFS搜索到的路徑，即與某頂點(diǎn)到F頂點(diǎn)的路徑int locate (AdjGraph *G, int F, int W, int S, int V)/查找頂點(diǎn)(F, W, S, V)在頂點(diǎn)向量中的位置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);/返回當(dāng)前位置int is_safe (int F, int W, int S, int V)/判斷目前的(F, W, S, V)是否安全辻(F!=S & (W=S S=V)return (0);當(dāng)農(nóng)夫與羊不在一起時(shí)，狼與羊或羊與白菜在一起是不安全的else 否則安全return (1) ;/安全返回 1int is_c

19、onnected(AdjGraph *G,int i, int j)/判斷狀態(tài)i與狀態(tài)j之間是否可轉(zhuǎn)換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)/以上三個(gè)條件不同時(shí)滿(mǎn)足兩個(gè)且農(nóng)夫狀態(tài)改變時(shí)，返回真/也即農(nóng)夫每

20、次只能帶一件東西過(guò)橋return(l);elsereturn(0);void CreateG(AdjGraph*G)int i,j,F,W,S,V;i 二0;for(F=0;F=l;F+)/生成所有安全的圖的頂點(diǎn)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之間可轉(zhuǎn)化，初始化為1,否則為0elseG-Edgeij=G-Edgeji=0;return;void print_path(AdjGraph *G, int u, int v)/輸出從u到V的簡(jiǎn)單路徑，即頂點(diǎn)序列中不重復(fù)岀現(xiàn)的路徑int k;k=u;while(k!=v)cou