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

1、本文格式為word版，下載可任意編輯傳教士和野人問題實驗報告 1.上機內(nèi)容 傳教士與野人問題求解（寬度搜尋算法） 二 二 問題背景： 從前有一條河，河的左岸有 m 個傳教士(missionary)和 m 個野人(cannibal)，和一艘最多可乘 n 人的小船。商定左岸，右岸和船上或者沒有傳教士，或者野人數(shù)量少于傳教士，否則野人會把傳教士吃掉。 三 三 試驗內(nèi)容： 編程，接收 m 和 n，搜尋一條可讓全部的野人和傳教士平安渡到右岸的方案，例如下圖: （m 表示傳教士(missionary)，c 表示野人(cannibal)） 初 態(tài) 目 標 left bank river right bank

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

3、人數(shù)據(jù)成員。 private: bool boat; /船是否在左岸？ public: elemtype* flag; / 標示前一狀態(tài)即擴展出本結(jié)點的父結(jié)點信息 elemtype(int max_people) /創(chuàng)建初始狀態(tài) missionary = cannibal = max_people; boat = true; flag = null; 在這里，elemtype 集成了 move，從而獲得 move 類的傳教士和野人數(shù)據(jù)成員。以上兩個類的數(shù)據(jù)成員用于保存全部擴展生成的結(jié)點。其中 missionary 表示表示左岸上傳教士的樹目，cannibal 表示左岸上野人的樹目，boat 表

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

5、表要移動的傳教士，野人的數(shù)量。對于固定大小的船，其裝載力量是肯定的，所以它的行動規(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 則用于用于記錄勝利搜尋的路徑。 搜尋過程大致

6、如下描述：先構(gòu)造初始結(jié)點以及船的行動規(guī)章，初始結(jié)點入 open 隊列，以寬度優(yōu)先依次搜尋 open 隊列頭結(jié)點的子結(jié)點，同時保存受訪問結(jié)點的父結(jié)點信息，知道搜尋到目標結(jié)點或者無解為止。 算法框圖如下所示： 開頭 初始接結(jié)點并入 open 隊列 open 為空？ open 隊列頭結(jié)點 n 出列，并入 closed 隊列 返回 y n 3 程序界面 和功能 說明： 程序運行環(huán)境為 dos 掌握臺，運行開頭以后，程序提示輸入需要坐船的傳教士和野人數(shù)目，例如輸入 3 表示有 3 個傳教士和 3 個野人。 用戶按回車鍵以后，程序連續(xù)提示輸入船的裝載力量，例如輸入 2 表示這個船依次最多可以坐 2 人。注

7、：一般狀況下，船的裝載力量應(yīng)當(dāng)少于傳教士或野人的數(shù)量，而且一般為偶數(shù)。 程序 開頭運行時的 界面截圖： 程序 運行結(jié)束時的 界面截圖： 把結(jié)點的子結(jié)點并入 open隊列，保存父結(jié)點 被擴展結(jié)點還有子結(jié)點嗎？ 返回 y n 輸出文件示例： left(3, 3) | (0, 0)right step 1 move 0 missionaries and 2 cannibals to the right side. left(3, 1) | (0, 2)right step 2 move 0 missionaries and 1 cannibals to the left side. left(3,

8、2) | (0, 1)right step 3 move 0 missionaries and 2 cannibals to the right side. left(3, 0) | (0, 3)right step 4 move 0 missionaries and 1 cannibals to the left side. left(3, 1) | (0, 2)right step 5 move 2 missionaries and 0 cannibals to the right side. left(1, 1) | (2, 2)right step 6 move 1 missionar

9、ies and 1 cannibals to the left side. left(2, 2) | (1, 1)right step 7 move 2 missionaries and 0 cannibals to the right side. left(0, 2) | (3, 1)right step 8 move 0 missionaries and 1 cannibals to the left side. left(0, 3) | (3, 0)right step 9 move 0 missionaries and 2 cannibals to the right side. le

10、ft(0, 1) | (3, 2)right step 10 move 0 missionaries and 1 cannibals to the left side. left(0, 2) | (3, 1)right step 11 move 0 missionaries and 2 cannibals to the right side. left(0, 0) | (3, 3)right ok! 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 . . . 六 六 心得體會： 這個是我們小組的第一個試驗，由于閱歷以及力量有限，所以算法上