傳教士和野人問題

1、狀態(tài)空間法詳解傳教士和野人問題傳教士和野人問題（TheMissionariesandCannibalsProblem）在河的左岸有三個(gè)傳教士、一條船和三個(gè)野人，傳教士們想用這條船將所有的成員都運(yùn)過河去，但是受到以下條件的限制：教士和野人都會(huì)劃船，但船一次最多只能裝運(yùn)兩個(gè)；在任何岸邊野人數(shù)目都不得超過傳教士，否則傳教士就會(huì)遭遇危險(xiǎn)：被野人攻擊甚至被吃掉。此外，假定野人會(huì)服從任何一種過河安排，試規(guī)劃出一個(gè)確保全部成員安全過河的計(jì)劃。（1）設(shè)定狀態(tài)變量及確定值域。為了建立這個(gè)問題的狀態(tài)空間，設(shè)左岸傳教士數(shù)為m,則m=0,1,2,3；對(duì)應(yīng)右岸的傳教士數(shù)為3m；左岸的野人數(shù)為c,則有c=0,1,2,3；

2、對(duì)應(yīng)右岸野人數(shù)為3c；左岸船數(shù)為b,故又有b=0,1,右岸的船數(shù)為1b.（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集。問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述,以左岸的狀態(tài)來標(biāo)記,即Sk=（m,c,b）,右岸的狀態(tài)可以不必標(biāo)出。初始狀態(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ù)；同理，從右岸將船劃回左岸稱之為Qij操作,下標(biāo)的定義同前。則共有10種操作,操作集為

3、F=P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q204）估計(jì)全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述之。在這個(gè)問題世界中，SO=（3,3,1）為初始狀態(tài)，S31=Sg=（0,0,0）為目標(biāo)狀態(tài)。全部的可能狀態(tài)共有32個(gè)，如表所示。狀離B上飛iLdLC.b岀%33LSBS244-3Si3214-i-l-SI7-311sto1LLER330S26】ieS15300JU1311!B132jJ00常S120JI-0221SLi02Isn22&彌D2CC-fAllAjtC=r.ninqrLrJ.LoilLJ!1UJIsftA1表1傳教士和野人問題的全部可能狀態(tài)

4、注意：按題目規(guī)定條件，應(yīng)劃去非法狀態(tài)，從而加快搜索效率。1）首先可以劃去左岸邊野人數(shù)目超過傳教士的情況，即S4、S8、S9、S20、S24、S25等6種狀態(tài)是不合法的；2）應(yīng)劃去右岸邊野人數(shù)目超過修道士的情況，即S6、S7、S11、S22、S23、S27等情況；3）應(yīng)劃去4種不可能出現(xiàn)狀態(tài)：劃去S15和S16船不可能停靠在無人的岸邊；劃去S3傳教士不可能在數(shù)量占優(yōu)勢的野人眼皮底下把船安全地劃回來；劃去S28傳教士也不可能在數(shù)量占優(yōu)勢的野人眼皮底下把船安全地劃向?qū)Π??？梢姡跔顟B(tài)空間中，真正符合題目規(guī)定條件的只有16個(gè)合理狀態(tài)。（5）當(dāng)狀態(tài)數(shù)量不是很大時(shí)，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)

5、空間圖搜索求解。根據(jù)上述分析，共有16個(gè)合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖所示。圖2傳教士和野人問題的狀態(tài)空間任何一條從SO到達(dá)S31的路徑都是該問題的解。A*算法詳解傳教士和野人問題評(píng)估函數(shù)為f=h+d=M+N-2*B+d。M表示左岸的傳教士的人數(shù)，N表示左岸野人的數(shù)目，B取值為0或1。1表示船在左岸，0表示船在右岸。d表示節(jié)點(diǎn)的深度。下面來證明h(n)=M+C-2B是滿足A*條件的。分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個(gè)人將船送回來。這樣，船一個(gè)來回可以運(yùn)過河2人，而船仍然在左岸。而最

6、后剩下的三個(gè)人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡(M+N-3)*2+1次。其中分子上的一3表示剩下三個(gè)留待最后一次運(yùn)過去。除以2是因?yàn)橐粋€(gè)來回可以運(yùn)過去2人，需要(M+N-3)/2個(gè)來回，而來回?cái)?shù)不能是小數(shù)，需要向上取整，這個(gè)用符號(hào)表示。而乘以2是因?yàn)橐粋€(gè)來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的1，則表示將剩下的3個(gè)運(yùn)過去，需要一次擺渡。化簡有：M+N-2。再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個(gè)人將船運(yùn)到左岸。因此對(duì)于狀態(tài)(M,N,0)來說，其所需要的最少擺渡數(shù)，相當(dāng)于船在左岸時(shí)狀態(tài)(M+1,N，1)或(M,N+1，1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因此所需要的最少擺渡數(shù)為：(M+N+1)-2+1。其中(M+N+1)的+1表示送船回到左岸的那個(gè)人，而最后邊的1，表示送船到左岸時(shí)的一次擺渡?；営校?M+N+1)-2+1=M+N。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個(gè)式子表示為：M+N-2B。其中B=1表示船在左岸