人工智能野人和傳教士問題

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

2、10Pif(ML,CL,BL=1)then(ML,CL-1,BL-1)01Pif(ML,CL,BL=1)then(ML-1,CL-1,BL-1)11Pif(ML,CL,BL=1)then(ML-2,CL,BL-1)20Pif(ML,CL,BL=1)then(ML,CL2,BL-1)02Qif(ML,CL,BL=0)then(ML+1,CL,BL+1)10Qif(ML,CL,BL=0)then(ML,CL+1,BL+1)01Qif(ML,CL,BL=0)then(ML+1,CL+1,BL+1)11Qif（ML,CL,BL=0）then（ML+2,CL+2,BL+1）20Qif（ML,CL,BL=

3、0）then（ML,CL+2,BL+1）02（3） 尋找一個(gè)啟發(fā)式函數(shù)引導(dǎo)規(guī)則的選用右岸總?cè)藬?shù)6-ML-CL兩岸中傳教士數(shù)目=f于人數(shù)目f=-?其它（3，3，1）f=2P110102f=1Pf=2P（2，2，0）（3，2，0）（3，1，0）f=1Q01f=1Q11（3，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）1f=4P20（0，2，0）f=3Q01（0，3，1）f=5 P02(0，1，1)f=4Q0110f=4Q(1，1，1)(0，2，1)f=3Q01f=3Q01(0，0

4、，0)6.2.3用狀態(tài)空間法求解傳教士和食人者問題傳教士和食人者問題(TheMissionariesandCannibalsProblem)。在河的左岸有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=

5、0,1,2,3;對應(yīng)右岸的傳教士數(shù)為3m;左岸的食人者數(shù)為c,則有c=0,1,2,3;對應(yīng)右岸食人者數(shù)為3c;左岸船數(shù)為b,故又有b=0,1;右岸的船數(shù)為1-b。(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ù)，第二下

6、標(biāo)j表示船載的食人者數(shù);同理，從右岸將船劃回左岸稱之為Qij操作，下標(biāo)的定義同前。則共有10種操作，操作集為F=P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20(4) 估計(jì)全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述。在這個(gè)問題世界中，S=3，3，1為初始狀態(tài)，S=Sg=(0，0，0)為目標(biāo)狀態(tài)。031全部的可能狀態(tài)共有32個(gè)，如表61所示。表61傳教士和食人者問題的全部可能狀態(tài)狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,bS03,3,1S84.3.1 S163,3,0S241,3,0S13,2,1S91,2,1S173,2,0S251,2,0

7、S23,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ī)定的條件，我們應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。例如，首先可以劃去岸邊食人者數(shù)目超過傳教士的情況，即,4、S8、S3S20S24S25等6種狀態(tài)是不合法的；其次，應(yīng)該劃去右岸邊食人者數(shù)目超過

8、修道士的情況，即S&S7、S11、S22、S2&S27等情況；余下20種合法狀態(tài)中，又有4種是不可能出現(xiàn)的狀態(tài)；S15和S16不可能出現(xiàn)，因?yàn)榇豢赡芡？吭跓o人的岸邊;S3不可能出現(xiàn)，因?yàn)閭鹘淌坎豢赡茉跀?shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃回來；還應(yīng)該劃去S28,因?yàn)閭鹘淌恳膊豢赡茉跀?shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃向?qū)Π丁？梢?，在狀態(tài)空間中，真正符合題目規(guī)定條件的只有16個(gè)合理狀態(tài)。(5) 當(dāng)狀態(tài)數(shù)量不是很大時(shí)，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。根據(jù)上述分析，共有16個(gè)合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖64所示。S10

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

10、nclude<stdlib.h>#include<ctype.h>#definemaxloop100/*最大層數(shù)，對于不同的擴(kuò)展方法自動(dòng)調(diào)整取值*/#definepristnum3/*初始化時(shí)設(shè)定有3個(gè)野人3個(gè)傳教士，實(shí)際可以改動(dòng)*/#defineslavenum3struct SPQ int sr,pr; /*船運(yùn)行一個(gè)來回后河右岸的野人、傳教士的人數(shù)*/intsl,pl;/*船運(yùn)行一個(gè)來回后河左岸的野人、傳教士的人數(shù)*/intssr,spr;/*回來(由左向右時(shí))船上的人數(shù)*/intsst,spt;/*去時(shí)(由右向左時(shí))船上的人數(shù)*/intloop;/*本結(jié)點(diǎn)所在的

11、層數(shù)*/structSPQ*upnode,*nextnode;/*本結(jié)點(diǎn)的父結(jié)點(diǎn)和同層的下一個(gè)結(jié)點(diǎn)的地址*/spq;intloopnum;/*記錄總的擴(kuò)展次數(shù)*/intopenednum;/*記錄已擴(kuò)展節(jié)點(diǎn)個(gè)數(shù)*/intunopenednum;/*記錄待擴(kuò)展節(jié)點(diǎn)個(gè)數(shù)*/intresultnum;structSPQ*opened;structSPQ*oend;structSPQ*unopened;structSPQ*uend;structSPQ*result;voidinitiate();voidreleasemem();voidshowresult();voidaddtoopened(stru

12、ctSPQ*ntx);intsearch();voidgoon();intstretch(structSPQ*ntx);voidrecorder();voidaddtoopened(structSPQ*ntx)/*擴(kuò)展節(jié)點(diǎn)*/unopened=unopened->nextnode;unopenednum-;if(openednum=0)oend=opened=ntx;oend->nextnode=ntx;oend=ntx;openednum+;voidrecorder()inti,loop;structSPQ*newnode;structSPQ*ntx;loop=oend->

13、loop;ntx=oend;resultnum=0;for(i=0;i<=loop;i+)newnode=(structSPQ*)malloc(sizeof(spq);if(newnode=NULL)printf("n內(nèi)存不夠n");exit(0);newnode->sr=ntx->sr;newnode->pr=ntx->pr;newnode->sl=ntx->sl;newnode->pl=ntx->pl;newnode->sst=ntx->sst;newnode->spt=ntx->spt;ne

14、wnode->ssr=ntx->ssr;newnode->spr=ntx->spr;newnode->nextnode=NULL;ntx=ntx->upnode;if(i=0)result=newnode;newnode->nextnode=result;result=newnode;resultnum+;voidreleasemem()inti;structSPQ*nodefree;for(i=1;i<openednum;i+)nodefree=opened;opened=opened->nextnode;free(nodefree);f

15、or(i=0;i<unopenednum;i+)nodefree=unopened;unopened=unopened->nextnode;free(nodefree);void showresult() /*int i;int fsr , fpr ; /*int fsl , fpl ; /*struct SPQ* nodefree;printf("%dprintf("%dprintf("%dprintf("%d顯示 */在右岸上的人數(shù)*/在左岸上的人數(shù)*/",result -> pr);",result ->

16、 sr);",result -> pl);",result -> sl);for(i=1;i<resultnum;i+)nodefree=result;result=result->nextnode;free(nodefree);printf("nnt左岸人數(shù)船上人數(shù)及方向右岸人數(shù)n");printf("第雎n",i);fpl=result->pl-result->spt+result->spr;fpr=result->pr-result->spr;fsl=result->s

17、l-result->sst+result->ssr;fsr=result->sr-result->ssr;printf("傳教士%8d%8dt<-t%8dn",fpl,result->spt,fpr);printf("野A%8d%8dt<-t%8dn",fsl,result->sst,fsr);printf("傳教士%8d%8dt->t%8dn",result->pl,result->spr,result->pr-result->spr);printf(&q

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

19、e='N')exit(0);intmain()intflag;/*標(biāo)記擴(kuò)展是否成功*/for(;)initiate();flag=search();if(flag=1)recorder();releasemem();showresult();goon();elseprintf("無法找到符合條件的解");releasemem();goon();system("pause");return0;voidinitiate()intx;charchoice;uend=unopened=(structSPQ*)malloc(sizeof(spq);

20、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->pl=0;unopened->sst=0;unopened->spt=0;unopened->ssr=0;unopene

21、d->spr=0;unopened->loop=0;printf("*n");I*printf（"題目：設(shè)有n個(gè)傳教士和m個(gè)野人來到河邊，打算乘一只船從右岸到左岸去。n"）;printf（"該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過傳教士人數(shù)，野人n"）;printf（"就會(huì)把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去n")；printf("I*");printf("n默認(rèn)的n、m值皆為3n");for(;)printf("n是否修

22、改,(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;elseprintf("n輸入值應(yīng)大于0n請重新輸入)printf("n請輸入野人人數(shù)");for(;)scanf("%d",&x);if(x>0)u

23、nopened->sr=x;break;elseprintf("n輸入值應(yīng)大于0n請重新輸入)break;if(choice='N')break;intsearch()intflag;structSPQ*ntx;/*提供將要擴(kuò)展的結(jié)點(diǎn)的指針*/for(;)ntx=unopened;/*從待擴(kuò)展鏈表中提取最前面的一個(gè)*/if(ntx->loop=maxloop)return0;addtoopened(ntx);/*將ntx加入已擴(kuò)展鏈表，并將這個(gè)節(jié)點(diǎn)從待擴(kuò)展鏈表*/flag=stretch(ntx);/*對ntx進(jìn)行擴(kuò)展,返回-1,0,1*/if(flag=

24、1)return1;intstretch(structSPQ*ntx)intfsr,fpr;/*在右岸上的人數(shù)*/intfsl,fpl;/*在左岸上的人數(shù)*/intsst,spt;/*出發(fā)時(shí)在船上的人數(shù)*/intssr,spr;/*返回時(shí)船上的人數(shù)*/structSPQ*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ù)限制*

25、/spt=2-sst;fsr=fsr-sst;fpr=fpr-spt;if(fpr=0)&&(fsr=0)/*搜索成功*/newnode=(structSPQ*)malloc(sizeof(spq);if(newnode=NULL)printf("n內(nèi)存不夠n");exit(0);newnode->upnode=ntx;/*保存父結(jié)點(diǎn)的地址以成鏈表*/newnode->nextnode=NULL;newnode->sr=0;newnode -> pr = 0;newnode->sl=opened->sr;newnode->pl=opened-&