傳教士與野人過河問題

1、傳教士 -野人問題有 N 個傳教士和N 個野人要過河，現(xiàn)在有一條船只能承載K 個人（包括野人） ， K<N ，在任何時刻，如果有野人和傳教士在一起，必須要求傳教士的人數(shù)多于或等于野人的人數(shù)。設(shè) M 為傳教士的人數(shù)，C 為野人的人數(shù)，用狀態(tài)空間發(fā)求解此問題的過程如下：M 、C = N， boat = k，要求 M>=C 且 M+C <= K初始狀態(tài)目標狀態(tài)LRLRM30M03C30C03B10B01(1) 用三元組來表示（ ML , CL , BL ）其中 0<=ML,CL<=3,BL 0,1(3,3,1)(0,0,0)(2) 規(guī)則集合P10if ( ML ,CL

2、, BL=1 )P01if ( ML ,CL , BL=1 )P11if ( ML ,CL , BL=1 )P20if ( ML ,CL , BL=1 )P02if ( ML ,CL , BL=1 )Q10 if ( ML ,CL , BL=0 )Q01 if ( ML ,CL , BL=0 )Q11 if ( ML ,CL , BL=0 )Q20 if ( ML ,CL , BL=0 )Q02 if ( ML ,CL , BL=0 )then ( ML 1 , CL , BL 1 )then ( ML , CL 1 , BL 1 )then ( ML 1 , CL1 , BL 1 )then

3、 ( ML 2 , CL , BL 1 )then ( ML , CL 2 , BL 1 )then ( ML+1 , CL , BL+1 )then ( ML , CL+1 , BL +1 )then ( ML+1 , CL +1, BL +1 )then ( ML+2 , CL +2, BL +1 )then ( ML , CL +2, BL +1 )(3) 尋找一個啟發(fā)式函數(shù)引導規(guī)則的選用右岸總?cè)藬?shù) 6 ML CL兩岸中傳教士數(shù)目 >=野人數(shù)目f =其它（ 3， 3， 1）f=2P11f=1P01f=2P02（2，2，0）（3，2，0）（3， 1，0）f=1Q01f=1Q11（ 3

4、， 2， 1）f=3P02（ 3， 0， 0）f=2Q01（ 3， 1， 1）f=4P20（ 1， 1， 0）f=2Q11（ 2， 2，1）f=4P20（ 1， 1， 0）f=2Q11（ 2， 2， 1）f=4P20（ 0， 2， 0）f=3Q01（ 0， 3， 1）f=5P02（ 0， 1， 1）f=4Q01f=4Q10（ 0，2， 1）（ 1， 1，1）f=3Q01f=3Q01（ 0， 0， 0）用狀態(tài)空間法求解傳教士和食人者問題例 6-2 傳教士和食人者問題（ The Missionaries and Cannibals Problem ）。在河的左岸有3個傳教士、 1 條船和 3 個食

5、人者，傳教士們想用這條船將所有的成員運過河去，但是受到以下條件的限制： （1）傳教士和食人者都會劃船，但船一次最多只能裝運兩個；（2）在任何岸邊食人者數(shù)目都不得超過傳教士，否則傳教士就會遭遇危險：被食人者攻擊甚至被吃掉。此外，假定食人者會服從任何一種過河安排，試規(guī)劃出一個確保全部成員安全過河的計劃。解 我們按上述步驟來進行求解分析。（ 1）設(shè)定狀態(tài)變量及確定值域。為了建立這個問題的狀態(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 ；

6、右岸的船數(shù)為 1-b。（ 2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標狀態(tài)集。問題的狀態(tài)可以用一個三元數(shù)組來描述，以左岸的狀態(tài)來標記， 即右岸的狀態(tài)可以不必標出。Sk =（m, c, b）初始狀態(tài)只有一個：S =（3，3， 1），初始狀態(tài)表示全部成員在河的的左岸；0目標狀態(tài)也只有一個：S =（ 0，0， 0），表示全部成員從河的左岸全部渡河完畢。g（ 3）定義并確定操作集。P 操作。其中，第一下標仍然以河的左岸為基點來考慮，把船從左岸劃向右岸定義為iji 表示船載的傳教士數(shù)，第二下標j表示船載的食人者數(shù)；同理，從右岸將船劃回左岸稱之為 Qij 操作，下標的定義同前。則共有10 種操作，操作集為F=

7、P 01，P10， P11，P02，P20， Q01，Q10， Q11， Q02， Q20（ 4）估計全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述。在這個問題世界中， S0=3 ， 3， 1 為初始狀態(tài)， S31=Sg=（ 0， 0， 0）為目標狀態(tài)。全部的可能狀態(tài)共有 32 個，如表 6 1 所示。表 61傳教士和食人者問題的全部可能狀態(tài)狀態(tài)m, c, b狀態(tài)m, c, b狀態(tài)m, c, b狀態(tài)m, c, bS3,3,1S1,3,1S3,3,0S1,3,0081624S13,2,1S91,2,1S173,2,0S251,2,0S23,1,1S101,1,1S183,1,0S261,

8、1,0S33,0,1S111,0,1S193,0,0S271,0,0S2,3,1S0,3,1S2,3,0S0,3,04122028S2,2,1S0,2,1S2,2,0S0,2,05132129S62,1,1S140,1,1S222,1,0S300,1,0S72,0,1S150,0,1S232,0,0S310,0,0值得注意的是按照題目規(guī)定的條件，我們應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。例如，首先可以劃去岸邊食人者數(shù)目超過傳教士的情況，即4、S8、 S9、S20、S24、S25 等 6 種狀態(tài)是不合法的；其次，應(yīng)該劃去右岸邊食人者數(shù)目超過修道士的情況，即S6、S7、 S11、S22

9、、S23、S27 等情況；余下 20 種合法狀態(tài)中，又有4 種是不可能出現(xiàn)的狀態(tài)；S和 S 不可能出現(xiàn)，因為船不可能?？吭跓o人的岸邊；S 不可能出現(xiàn)，因為傳教士不可15163S ，因為傳教士也不可能在數(shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃回來；還應(yīng)該劃去28能在數(shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃向?qū)Π?。可見，在狀態(tài)空間中， 真正符合題目規(guī)定條件的只有 16 個合理狀態(tài)。（ 5） 當狀態(tài)數(shù)量不是很大時，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。根據(jù)上述分析， 共有 16 個合法狀態(tài)和允許的操作， 可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖 6 4 所示。18S1210S24S

10、S0231011003111101112001S2902 10S17111S1401S01331320321311020010011000S0S2S02012030S131321S02S011122010300221021SS195圖 64 傳教士和食人者問題的狀態(tài)空間如圖 6 4 所示，由于劃船操作是可逆的，所以圖中狀態(tài)節(jié)點間用雙向箭頭連接，箭頭旁邊所標的數(shù)字表示了或操作的下標，即分別表示船載的傳教士數(shù)和食人者數(shù)。這樣，任何一條從 S0 到達 S31 的路徑都是該問題的解。這樣，通過運用狀態(tài)空間表示法就解決了傳教士和食人者問題的求解。源代碼：#include <stdio.h>#

11、include <stdlib.h>#include <ctype.h>#define maxloop 100 /*最大層數(shù)，對于不同的擴展方法自動調(diào)整取值#define pristnum 3 /* 初始化時設(shè)定有3個野人 3個傳教士，實際可以改動#define slavenum 3*/*/struct SPQint sr,pr; /*船運行一個來回后河右岸的野人、傳教士的人數(shù)*/int sl,pl; /*船運行一個來回后河左岸的野人、傳教士的人數(shù)*/int ssr,spr; /*回來（由左向右時）船上的人數(shù)*/int sst,spt; /*去時（由右向左時）船上的人數(shù)

12、*/int loop; /*本結(jié)點所在的層數(shù)*/struct SPQ *upnode ,*nextnode;/*本結(jié)點的父結(jié)點和同層的下一個結(jié)點的地址spq;int loopnum;/*記錄總的擴展次數(shù)*/*/int openednum;/*記錄已擴展節(jié)點個數(shù)*/int unopenednum;/*記錄待擴展節(jié)點個數(shù)*/int resultnum;struct SPQ *opened;struct SPQ *oend;struct SPQ *unopened;struct SPQ *uend;struct SPQ *result;void initiate();void releasemem(

13、);void showresult();void addtoopened(struct SPQ *ntx);int search();void goon();int stretch(struct SPQ* ntx);void recorder();void addtoopened(struct SPQ *ntx) /* 擴展節(jié)點 */unopened = unopened -> nextnode;unopenednum-;if (openednum = 0 )oend = opened = ntx;oend -> nextnode = ntx;oend = ntx;openednu

14、m+;void recorder()int i , loop;struct SPQ *newnode;struct SPQ *ntx;loop = oend -> loop;ntx = oend;resultnum = 0;for( i = 0 ; i <= loop ; i+ )newnode = (struct SPQ*) malloc (sizeof(spq);if(newnode=NULL)printf("n 存不夠！ n");exit(0);newnode -> sr = ntx -> sr;newnode -> pr = ntx -

15、> pr;newnode -> sl = ntx -> sl;newnode -> pl = ntx -> pl;newnode -> sst = ntx -> sst;newnode -> spt = ntx -> spt;newnode -> ssr = ntx -> ssr;newnode -> spr = ntx -> spr;newnode -> nextnode = NULL;ntx = ntx -> upnode;if(i = 0)result = newnode;newnode ->

16、 nextnode = result;result = newnode;resultnum+;void releasemem()int i;struct SPQ* nodefree;for ( i = 1 ; i < openednum ; i+ )nodefree = opened;opened = opened -> nextnode;free(nodefree);for ( i = 0 ; i < unopenednum ; i+ )nodefree = unopened;unopened = unopened -> nextnode;free(nodefree)

17、;void showresult()/* 顯示 */int i;int fsr , fpr ; /*在右岸上的人數(shù)*/int fsl , fpl ; /*在左岸上的人數(shù)*/struct SPQ* nodefree;printf("%d個傳教士 ",result -> pr);printf("%d個野人",result -> sr);printf("%d個傳教士 ",result -> pl);printf("%d個野人",result -> sl);for ( i = 1 ; i <

18、resultnum ; i+ )nodefree = result;result = result -> nextnode;free(nodefree);printf("nnt左岸人數(shù)船上人數(shù)及方向右岸人數(shù) n");printf(" 第 %d 輪 n",i);fpl = result -> pl - result -> spt + result -> spr;fpr = result -> pr - result -> spr;fsl = result -> sl - result -> sst + res

19、ult -> ssr;fsr = result -> sr - result -> ssr;printf(" 傳教士 %8d%8dt<-t%8dn",fpl,result -> spt,fpr);printf(" 野人%8d%8dt<-t%8dn",fsl,result -> sst,fsr);printf(" 傳教士 %8d%8dt->t%8dn",result -> pl,result -> spr,result -> pr - result -> spr);

20、 printf(" 野 人%8d%8dt->t%8dn",result -> sl,result -> ssr,result -> sr - result -> ssr);printf("n 全體傳教士和野人全部到達對岸");free(result);void goon() /* 循環(huán)操作選擇*/char choice;for(;)printf(" 是否繼續(xù)？ (Y/N)n");scanf ("%s" , &choice);choice=toupper(choice);if(c

21、hoice='Y')break;if(choice='N')exit(0);int main()int flag; /*標記擴展是否成功*/for( ; ; )initiate();flag = search ();if(flag = 1)recorder();releasemem();showresult();goon();elseprintf(" 無法找到符合條件的解");releasemem();goon();system("pause");return 0;void initiate()int x;char cho

22、ice;uend = unopened = (struct SPQ*)malloc(sizeof(spq);if(uend=NULL)printf("n存不夠！n");exit(0);unopenednum=1;openednum=0;unopened -> upnode = unopened; /*保存父結(jié)點的地址以成鏈表*/unopened -> nextnode = unopened;unopened -> sr = slavenum;unopened -> pr = pristnum;unopened -> sl = 0;unopene

23、d -> pl = 0;unopened -> sst = 0;unopened -> spt = 0;unopened -> ssr = 0;unopened -> spr = 0;unopened -> loop = 0;printf("*n");printf("printf("printf("題目：設(shè)有n 個傳教士和m 個野人來到河邊，打算乘一只船從右岸到左岸去。該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去n"

24、);n");n");printf("*");printf("n默認的n、 m 值皆為3n");for(;)printf("n是否修改？(Y/N)");scanf("%s",&choice);choice=toupper(choice);if(choice='Y')printf("n請輸入傳教士人數(shù)");for(;)scanf("%d",&x);if(x>0)unopened -> pr = x;break;els

25、e printf("n輸入值應(yīng)大于0！ n 請重新輸入");printf("n請輸入野人人數(shù)");for(;)scanf("%d",&x);if(x>0)unopened -> sr = x;break;else printf("n輸入值應(yīng)大于0！ n 請重新輸入");break;if(choice='N')break;int search()int flag;struct SPQ *ntx; /*提供將要擴展的結(jié)點的指針*/for( ; )ntx = unopened; /*從

26、待擴展鏈表中提取最前面的一個*/if(ntx->loop = maxloop)return 0;addtoopened(ntx); /*將 ntx 加入已擴展鏈表，并將這個節(jié)點從待擴展鏈表中去掉flag = stretch(ntx); /*對 ntx 進行擴展 ,返回 -1,0,1 */if(flag = 1)return 1;*/int stretch(struct SPQ *ntx)int fsr , fpr ; /*在右岸上的人數(shù)*/int fsl , fpl ; /*在左岸上的人數(shù)*/int sst , spt ; /*出發(fā)時在船上的人數(shù)*/int ssr , spr ; /*返

27、回時船上的人數(shù)*/struct SPQ *newnode;for (sst = 0 ; sst <= 2 ; sst+) /*討論不同的可能性并判斷是否符合條件*/fsr = ntx -> sr;fpr = ntx -> pr;fsl = ntx -> sl;fpl = ntx -> pl;if (sst <= fsr) && ( 2 - sst) <= fpr)/*滿足人數(shù)限制 */spt = 2 - sst;fsr = fsr - sst;fpr = fpr - spt;if(fpr = 0) && (fsr = 0

28、)/*搜索成功 */newnode = (struct SPQ*) malloc (sizeof(spq);if(newnode=NULL)printf("n 存不夠！ n");exit(0);newnode -> upnode = ntx; /*保存父結(jié)點的地址以成鏈表*/newnode -> nextnode = NULL;newnode -> sr = 0;newnode -> pr = 0;newnode -> sl = opened -> sr;newnode -> pl = opened -> pr;newnode -> sst = sst;newnode -> spt = spt