傳教士和野人問題實(shí)驗(yàn)報(bào)告

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

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

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

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

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

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

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

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