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

1、1.上機(jī)內(nèi)容傳教士與野人問(wèn)題求解（寬度搜索算法）二 問(wèn)題背景：從前有一條河，河的左岸有m個(gè)傳教士(Missionary)和m個(gè)野人(Cannibal)，和一艘最多可乘n人的小船。約定左岸，右岸和船上或者沒(méi)有傳教士，或者野人數(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個(gè)野人同在左岸作為初始狀態(tài)

2、。四 實(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 ElemType : Move /繼承Move類(lèi)，獲得傳教士，野人數(shù)據(jù)成員。private: bool boat; /船是否在左岸？public: ElemType* flag; / 標(biāo)示前一狀態(tài)即擴(kuò)展出本結(jié)點(diǎn)的父結(jié)點(diǎn)信息 ElemType(int MAX

3、_PEOPLE) /創(chuàng)建初始狀態(tài) missionary = cannibal = MAX_PEOPLE; boat = true; flag = NULL;在這里，Elemtype集成了Move，從而獲得Move類(lèi)的傳教士和野人數(shù)據(jù)成員。以上兩個(gè)類(lèi)的數(shù)據(jù)成員用于保存所有擴(kuò)展生成的結(jié)點(diǎn)。其中missionary表示表示左岸上傳教士的樹(shù)目，cannibal表示左岸上野人的樹(shù)目，boat表示船在哪個(gè)岸上（其中true表示在左岸，這是船的初始狀態(tài)，表示false在右岸）， flag用于標(biāo)示前一狀態(tài)即擴(kuò)展出本結(jié)點(diǎn)的父結(jié)點(diǎn)信息，以便最后回搜找出解的路徑。舉例說(shuō)明：假設(shè)左岸有3個(gè)傳教士和3個(gè)野人，小船最多可

4、乘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類(lèi)的（m,c）表示。行動(dòng)規(guī)則的兩位數(shù)分別代表要移動(dòng)的傳教士，野人的數(shù)量。對(duì)于固定大小的船，其裝載能力是一定的，所以它的行動(dòng)規(guī)則空間也是一定的。在這里，用MoveGroup類(lèi)的構(gòu)造函數(shù)構(gòu)造出所有的行動(dòng)規(guī)則。 注意，這里MoveGroup類(lèi)中的Move對(duì)象只有500的可用空間，所以，輸入的傳教士和野人數(shù)目構(gòu)成的行

5、動(dòng)規(guī)則不能超過(guò)500種。(3)寬度優(yōu)先算法：實(shí)驗(yàn)的主要搜索算法由ANSWER類(lèi)的構(gòu)造函數(shù)實(shí)現(xiàn)，這里主要用到了OPEN和CLOSED隊(duì)列，以及一個(gè)臨時(shí)的TEMP堆棧。其中，OPEN表用于存放擴(kuò)展結(jié)點(diǎn)，CLOSED表用于存放被擴(kuò)展結(jié)點(diǎn)，TEMP則用于用于記錄成功搜索的路徑。搜索過(guò)程大致如下描述：先構(gòu)造初始結(jié)點(diǎn)以及船的行動(dòng)規(guī)則，初始結(jié)點(diǎn)入OPEN隊(duì)列，以寬度優(yōu)先依次搜索OPEN隊(duì)列頭結(jié)點(diǎn)的子結(jié)點(diǎn)，同時(shí)保存受訪(fǎng)問(wèn)結(jié)點(diǎn)的父結(jié)點(diǎn)信息，知道搜索到目標(biāo)結(jié)點(diǎn)或者無(wú)解為止。算法框圖如下所示： 開(kāi)始初始接結(jié)點(diǎn)并入OPEN隊(duì)列Y返回OPEN為空？NOPEN隊(duì)列頭結(jié)點(diǎn)n出列，并入CLOSED隊(duì)列把結(jié)點(diǎn)的子結(jié)點(diǎn)并入OPE

6、N隊(duì)列，保存父結(jié)點(diǎn)Y被擴(kuò)展結(jié)點(diǎn)還有子結(jié)點(diǎn)嗎？N返回3 程序界面和功能說(shuō)明：程序運(yùn)行環(huán)境為DOS控制臺(tái)，運(yùn)行開(kāi)始以后，程序提示輸入需要坐船的傳教士和野人數(shù)目，例如輸入3表示有3個(gè)傳教士和3個(gè)野人。 用戶(hù)按回車(chē)鍵以后，程序繼續(xù)提示輸入船的裝載能力，例如輸入2表示這個(gè)船依次最多可以坐2人。注：一般情況下，船的裝載能力應(yīng)該少于傳教士或野人的數(shù)量，而且一般為偶數(shù)。程序開(kāi)始運(yùn)行時(shí)的界面截圖：程序運(yùn)行結(jié)束時(shí)的界面截圖：輸出文件示例：Left(3, 3) | (0, 0)RightStep 1Move 0 missionaries and 2 cannibals to the right side.Left(

7、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 missionaries and 1 cannibals to the left side.Left(3, 1) | (0, 2)RightStep 5Move 2 missionaries and 0

8、 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(0, 2) | (3, 1)RightStep 8Move 0 missionaries and 1 cannibals to the left side.Left(0, 3) | (3, 0)Ri

9、ghtStep 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 and 2 cannibals to the right side.Left(0, 0) | (3, 3)RightOK!5錯(cuò)誤說(shuō)明：（1） 關(guān)于有沒(méi)有解的問(wèn)題：由于傳教士和野人問(wèn)題是一個(gè)真實(shí)的問(wèn)題，來(lái)到

10、岸邊的傳教士和野人數(shù)目與船的裝載能力都是隨機(jī)的，所以某些特定情況下，要以一定規(guī)則把人都運(yùn)到船的對(duì)岸是沒(méi)有解的，例如假設(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í)間的問(wèn)題：本實(shí)驗(yàn)使用寬度優(yōu)先搜索算法，但并沒(méi)有進(jìn)行優(yōu)化，所以有時(shí)候程序雖然確實(shí)有解，但是由于算法的效率確實(shí)很低，造成的時(shí)間上的開(kāi)銷(xiāo)有時(shí)候可能會(huì)比起喝一杯咖啡的時(shí)間還要長(zhǎng)，這時(shí)候程序會(huì)提示：Please wait patiently。Working . . .六 心得體會(huì)：這個(gè)是我們小組的第一個(gè)實(shí)驗(yàn)，由于經(jīng)驗(yàn)以及能力有限，所