傳教士與野人過河問題-全文預(yù)覽
【正文】 條從S0到達S31的路徑都是該問題的解?？梢?，在狀態(tài)空間中，真正符合題目規(guī)定條件的只有16個合理狀態(tài)。在這個問題世界中，S0={3，3，1}為初始狀態(tài)，S31=Sg=（0，0，0）為目標狀態(tài)。（3）定義并確定操作集。為了建立這個問題的狀態(tài)空間，設(shè)左岸的傳教士數(shù)為m，則有m={0，1，2，3}；對應(yīng)右岸的傳教士數(shù)為3—m；左岸的食人者數(shù)為c，則有c={0，1，2，3}；對應(yīng)右岸食人者數(shù)為3—c；左岸船數(shù)為b，故又有b={0，1}；右岸的船數(shù)為1b。在河的左岸有3個傳教士、1條船和3個食人者，傳教士們想用這條船將所有的成員運過河去，但是受到以下條件的限制：（1）傳教士和食人者都會劃船，但船一次最多只能裝運兩個；（2）在任何岸邊食人者數(shù)目都不得超過傳教士，否則傳教士就會遭遇危險：被食人者攻擊甚至被吃掉。設(shè)M為傳教士的人數(shù)，C為野人的人數(shù)，用狀態(tài)空間發(fā)求解此問題的過程如下：M、C = N，boat = k，要求M=C且M+C = K初始狀態(tài) 目標狀態(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) 尋找一個啟發(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）。（1）設(shè)定狀態(tài)變量及確定值域。 Sk=（m, c, b）初始狀態(tài)只有一個：S0=（3， 3， 1），初始狀態(tài)表示全部成員在河的的左岸；目標狀態(tài)也只有一個：Sg=（0，0，0），表示全部成員從河的左岸全部渡河完畢。則共有10種操作，操作集為 F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}（4）估計全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述。例如，首先可以劃去岸邊食人者數(shù)目超過傳教士的情況，即ＳSSSS2S25等6種狀態(tài)是不合法的；其次，應(yīng)該劃去右岸邊食人者數(shù)目超過修道士的情況，即SSS1S2S2S27等情況；余下20種合法狀態(tài)
法律信息相關(guān)推薦
鄂ICP備17016276號-1