傳教士野人過河問題兩種解法思路-wenkub
2023-04-08 06:57:34 本頁面
【正文】 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)數(shù)量不是很大時，畫出合理的狀態(tài)空間圖 圖1 狀態(tài)空間圖箭頭旁邊所標的數(shù)字表示了Ｐ或Ｑ操作的下標，即分別表示船載的傳教士數(shù)和食人者數(shù)。二、解答步驟(1) 設置狀態(tài)變量并確定值域M為傳教士人數(shù)，C 為野人人數(shù)，B為船數(shù)，要求M=C且M+C = 3，L表示左岸，R表示右岸。實驗 傳教士野人過河問題37030602 王世婷一、實驗問題傳教士和食人者問題（The Missionaries and Cannibals Problem）。初始狀態(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)表示全部成員從河的左岸全部渡河完畢。三、算法設計方法一: 樹的遍歷根據(jù)規(guī)則由根（初始狀態(tài)）擴展出整顆樹，檢測每個結(jié)點的“可擴展標記”，為“1”的即目標結(jié)點。見源程序2。設初始狀態(tài)和目標狀態(tài)分別為：但在描述規(guī)則時發(fā)現(xiàn)這樣定義會造成規(guī)則麻煩、不清晰，原因在于此題并不關(guān)心是哪幾個傳教士和野人在船上，僅關(guān)心其人數(shù)，故沒有必要將每個人都設置變量，分別將傳教士、野人、船作為一類即可。n=2。node(1,:)=[3,3,1,1,1]。(node(j,2)=1) forward(j,0,1)。amp。 node(j,1)==node(j,2)) forward(j,1,1)。 end if (node(j,1)==2 amp。 node(j,2)==1) forward(j,2,0)。 end if (node(j,1)==2 amp。 node(j,2)==1) afterward(j,1,0)。 end if (node(j,1)==0 || node(j,1)==3)amp。amp。 end end end j=j+1。for t=1:n j=1。 k=node(k,5)。第%d種方法：\n39。 if node(result(j),3)==1 fprintf(39。 end if node(result(j),3)==0 fprintf(39。 end j=j1。)。)。node(n,2)=node(z,2)y。node(n,4)=1。endn=n+1。node(n,2)=node(z,2)+y。node(n,4)=1。endn=n+1。amp。 return end i=node(i,5)。amp。if node(n,1)==0 amp。 node(n,3)==0 s=1。global n node open_list index。node(1,:)=[3,3,1,1,1]。if row==0 fprintf(39。%定義啟發(fā)函數(shù) if node(open_list(i1,1),4)==1%如果該結(jié)點是目標結(jié)點，則打印結(jié)果 fprintf(39。 k=open_list(i1,1)。 j=j+1。)。第%d次：左岸到右岸，傳教士過去%d人，野人過去%d人\n39。第%d次：右岸到左岸，傳教士過去%d人，野人過去%d人\n39。 end pause()。 return endend[r_row,~,~]=find(open_list(:,2)==max(open_list(:,2)))。(node(j,2)=1) forward(j,0,1)。amp。 node(j,1)==node(j,2))
試題試卷相關(guān)推薦
鄂ICP備17016276號-1