传教士与野人过河问题.doc

传教士-野人问题有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K=C且M+C = K初始状态目标状态LRLRM30M03C30C03B10B01(1) 用三元组来表示（ML , CL , BL）其中0=ML , CL =野人数目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）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 用状态空间法求解传教士和食人者问题例6-2 传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。解 我们按上述步骤来进行求解分析。（1）设定状态变量及确定值域。为了建立这个问题的状态空间，设左岸的传教士数为m，则有m=0，1，2，3；对应右岸的传教士数为3m；左岸的食人者数为c，则有c=0，1，2，3；对应右岸食人者数为3c；左岸船数为b，故又有b=0，1；右岸的船数为1-b。（2）确定状态组，分别列出初始状态集和目标状态集。问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即右岸的状态可以不必标出。 Sk=（m, c, b）初始状态只有一个：S0=（3， 3， 1），初始状态表示全部成员在河的的左岸；目标状态也只有一个：Sg=（0，0，0），表示全部成员从河的左岸全部渡河完毕。（3）定义并确定操作集。仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为 F=P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20（4）估计全部的状态空间数，并尽可能列出全部的状态空间或予以描述。在这个问题世界中，S0=3，3，1为初始状态，S31=Sg=（0，0，0）为目标状态。全部的可能状态共有32个，如表61所示。 表61 传教士和食人者问题的全部可能状态状 态m, c, b状 态m, c, b状 态m, c, b状 态 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值得注意的是按照题目规定的条件，我们应该划去不合法的状态，这样可以加快搜索求解的效率。例如，首先可以划去岸边食人者数目超过传教士的情况，即4、S8、S9、S20、S24、S25等6种状态是不合法的；其次，应该划去右岸边食人者数目超过修道士的情况，即S6、S7、S11、S22、S23、S27等情况；余下20种合法状态中，又有4种是不可能出现的状态；S15和S16不可能出现，因为船不可能停靠在无人的岸边；S3不可能出现，因为传教士不可能在数量占优势的食人者眼皮底下把船安全地划回来；还应该划去S28，因为传教士也不可能在数量占优势的食人者眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题目规定条件的只有16个合理状态。（5） 当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。 根据上述分析，共有16个合法状态和允许的操作，可以划出传教士和食人者问题的状态空间图，如图64所示。 021111010320220321311020S0S17S2111011002S1S2200111013310120S290210S30S140119300S5221S10S12031S24110S1831002S13000图64 传教士和食人者问题的状态空间如图64所示，由于划船操作是可逆的，所以图中状态节点间用双向箭头连接，箭头旁边所标的数字表示了或操作的下标，即分别表示船载的传教士数和食人者数。这样，任何一条从S0到达S31的路径都是该问题的解。这样，通过运用状态空间表示法就解决了传教士和食人者问题的求解。源代码：#include #include #include #define maxloop 100 /* 最大层数，对于不同的扩展方法自动调整取值 */ #define pristnum 3 /*初始化时设定有3个野人3个传教士，实际可以改动*/ #define slavenum 3struct SPQ int sr,pr; /* 船运行一个来回后河右岸的野人、传教士的人数 */ int sl,pl; /* 船运行一个来回后河左岸的野人、传教士的人数 */ int ssr,spr; /* 回来（由左向右时）船上的人数 */ int sst,spt; /* 去时（由右向左时）船上的人数 */ int loop; /* 本结点所在的层数 */ struct SPQ *upnode ,*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 SPQ *ntx); int search(); void goon(); int stretch(struct SPQ* ntx); 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; 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; 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 - nextnode = result; result = newnode; resultnum+; void releasemem() int i; struct SPQ* nodefree; for ( i = 1 ; i nextnode; free(nodefree); for ( i = 0 ; i nextnode; free(nodefree); void showresult() /*显示*/ int i; int fsr , fpr ; /* 在右岸上的人数 */ int fsl , fpl ; /* 在左岸上的人数 */ struct SPQ* nodefree; printf(%d个传教士,result - pr); printf(%d个野人 ,result - sr); printf(%d个传教士,result - pl); printf(%d个野人 ,result - sl); for ( i = 1 ; i nextnode; free(nodefree); printf(nnt左岸人数 船上人数及方向 右岸人数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); 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全体传教士和野人全部到达对岸); free(result); void goon() /*循环操作选择*/ char choice; for(;) printf(是否继续？(Y/N)n); scanf (%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(); releasemem(); showresult(); goon(); else printf(无法找到符合条件的解); releasemem(); goon(); system(pause); return 0; void initiate() int x; char choice; uend = unopened = (struct SPQ*)malloc(sizeof(spq); if(uend=NULL) printf(n内存不够！n); exit(0); unopenednum=1; openednum=0; unopened - upnode = unopened; /* 保存父结点的地址以成链表 */ unopened - nextnode = unopened; unopened - sr = slavenum; unopened - pr = pristnum; unopened - sl = 0; unopened - pl = 0; unopened - sst = 0; unopened - spt = 0; unopened - ssr = 0; unopened - spr = 0; unopened - loop = 0; printf(*n); printf(题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到左岸去。n); printf(该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人n); printf(就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去n); printf(*); printf(n默认的n、m值皆为3n); for(;) printf(n是否修改？(Y/N); scanf(%s,&choice); choice=toupper(choice); if(choice=Y) printf(n请输入传教士人数); for(;) scanf(%d,&x); if(x0) unopened - pr = x; break; else printf(n输入值应大于0！n请重新输入); printf(n请输入野人人数); for(;) scanf(%d,&x); if(x0) unopened - sr = x; break; else printf(n输入值应大于0！n请重新输入); break; if(choice=N)break; int search() int flag; struct SPQ *ntx; /* 提供将要扩展的结点的指针 */ for( ; ) ntx = unopened; /* 从待扩展链表中提取最前面的一个 */ if(ntx-loop = maxloop) return 0; addtoopened(ntx); /* 将ntx加入已扩展链表，并将这个节点从待扩展链表中去掉 */ flag = stretch(ntx); /* 对ntx进行扩展,返回-1,0,1 */ if(flag = 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 - sl; fpl = ntx - pl; if (sst = fsr) & ( 2 - sst) upnode = ntx; /* 保存父结点的地址以成链表 */ 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;