傳教士與野人過河問題(已修改)
2025-08-04 08:09 本頁面
【正文】 傳教士野人問題有N個(gè)傳教士和N個(gè)野人要過河，現(xiàn)在有一條船只能承載K個(gè)人（包括野人），KN，在任何時(shí)刻，如果有野人和傳教士在一起，必須要求傳教士的人數(shù)多于或等于野人的人數(shù)。設(shè)M為傳教士的人數(shù)，C為野人的人數(shù)，用狀態(tài)空間發(fā)求解此問題的過程如下：M、C = N，boat = k，要求M=C且M+C = K初始狀態(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(1) 用三元組來表示（ML , CL , BL）其中0=ML , CL = 3 , BL ∈{ 0 , 1}(3 , 3 , 1) (0 , 0 , 0)(2) 規(guī)則集合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 ) (3) 尋找一個(gè)啟發(fā)式函數(shù)引導(dǎo)規(guī)則的選用 右岸總?cè)藬?shù)6 – ML – CL 兩岸中傳教士數(shù)目=野人數(shù)目f = –∞ 其它f=3 Q01f=2 P02f=1 Q01f=1 Q11f=1 P01f=2 P11（3，3，1）（3，2，0）（2，2，0）（3，1，0）（3，2，1）（3，0，0）f=3 P02（3，1，1）f=2 Q01（1，1，0）f=4 P20（2，2，1）f=2 Q11（1，1，0）f=4 P20（2，2，1）f=2 Q111（0，2，0）f=4 P20（0，3，1）f=3 Q01（0，1，1）f=5 P02（0，2，1）f=4 Q01（0，0，0）f=3 Q01（1，1，1）f=4 Q10 用狀態(tài)空間法求解傳教士和食人者問題例62 傳教士和食人者問題（The Missionaries and Cannibals Problem）。在河的左岸有3個(gè)傳教士、1條船和3個(gè)食人者，傳教士們想用這條船將所有的成員運(yùn)過河去，但是受到以下條件的限制：（1）傳教士和食人者都會(huì)劃船，但船一次最多只能裝運(yùn)兩個(gè)；（2）在任何岸邊食人者數(shù)目都不得超過傳教士，否則傳教士就會(huì)遭遇危險(xiǎn)：被食人者攻擊甚至被吃掉。此外，假定食人者會(huì)服從任何一種過河安排，試規(guī)劃出一個(gè)確保全部成員安全過河的計(jì)劃。解 我們按上述步驟來進(jìn)行求解分析。（1）設(shè)定狀態(tài)變量及確定值域。為了建立這個(gè)問題的狀態(tài)空間，設(shè)左岸的傳教士數(shù)為m，則有m={0，1，2，3}；對(duì)應(yīng)右岸的傳教士數(shù)為3—m；左岸的食人者數(shù)為c，則有c={0，1，2，3}；對(duì)應(yīng)右岸食人者數(shù)為3—c；左岸船數(shù)為b，故又有b={0，1}；右岸的船數(shù)為1b。（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集。問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述，以左岸的狀態(tài)來標(biāo)記，即右岸的狀態(tài)可以不必標(biāo)出。 Sk=（m, c, b）初始狀態(tài)只有一個(gè)：S0=（3， 3， 1），初始狀態(tài)表示全部成員在河的的左岸；目標(biāo)狀態(tài)也只有一個(gè)：Sg=（0，0，0），表示全部成員從河的左岸全部渡河完畢。（3）定義并確定操作集。仍然以河的左岸為基點(diǎn)來考慮，把船從左岸劃向右岸定義為Pij操作。其中，第一下標(biāo)i表示船載的傳教士數(shù)，第二下標(biāo)j表示船載的食人者數(shù)；同理，從右岸將船劃回左
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1