傳教士和野人問題實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1.上機內(nèi)容傳教士與野人問題求解（寬度搜索算法）二 問題背景：從前有一條河，河的左岸有m個傳教士(Missionary)和m個野人(Cannibal)，和一艘最多可乘n人的小船。約定左岸，右岸和船上或者沒有傳教士，或者野人數(shù)量少于傳教士，否則野人會把傳教士吃掉。三 實驗內(nèi)容：編程，接收m和n，搜索一條可讓所有的野人和傳教士安全渡到右岸的方案，例如下圖:（M表示傳教士(Missionary)，C 表示野人(Cannibal)）初態(tài)目標(biāo)LeftBankRiverRightbankLeftBankRiverRightbankM.M.C.C.注：本實驗的舉例均以3個傳教士和3

2、個野人同在左岸作為初始狀態(tài)。四 實驗方案和算法： 1數(shù)據(jù)結(jié)構(gòu)： 本實驗需要用到的數(shù)據(jù)結(jié)構(gòu)主要是隊列和堆棧，其實現(xiàn)均包含于dso.h頭文件中，分別命名為class stack和class queue。2寬度搜索算法：(1)結(jié)點結(jié)構(gòu)：class Move public:    int missionary;      /要移動的傳教士數(shù)量    int cannibal;        /野人;class ElemTyp

3、e : Move   /繼承Move類，獲得傳教士，野人數(shù)據(jù)成員。private:    bool boat;            /船是否在左岸？public:    ElemType* flag;      / 標(biāo)示前一狀態(tài)即擴展出本結(jié)點的父結(jié)點信息    ElemType(int MAX_PEOPLE)   /創(chuàng)建初始狀態(tài)

4、0;      missionary = cannibal = MAX_PEOPLE;       boat = true;       flag = NULL;在這里，Elemtype集成了Move，從而獲得Move類的傳教士和野人數(shù)據(jù)成員。以上兩個類的數(shù)據(jù)成員用于保存所有擴展生成的結(jié)點。其中missionary表示表示左岸上傳教士的樹目，cannibal表示左岸上野人的樹目，boat表示船在哪個岸上（其中true表示在左岸

5、，這是船的初始狀態(tài)，表示false在右岸）， flag用于標(biāo)示前一狀態(tài)即擴展出本結(jié)點的父結(jié)點信息，以便最后回搜找出解的路徑。舉例說明：假設(shè)左岸有3個傳教士和3個野人，小船最多可乘2人。把當(dāng)前左岸的狀態(tài)抽象為：(3,3,1)，前兩個"3"代表左岸有3個傳教士和3個野人，1代表船在左岸。很明顯，目標(biāo)狀態(tài)為(0,0,0),表示左岸的傳教士和也人數(shù)目都是0，而船在右岸。(2)船的行動規(guī)則（successor function）:把每一次可行的渡船方案作為行動規(guī)則，用Move類的（m,c）表示。行動規(guī)則的兩位數(shù)分別代表要移動的傳教士，野人的數(shù)量。對于固定大小的船，其裝載能力是一定的，

6、所以它的行動規(guī)則空間也是一定的。在這里，用MoveGroup類的構(gòu)造函數(shù)構(gòu)造出所有的行動規(guī)則。 注意，這里MoveGroup類中的Move對象只有500的可用空間，所以，輸入的傳教士和野人數(shù)目構(gòu)成的行動規(guī)則不能超過500種。(3)寬度優(yōu)先算法：實驗的主要搜索算法由ANSWER類的構(gòu)造函數(shù)實現(xiàn)，這里主要用到了OPEN和CLOSED隊列，以及一個臨時的TEMP堆棧。其中，OPEN表用于存放擴展結(jié)點，CLOSED表用于存放被擴展結(jié)點，TEMP則用于用于記錄成功搜索的路徑。搜索過程大致如下描述：先構(gòu)造初始結(jié)點以及船的行動規(guī)則，初始結(jié)點入OPEN隊列，以寬度優(yōu)先依次搜索OPEN隊列頭結(jié)點的子結(jié)點，同時保

7、存受訪問結(jié)點的父結(jié)點信息，知道搜索到目標(biāo)結(jié)點或者無解為止。算法框圖如下所示： 開始初始接結(jié)點并入OPEN隊列Y返回OPEN為空？NOPEN隊列頭結(jié)點n出列，并入CLOSED隊列把結(jié)點的子結(jié)點并入OPEN隊列，保存父結(jié)點Y被擴展結(jié)點還有子結(jié)點嗎？N返回3 程序界面和功能說明：程序運行環(huán)境為DOS控制臺，運行開始以后，程序提示輸入需要坐船的傳教士和野人數(shù)目，例如輸入3表示有3個傳教士和3個野人。 用戶按回車鍵以后，程序繼續(xù)提示輸入船的裝載能力，例如輸入2表示這個船依次最多可以坐2人。注：一般情況下，船的裝載能力應(yīng)該少于傳教士或野人的數(shù)量，而且一般為偶數(shù)。程序開始運行時的界面截圖：程序運行結(jié)束時的界

8、面截圖：輸出文件示例：Left(3, 3) | (0, 0)RightStep 1Move 0 missionaries and 2 cannibals to the right side.Left(3, 1) | (0, 2)RightStep 2Move 0 missionaries and 1 cannibals to the left side.Left(3, 2) | (0, 1)RightStep 3Move 0 missionaries and 2 cannibals to the right side.Left(3, 0) | (0, 3)RightStep 4Move 0 m

9、issionaries and 1 cannibals to the left side.Left(3, 1) | (0, 2)RightStep 5Move 2 missionaries and 0 cannibals to the right side.Left(1, 1) | (2, 2)RightStep 6Move 1 missionaries and 1 cannibals to the left side.Left(2, 2) | (1, 1)RightStep 7Move 2 missionaries and 0 cannibals to the right side.Left

10、(0, 2) | (3, 1)RightStep 8Move 0 missionaries and 1 cannibals to the left side.Left(0, 3) | (3, 0)RightStep 9Move 0 missionaries and 2 cannibals to the right side.Left(0, 1) | (3, 2)RightStep 10Move 0 missionaries and 1 cannibals to the left side.Left(0, 2) | (3, 1)RightStep 11Move 0 missionaries an

11、d 2 cannibals to the right side.Left(0, 0) | (3, 3)RightOK!5錯誤說明：（1） 關(guān)于有沒有解的問題：由于傳教士和野人問題是一個真實的問題，來到岸邊的傳教士和野人數(shù)目與船的裝載能力都是隨機的，所以某些特定情況下，要以一定規(guī)則把人都運到船的對岸是沒有解的，例如假設(shè)有10個傳教士和10個野人，船一次最多能夠裝2人，這時候是不能把人都運到對岸的，這時候程序會提示：There may not be any way to transport these guys.（2） 關(guān)于運行時間的問題：本實驗使用寬度優(yōu)先搜索算法，但并沒有進行優(yōu)化，所以有時候程序雖然確實有解，但是由于算法的效率確實很低，造成的時間上的開銷有時候可能會比起喝一杯咖啡的時間還要長，這時候程序會提示：Please wait patiently。Working . . .六 心得體會：這個是我們小組的第一個實驗，