人工智能野人和传教士问题

1、传教士野人问题有N个传教士和N个野人要过河，现在有一条船只能承载K个人(包括野人)，KvN,在 任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。设M为传教士的人数，C为野人的人数，用状态空间发求解此问题的过程如下：M、C 二 N, boat = k,要求 M=C 且 M+C v二 K初始状态U标状态其中 0=ML.CL=野人数口其它(3, 3, 1)(3, 2, 1)I f=3 P()2(3, 0, 0)I f=2 Ooi (3, 1, 1)I f=4 P20(1, 1, 0)I f=2 On(2, 2, 1)I f=4 P20(1, 1, 0)I f=2 On(

2、2, 2, 1)I f=4 P20(0, 2, 0)I f=3 Ooi (0,卜 1)I f=5 P()2用状态空间法求解传教士和食人者问题传教士和食人者问题（The Missionaries and Cannibals Problem）在河的左岸有3个传 教七、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条 件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食 人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外， 假泄食人者会服从任何一种过河安排，试规划岀一个确保全部成员安全过河的计划。解我们按上述步骤来

3、进行求解分析。（1）设定状态变量及确定值域。为了建立这个问题的状态空间，设左岸的传教士数为m,则有m =0. 1, 2, 3：对应右岸的传教士数为3-m：左岸的食人者数为c,则有c=0, 1, 2, 3： 对应右岸食人者数为3-c：左岸船数为b,故又有b=0, 1：右岸的船数为1-b。（2）确定状态组，分别列出初始状态集和目标状态集。问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即右岸的状态可以不必 标出。Sk= （m. c, b）初始状态只有一个：So= （3,3,1）,初始状态表示全部成员在河的的左岸；目标状态也只有一个：Ss= （0, 0, 0）,表示全部成员从河的左岸全部渡河

4、完毕。（3）泄义并确定操作集。仍然以河的左岸为基点来考虑，把船从左岸划向右岸泄义为Pij操作。其中，第一下标 i表示船载的传教士数，第二下标j表示船载的食人者数：同理，从右岸将船划回左岸称之 为Qij操作，下标的建义同前。则共有10种操作，操作集为F=Poi, Pio, Pii, P02, P20, Q01, Q10, Q11, Q02, Q20）（4）估计全部的状态空间数，并尽可能列岀全部的状态空间或予以描述。在这个问题世界中，S（尸3, 3, 1为初始状态，S3i=Ss= （0, 0, 0）为目标状态。 全部的可能状态共有32个，如表6-1所示。表6-1传教士和食人者问题的全部可能状态状态

5、m, c, b状态m, c, b状态m, c, b状态m. c, bSo3.3Ss1.3.1S163,3,0S24130Si321S9121S173,2,0S25120S23.1.1Sio1丄1S1830S261丄0S3301Sil1.0.1S193,0,0S271A0S42.3S120.3S202,3,0S280,3,0S5221S13021S212,2,0S29020S62.1.1S140.1.1S222.1.0S?o0丄0S72A1S150A1S232,0.0S310.0,0值得注意的是按照题目规龙的条件，我们应该划去不合法的状态，这样可以加快搜索 求解的效率。例如，首先可以划去岸边食人

6、者数目超过传教士的情况，即S4、S8、S9、S20、 S24、S25等6种状态是不合法的：英次，应该划去右岸边食人者数目超过修道士的情况，即 S6、S7、S1K S22、S23、S27等情况：余下20种合法状态中，又有4种是不可能岀现的状态; S15和S16不可能出现，因为船不可能停靠在无人的岸边：S3不可能岀现，因为传教七不可 能在数量占优势的食人者眼皮底下把船安全地划回来：还应该划去S28,因为传教士也不可 能在数呈:占优势的食人者眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题 目规左条件的只有16个合理状态。（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态

7、空间图 搜索求解。根据上述分析，共有16个合法状态和允许的操作，可以划出传教士和食人者问题的状 态空间图，如图64所示。331320321311020010011000So 11 S：i/ S2/ 1 /4S.220/ 10300221寸 021 rSl9S5图6-4传教士和食人者问题的状态空间如图64所示，由于划船操作是可逆的，所以图中状态节点间用双向箭头连接，箭头 旁边所标的数字表示了P或Q操作的下标，即分别表示船载的传教七数和食人者数。这样, 任何一条从So到达S31的路径都是该问题的解。这样，通过运用状态空间表示法就解决了传教士和食人者问题的求解。源代码：#includc o#incl

8、ude o#includc o#define maxloop 100/*最大层数，对于不同的扩展方法自动调整取值*/#dcfinc pristnum 3 /*初始化时设定有3个野人3个传教士，实际可以改动*/#define slavenuin 3struct SPQ intsr.pr;/*船运行一个来回后河右岸的野人、传教士的人数*/imsl.pl;/*船运行一个来回后河左岸的野人、传教士的人数*/int ssr,spr;/*回来（由左向右时）船上的人数*/int sst,spt;/*去时（由右向左时）船上的人数*/int loop; /*本结点所在的层数*/struct SPQ *upnod

9、e ,*nextnode;/*本结点的父结点和同层的下一个结点的地址*/spq：int loopnum;/*记录总的扩展次数*/int openednum:/*记录已扩展右点个数*/int unopenednum;/*记录待扩展巧点个数*/int resultnum;struct SPQ opened;struct SPQ *oend;struct SPQ unopened:struct SPQ *uend;struct SPQ *result;void initiate();void releasemem();void showresult();void addtoopened(struct

10、 SPQ *ntx);int search();void goon();int strctch(struct SPQ* mx);void recorder();void addtoopened(struct SPQ *ntx) /*扩展巧点*/ unopened = unopened nextnode;unopenednum-;if (openednum = 0 )oend = opened = ntx;oend - nextnode = ntx;oend = ntx;openednum+;void recorder()int i, loop;struct SPQ *newnode;struc

11、t SPQ *ntx;loop = oend loop;ntx = oend;resultnum = 0;for( i = 0 ; i sr = ntx sr;newnodc - pr = ntx - pr;newnodc - si = ntx si;newnodc - pl = ntx pl;newnodc - sst = ntx sst;newnodc - spt = ntx spt;newnode - ssr = ntx ssr;newnodc - spr = ntx spr:newnode - nextnode = NULL:ntx = ntx - upnode;if(i = 0)re

12、sult = newnode;newnode - nextnode = result;result = newnode;resultnum+;void releasememoint i;struct SPQ* nodefree;for (i = 1 ; i nextnode; free(nodefree);for (i = 0 ; i pr); printf(n%d 个野人 result - sr); printf(H%d 个传教 kresult - pl); printf(N%d 个野人 *result - si); for (i = 1 ; i pl result - spt + resu

13、lt - spr;fpr = result pr result spr;fsl = result si result sst + result ssr;fsr = result sr - result - ssr;printfC* 传教士 %8d%8dt spt.fpr);printf(H 野 人 %8d%8dt sstjsr);printf(传教士%8d%8dt-t%8dn,result - pl,result - spr.result - pr - result - spr); printf(N野 人%8d%8dt-t%8dirresult - si,result - ssr,result

14、 - sr - result - ssr);printf(”n全体传教士和野人全部到达对岸“)；free(result);void goon() /*循环操作选择*/char choice;for(;)printf(是否继续? (Y/N)n);scanf fr%s, &choice);choice=toupper(choice);if(choice=,Y,)break;if(choice=,N,)exit(0);)int main()int flag; /*标记扩展是否成功*/for(;)initiate();flag = search ();if(flag= 1)recorder();rel

15、easememo；showresult();goon();elseprintf(无法找到符合条件的解“);releasemem();goon();system(” pause”)；return 0;void initiate()int x;char choice;uend = unopened = (struct SPQ*)malloc(sizeof(spq);if(uend=NULL)printf(Hn 内存不够！ nH);exit(O);unopencdnum=l;opcnednum=0:保存父结点的地址以成链表*/unopened upnode = unopened; /* unopen

16、ed nextnode = unopened: unopened sr = slavenum;unopened pr = pristnum:unopened si = 0;unopened pl = 0;unopened sst = 0;unopened spt = 0;unopened ssr = 0;unopened spr = 0;unopened loop = 0;printfC*题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到左岸去 ）;printfC1该船的负载能力为两人。在任何时候，如果野人人数超过传教七人数，野人n”）；primf（”就会把传教士吃掉。他们怎样才能用

17、这条船安全的把所有人都渡过河去）;printf(* * * * * * *“)printf(Hii 默认的 n m 值皆为3nJ;printf(Mn 是否修改？ (Y/N)H);scanf(,r%sH,&choice);choice=toupper(choice);if(choice=,Y,)printf（Mii请输入传教士人数”）;for（;）scanf(n%d*&x);if(x0)unopened - pr = x;break:else printf(n输入值应大于0! n请重新输入”)；printfCXn请输入野人人数);for(;)scanf(,%d,&x);if(x0)unopene

18、d - sr = x;break:else printf(n输入值应大于0! n请重新输入”)；break:if(choice=,N,)break;int search()int flag;stmct SPQ *ntx;/*提供将要扩展的结点的指针*/for(;)ntx = unopened: /*从待扩展链表中提取最前面的一个*/if(ntx-loop = maxloop)return 0;addtoopened(ntx): /*将ntx加入已扩展链表，并将这个fj点从待扩展链表中去掉*/ flag = stretch(ntx); /* 对 ntx 进行扩展，返回 1.0,1 /if(fla

19、g= 1)return 1;int stretch(struct SPQ *ntx)int fsr, fpr; /*在右岸上的人数*/int fsl, fpl; /*在左岸上的人数*/int sst, spt; /*出发时在船上的人数*/int ssr, spr;/*返回时船上的人数*/struct SPQ *newnode;for (sst = 0 ; sst sr;fpr = ntx pr;fsl = ntx - si;fpl = ntx - pl;if (sst = fsr) & ( 2 - sst) upnode = ntx; /*保存父结点的地址以成链表/newnode nextnode = NULL:newnodc sr = 0;newnode - pr = 0;newnodc - si = opened - sr;newnode - pl = opened - pr;newnodc - sst = sst;newnode - spt = spt;newnodc - ssr = 0;newnodc - spr = 0;newnodc loop = ntx - loop + 1;oend - nextnode = ne