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

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

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

3、人數(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) missionary = cannibal = max_people; boat = true; flag = null; 在這里，elemtype 集成了 move，從而獲得 move 類的傳教士和野人數(shù)據(jù)成員。以上兩個(gè)類的數(shù)據(jù)成員用于保存全部擴(kuò)展生成的結(jié)點(diǎn)。其中 missionary 表示表示左岸上傳教士的樹目，cannibal 表示左岸上野人的樹目，boat 表

4、示船在哪個(gè)岸上（其中 true 表示在左岸，這是船的初始狀態(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ù)分別代

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

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

7、：一般狀況下，船的裝載力量應(yīng)當(dāng)少于傳教士或野人的數(shù)量，而且一般為偶數(shù)。 程序 開頭運(yùn)行時(shí)的 界面截圖： 程序 運(yùn)行結(jié)束時(shí)的 界面截圖： 把結(jié)點(diǎn)的子結(jié)點(diǎn)并入 open隊(duì)列，保存父結(jié)點(diǎn) 被擴(kuò)展結(jié)點(diǎn)還有子結(jié)點(diǎn)嗎？ 返回 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 錯(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í)間的問題：本試驗(yàn)使用寬度優(yōu)先搜尋算法，但并沒有進(jìn)行優(yōu)化，所以有時(shí)候程序雖然的確有解，但是由于算法的效率的確很低，造成的時(shí)間上的開銷有時(shí)候可能會(huì)比起喝一杯咖啡的時(shí)間還要長(zhǎng)，這時(shí)候程序會(huì)提示： please wait patiently。working . . . 六 六 心得體會(huì)： 這個(gè)是我們小組的第一個(gè)試驗(yàn)，由于閱歷以及力量有限，所以算法上