傳教士與野人過(guò)河問(wèn)題

1、傳教士-野人問(wèn)題有N個(gè)傳教士和N個(gè)野人要過(guò)河，現(xiàn)在有一條船只能承載K個(gè)人（包括野人），K=C且M+C = K初始狀態(tài)目標(biāo)狀態(tài)LRLRM30M03C30C03B10B01(1) 用三元組來(lái)表示（ML , CL , BL）其中0=ML , CL =野人數(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

2、）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 Q106.2.3 用狀態(tài)空間法求解傳教士和食人者問(wèn)題例6-2 傳教士和食人者問(wèn)題（The Missionaries and Cannibals Problem）。在河的左岸有3個(gè)傳教士、1條船和3個(gè)食人者，傳教士們想用這條船將所有的成員運(yùn)過(guò)河去，但是受到以下條件的限制：（1）傳教士和食人者都會(huì)劃船，但船一次最多只能裝運(yùn)兩個(gè)；（2）在任何岸邊食人者數(shù)目都不得超過(guò)傳教士，否則傳教士就會(huì)遭遇危險(xiǎn)：被食人者攻擊甚至被吃掉。此外，假定食人者會(huì)服從任何一種過(guò)

3、河安排，試規(guī)劃出一個(gè)確保全部成員安全過(guò)河的計(jì)劃。解 我們按上述步驟來(lái)進(jìn)行求解分析。（1）設(shè)定狀態(tài)變量及確定值域。為了建立這個(gè)問(wèn)題的狀態(tài)空間，設(shè)左岸的傳教士數(shù)為m，則有m=0，1，2，3；對(duì)應(yīng)右岸的傳教士數(shù)為3m；左岸的食人者數(shù)為c，則有c=0，1，2，3；對(duì)應(yīng)右岸食人者數(shù)為3c；左岸船數(shù)為b，故又有b=0，1；右岸的船數(shù)為1-b。（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集。問(wèn)題的狀態(tài)可以用一個(gè)三元數(shù)組來(lái)描述，以左岸的狀態(tài)來(lá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，

4、0，0），表示全部成員從河的左岸全部渡河完畢。（3）定義并確定操作集。仍然以河的左岸為基點(diǎn)來(lái)考慮，把船從左岸劃向右岸定義為Pij操作。其中，第一下標(biāo)i表示船載的傳教士數(shù)，第二下標(biāo)j表示船載的食人者數(shù)；同理，從右岸將船劃回左岸稱(chēng)之為Qij操作，下標(biāo)的定義同前。則共有10種操作，操作集為 F=P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20（4）估計(jì)全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述。在這個(gè)問(wèn)題世界中，S0=3，3，1為初始狀態(tài)，S31=Sg=（0，0，0）為目標(biāo)狀態(tài)。全部的可能狀態(tài)共有32個(gè)，如表61所示。 表61 傳教士和食人者問(wèn)題的全部可能狀

5、態(tài)狀 態(tài)m, c, b狀 態(tài)m, c, b狀 態(tài)m, c, b狀 態(tài) m, c, bS03,3,1S81,3,1S163,3,0S241,3,0S13,2,1S91,2,1S173,2,0S251,2,0S23,1,1S101,1,1S183,1,0S261,1,0S33,0,1S111,0,1S193,0,0S271,0,0S42,3,1S120,3,1S202,3,0S280,3,0S52,2,1S130,2,1S212,2,0S290,2,0S62,1,1S140,1,1S222,1,0S300,1,0S72,0,1S150,0,1S232,0,0S310,0,0值得注意的是按照題目規(guī)定

6、的條件，我們應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。例如，首先可以劃去岸邊食人者數(shù)目超過(guò)傳教士的情況，即4、S8、S9、S20、S24、S25等6種狀態(tài)是不合法的；其次，應(yīng)該劃去右岸邊食人者數(shù)目超過(guò)修道士的情況，即S6、S7、S11、S22、S23、S27等情況；余下20種合法狀態(tài)中，又有4種是不可能出現(xiàn)的狀態(tài)；S15和S16不可能出現(xiàn)，因?yàn)榇豢赡芡？吭跓o(wú)人的岸邊；S3不可能出現(xiàn)，因?yàn)閭鹘淌坎豢赡茉跀?shù)量占優(yōu)勢(shì)的食人者眼皮底下把船安全地劃回來(lái)；還應(yīng)該劃去S28，因?yàn)閭鹘淌恳膊豢赡茉跀?shù)量占優(yōu)勢(shì)的食人者眼皮底下把船安全地劃向?qū)Π??？梢?jiàn)，在狀態(tài)空間中，真正符合題目規(guī)定條件的只有16個(gè)合理狀

7、態(tài)。（5） 當(dāng)狀態(tài)數(shù)量不是很大時(shí)，按問(wèn)題的有序元組畫(huà)出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。 根據(jù)上述分析，共有16個(gè)合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問(wèn)題的狀態(tài)空間圖，如圖64所示。 021111010320220321311020S0S17S2111011002S1S2200111013310120S290210S30S140119300S5221S10S12031S24110S1831002S13000圖64 傳教士和食人者問(wèn)題的狀態(tài)空間如圖64所示，由于劃船操作是可逆的，所以圖中狀態(tài)節(jié)點(diǎn)間用雙向箭頭連接，箭頭旁邊所標(biāo)的數(shù)字表示了或操作的下標(biāo)，即分別表示

8、船載的傳教士數(shù)和食人者數(shù)。這樣，任何一條從S0到達(dá)S31的路徑都是該問(wèn)題的解。這樣，通過(guò)運(yùn)用狀態(tài)空間表示法就解決了傳教士和食人者問(wèn)題的求解。源代碼：#include #include #include #define maxloop 100 /* 最大層數(shù)，對(duì)于不同的擴(kuò)展方法自動(dòng)調(diào)整取值 */ #define pristnum 3 /*初始化時(shí)設(shè)定有3個(gè)野人3個(gè)傳教士，實(shí)際可以改動(dòng)*/ #define slavenum 3struct SPQ int sr,pr; /* 船運(yùn)行一個(gè)來(lái)回后河右岸的野人、傳教士的人數(shù) */ int sl,pl; /* 船運(yùn)行一個(gè)來(lái)回后河左岸的野人、傳教士的人數(shù) *

9、/ int ssr,spr; /* 回來(lái)（由左向右時(shí)）船上的人數(shù) */ int sst,spt; /* 去時(shí)（由右向左時(shí)）船上的人數(shù) */ int loop; /* 本結(jié)點(diǎn)所在的層數(shù) */ struct SPQ *upnode ,*nextnode;/* 本結(jié)點(diǎn)的父結(jié)點(diǎn)和同層的下一個(gè)結(jié)點(diǎn)的地址 */ spq; int loopnum;/* 記錄總的擴(kuò)展次數(shù) */ int openednum;/* 記錄已擴(kuò)展節(jié)點(diǎn)個(gè)數(shù) */ int unopenednum;/* 記錄待擴(kuò)展節(jié)點(diǎn)個(gè)數(shù) */ int resultnum; struct SPQ *opened; struct SPQ *oend; st

10、ruct SPQ *unopened; struct SPQ *uend; struct SPQ *result; void initiate(); void releasemem(); void showresult(); void addtoopened(struct SPQ *ntx); int search(); void goon(); int stretch(struct SPQ* ntx); void recorder(); void addtoopened(struct SPQ *ntx) /*擴(kuò)展節(jié)點(diǎn)*/ unopened = unopened - nextnode; uno

11、penednum-; if (openednum = 0 ) oend = opened = ntx; oend - nextnode = ntx; oend = ntx; openednum+; void recorder() int i , loop; struct SPQ *newnode; struct SPQ *ntx; loop = oend - loop; ntx = oend; resultnum = 0; for( i = 0 ; i sr = ntx - sr; newnode - pr = ntx - pr; newnode - sl = ntx - sl; newnod

12、e - 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 - nextnode = result; result = newnode; resultnum+; void releasemem() int i; struct SPQ* no

13、defree; for ( i = 1 ; i nextnode; free(nodefree); for ( i = 0 ; i nextnode; free(nodefree); void showresult() /*顯示*/ int i; int fsr , fpr ; /* 在右岸上的人數(shù) */ int fsl , fpl ; /* 在左岸上的人數(shù) */ struct SPQ* nodefree; printf(%d個(gè)傳教士,result - pr); printf(%d個(gè)野人 ,result - sr); printf(%d個(gè)傳教士,result - pl); printf(%d個(gè)

14、野人 ,result - sl); for ( i = 1 ; i 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 + result - ssr; fsr = result - sr - result - ssr; printf(傳教士%8d%8dt spt,fpr)

15、; printf(野 人%8d%8dt sst,fsr); printf(傳教士%8d%8dt-t%8dn,result - pl,result - spr,result - pr - result - spr); printf(野 人%8d%8dt-t%8dn,result - sl,result - ssr,result - sr - result - ssr); printf(n全體傳教士和野人全部到達(dá)對(duì)岸); free(result); void goon() /*循環(huán)操作選擇*/ char choice; for(;) printf(是否繼續(xù)？(Y/N)n); scanf (%s ,

16、 &choice); choice=toupper(choice); if(choice=Y)break; if(choice=N)exit(0); int main() int flag; /* 標(biāo)記擴(kuò)展是否成功 */ for( ; ; ) initiate(); flag = search (); if(flag = 1) recorder(); releasemem(); showresult(); goon(); else printf(無(wú)法找到符合條件的解); releasemem(); goon(); system(pause); return 0; void initiate()

17、 int x; char choice; uend = unopened = (struct SPQ*)malloc(sizeof(spq); if(uend=NULL) printf(n內(nèi)存不夠！n); exit(0); unopenednum=1; openednum=0; unopened - upnode = unopened; /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ unopened - nextnode = unopened; unopened - sr = slavenum; unopened - pr = pristnum; unopened - sl = 0; unopened

18、 - pl = 0; unopened - sst = 0; unopened - spt = 0; unopened - ssr = 0; unopened - spr = 0; unopened - loop = 0; printf(*n); printf(題目：設(shè)有n個(gè)傳教士和m個(gè)野人來(lái)到河邊，打算乘一只船從右岸到左岸去。n); printf(該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，野人n); printf(就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全的把所有人都渡過(guò)河去n); printf(*); printf(n默認(rèn)的n、m值皆為3n); for(;) print

19、f(n是否修改？(Y/N); scanf(%s,&choice); choice=toupper(choice); if(choice=Y) printf(n請(qǐng)輸入傳教士人數(shù)); for(;) scanf(%d,&x); if(x0) unopened - pr = x; break; else printf(n輸入值應(yīng)大于0！n請(qǐng)重新輸入); printf(n請(qǐng)輸入野人人數(shù)); for(;) scanf(%d,&x); if(x0) unopened - sr = x; break; else printf(n輸入值應(yīng)大于0！n請(qǐng)重新輸入); break; if(choice=N)break

20、; int search() int flag; struct SPQ *ntx; /* 提供將要擴(kuò)展的結(jié)點(diǎn)的指針 */ for( ; ) ntx = unopened; /* 從待擴(kuò)展鏈表中提取最前面的一個(gè) */ if(ntx-loop = maxloop) return 0; addtoopened(ntx); /* 將ntx加入已擴(kuò)展鏈表，并將這個(gè)節(jié)點(diǎn)從待擴(kuò)展鏈表中去掉 */ flag = stretch(ntx); /* 對(duì)ntx進(jìn)行擴(kuò)展,返回-1,0,1 */ if(flag = 1) return 1; int stretch(struct SPQ *ntx) int fsr ,

21、fpr ; /* 在右岸上的人數(shù) */ int fsl , fpl ; /* 在左岸上的人數(shù) */ int sst , spt ; /* 出發(fā)時(shí)在船上的人數(shù) */ int ssr , spr ; /* 返回時(shí)船上的人數(shù) */ struct SPQ *newnode; for (sst = 0 ; sst sr; fpr = ntx - pr; fsl = ntx - sl; fpl = ntx - pl; if (sst = fsr) & ( 2 - sst) upnode = ntx; /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ newnode - nextnode = NULL; newnode - sr = 0; newnode - pr = 0; newnode - sl = opened - sr; newnode - pl = opened - pr; newnode - sst = sst; newnode - spt = spt; newnode - ssr = 0; newnode - spr = 0; newnode - loop = ntx - loop + 1;