傳教士野人過(guò)河問(wèn)題兩種解法思路(已修改)
2025-04-05 06:57 本頁(yè)面
【正文】 實(shí)驗(yàn) 傳教士野人過(guò)河問(wèn)題37030602 王世婷一、實(shí)驗(yàn)問(wèn)題傳教士和食人者問(wèn)題（The Missionaries and Cannibals Problem）。在河的左岸有3個(gè)傳教士、1條船和3個(gè)食人者，傳教士們想用這條船將所有的成員運(yùn)過(guò)河去，但是受到以下條件的限制：（1）傳教士和食人者都會(huì)劃船，但船一次最多只能裝運(yùn)兩個(gè)；（2）在任何岸邊食人者數(shù)目都不得超過(guò)傳教士，否則傳教士就會(huì)遭遇危險(xiǎn)：被食人者攻擊甚至被吃掉。此外，假定食人者會(huì)服從任何一種過(guò)河安排，試規(guī)劃出一個(gè)確保全部成員安全過(guò)河的計(jì)劃。二、解答步驟(1) 設(shè)置狀態(tài)變量并確定值域M為傳教士人數(shù)，C 為野人人數(shù)，B為船數(shù)，要求M=C且M+C = 3，L表示左岸，R表示右岸。初始狀態(tài) 目標(biāo)狀態(tài)L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(2) 確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集用三元組來(lái)表示：（ML , CL , BL）（均為左岸狀態(tài)）其中,BL ∈{ 0 , 1} ：(3 , 3 , 1) ： (0 , 0 , 0)初始狀態(tài)表示全部成員在河的的左岸；目標(biāo)狀態(tài)表示全部成員從河的左岸全部渡河完畢。(3) 定義并確定規(guī)則集合仍然以河的左岸為基點(diǎn)來(lái)考慮，把船從左岸劃向右岸定義為Pij操作。其中，第一下標(biāo)i表示船載的傳教士數(shù)，第二下標(biāo)j表示船載的食人者數(shù)；同理，從右岸將船劃回左岸稱之為Qij操作，下標(biāo)的定義同前。則共有10種操作，操作集為 F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P10 if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 ) P01 if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 ) P11 if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) P20 if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 ) P02 if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 ) Q10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) Q01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) Q11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 ) Q02 if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) (4) 當(dāng)狀態(tài)數(shù)量不是很大時(shí)，畫出合理的狀態(tài)空間圖 圖1 狀態(tài)空間圖箭頭旁邊所標(biāo)的數(shù)字表示了Ｐ或Ｑ操作的下標(biāo)，即分別表示船載的傳教士數(shù)和食人者數(shù)。三、算法設(shè)計(jì)方法一: 樹(shù)的遍歷根據(jù)規(guī)則由根（初始狀態(tài)）擴(kuò)展出整顆樹(shù)，檢測(cè)每個(gè)結(jié)點(diǎn)的“可擴(kuò)展標(biāo)記”，為“1”的即目標(biāo)結(jié)點(diǎn)。由目標(biāo)結(jié)點(diǎn)上溯出路徑。見(jiàn)源程序1。方法二：?jiǎn)l(fā)式搜索構(gòu)造啟發(fā)式函數(shù)為：選擇較大值的結(jié)點(diǎn)先擴(kuò)展。見(jiàn)源程序2。四、實(shí)驗(yàn)結(jié)果方法一的實(shí)驗(yàn)結(jié)果：傳教士野人過(guò)河問(wèn)題第1種方法：第1次：左岸到右岸，傳教士過(guò)去1人，野人過(guò)去1人第2次：右岸到左岸，傳教士過(guò)去1人，野人過(guò)去0人第3次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第4次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第5次：左岸到右岸，傳教士過(guò)去2人，野人過(guò)去0人第6次：右岸到左岸，傳教士過(guò)去1人，野人過(guò)去1人第7次：左岸到右岸，傳教士過(guò)去2人，野人過(guò)去0人第8次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第9次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第10次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第11次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第2種方法：第1次：左岸到右岸，傳教士過(guò)去1人，野人過(guò)去1人第2次：右岸到左岸，傳教士過(guò)去1人，野人過(guò)去0人第3次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第4次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第5次：左岸到右岸，傳教士過(guò)去2人，野人過(guò)去0人第6次：右岸到左岸，傳教士過(guò)去1人，野人過(guò)去1人第7次：左岸到右岸，傳教士過(guò)去2人，野人過(guò)去0人第8次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第9次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第10次：右岸到左岸，傳教士過(guò)去1人，野人過(guò)去0人第11次：左岸到右岸，傳教士過(guò)去1人，野人過(guò)去1人第3種方法：第1次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第2次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第3次：左岸到右岸，傳教士過(guò)去0人，野人過(guò)去2人第4次：右岸到左岸，傳教士過(guò)去0人，野人過(guò)去1人第5次：左岸到右岸，傳教士過(guò)去2人，野人過(guò)去0人第6次：右岸到左岸，傳教士過(guò)去1人，野人過(guò)去1人第7次
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1