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