《人工智能 野人和传教士问题》由会员分享，可在线阅读，更多相关《人工智能 野人和传教士问题（14页珍藏版）》请在金锄头文库上搜索。
1、传教士野人问题有N个传教士和N个野人要过河，现在有一条船只能承载K个人(包括野人)，K=C 且 M十C=K其中 0=ML,CL=野人数目_oo其它P02,b 0)Ooi(3, 2, 1)(3, 0, 0)(3, b 1)(1, b 0)J f=2 Oil(2, 2, 1)I f=4 P20Oil(1, b 0)(2, 2, 1)(0, 2, 0)Ooi(0, 3, 1)OiofM(0, 0, 0)(0, 2, 1)f3 OoiOoi623用状态空间法求解传教士和食人者问题传教士和食人者问题（The Missionaiies and Camubals Problem）。在河的左/t-有3个传 教
2、士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条 件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何斥边食 人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外, 假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。解我们按上述步骤来进行求解分析。（1）设定状态变量及确定值域。为了建立这个问题的状态空间，设左岸的传教士数为m,则有m=0, 1, 2, 3；对应右岸的传教士数为3m；左申的食人者数为c,则有c=0, 1, 2, 3； 对应右岸食人者数为3c：左即船数为b,故又有b=0, 1；
3、右即的船数为1-b。（2）确定状态组，分别列出初始状态集和目标状态集。问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即右斗的状态可以不必 标出。Sk= （m, c, b）初始状态只有一个：So= （3,3,1）,初始状态表示全部成员在河的的左岸；目标状态也只有一个：Sg= （0, 0, 0）,表示全部成员从河的左#全部渡河完毕。（3）定义并确定操作集。仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Py操作。其中，第一下标 1表示船载的传教士数，第二下标J表示船载的食人者数；同理，从右岸将船划回左斥称之 为Q1J操作，下标的定义同前。则共有10种操作，操作集为F=Poi, Pio
4、, Pii, P02, Pzo, Qoi, Qio, Qu, Q02. Q20（4）估计全部的状态空间数，并尽可能列出全部的状态空间或予以描述。在这个问题世界中，So=3, 3, 1为初始状态，S3i=Sg= （0, 0, 0）为目标状态。 全部的可能状态共有32个，如表6-1所示。表61传教士和食人者问题的全部可能状态状态m, c，b状态ni, c, b状态in, c、b状态叫c, bSo3,3Ss1,3,1S163,3,0S241,3,0Si3,2,1S91,2,1S173,2,0S251,2,0S23,1,1Sio1,1,1S183,1,0S251,1,0S33,0,1Sil1,0,1S
5、193,0,0S271Q0S42,3,1S120,3,1S202,3,0S280,3,0S52,2,1S130,2,1S212,2,0S290,2,0S52,1,1S140,1,1S222,1,0S300,1,0S72Q1S150A1S232Q0S310Q0值得注意的是按照题目规定的条件，我们应该划去不合法的状态，这样可以加快搜索 求解的效率。例如，首先可以划去卅边食人者数目超过传教士的情况，即S4、Ss、S9、S20、 S24、S25等6种状态是不合法的：其次，应该划去右岸边食人者数目超过修道士的情况，即 S6、S7、S1K S22、S23、S27等情况;余下20种合法状态中,又有4种是不可
6、能出现的状态; S15和S16不可能出现，因为船不可能停靠在无人的岸边；S3不可能出现，因为传教士不可 能在数量占优势的食人者眼皮底下把船安全地划回来：还应该划去S28,因为传教士也不可 能在数量占优势的食人者眼皮底下把船安全地划向对挣。可见，在状态空间中，真正符合题 目规定条件的只有16个合理状态。（5）当状态数量不是很人时，按问题的有序元组画出状态空间图，依照状态空间图 搜索求解。根据上述分析，共有16个合法状态和允许的操作，可以划出传教士和食人者问题的状 态空间图，如图64所示。SyS12331320321311020010011 000S19S5图64传教士和食人者问题的状态空间如图6
7、4所示，由于划船操作是可逆的，所以图中状态节点间用双向箭头连接，箭头 旁边所标的数字表示了P或Q操作的下标，即分别表示船载的传教士数和衣人者数。这样, 任何一条从So到达S31的路径都是该问题的解。这样，通过运用状态空间表示法就解决了传教士和食人者问题的求解。源代码：#include #include #include define maxloop 100/*最大层数，对于不同的扩展方法自动调整取值*/define pristnum 3 /*初始化时设定有3个野人3个传教士,实际可以改动*/define slavenum 3stmct SPQ mt sr,pr; /*船运行一个来回后河右#的野
8、人、传教士的人数*/mt sl,pl; /*船运行一个来回后河左岸的野人、传教士的人数*/int ssr,spr; /*回来（由左向右时）船上的人数*/mt sst,spt; /*去时（由右向左时）船上的人数*/int loop; /*本结点所在的层数*/stmct SPQ *upnode ,*nextnodey*本结点的父结点和同层的卞一个结点的地址*/spq；mt loopnum;/*记录总的扩展次数*/mt openednum;/*记录已扩展节点个数*/mt unopenednum;/*记录待扩展节点个数*/mt resultnum;stmct SPQ * opened;stmct SP
9、Q *oend;stmct SPQ *unopened;stmct SPQ *uend;stmct SPQ *result;void uutiateQ;void releasemem();void showresultQ;void addtoopened(stinct SPQ *ntx);mt seaich();void goon();mt stretch(stmct SPQ* ntx);void recordei();void addtoopened(stiuct SPQ *ntx) /*扩展节点*/ unopened = unopened - nextnode; unopenednum;i
10、f (openednum = 0 )oend = opened = ntx;oend - nextnode = ntx;oend = ntx;openednum-H-;void recoider()mt i, loop;stmct SPQ *newnode;stmct SPQ *ntx;loop = oend - loop;ntx = oend;resultnum = 0;fdr( i = 0 ; i sr = ntx - sr;newnode - pr = ntx - pr;newnode - si = ntx - si;newnode - pl = ntx - pl;newnode - s
11、st = ntx - sst;newnode - spt = ntx - spt;newnode - ssr = ntx - ssr;newnode - spr = ntx - spr;newnode - nextiiode = NULL;ntx = ntx - upnode;if(i 0)result = newnode;newnode - nextiiode = result;result = newnode;resultnum+;void releasemeniQmt i;stmct SPQ* nodefiee;for (i = 1 ; i nextnode;fiee(nodefiee);for (i = 0 ; i nextnode; fiee(nodefiee);void showresultO /* 显示 */mt i;mt fsr , fpr ; /*在右岸上的人数*/ mt fsl, fpl; /*在左岸上的人数*/ stmct SPQ* nodefiee
