传教士与野人过河问题Word版

1、如果您需要使用本文档，请点击下载按钮下载!传教士-野人问题有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 Q10如果您需要使用本文档，请点击下载按钮下载!6.2.3 用状态空间法求解传教士和食人者问题例6-2 传教士和食人者问题（The Missionaries and

2、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）定义并确定操作集。仍然

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

4、,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所示。 0211110103202203213

5、11020S0S17S2111011002S1S2200111013310120S290210S30S1401S13010111102S19300S5221S10S12031S24110S1831002S13000图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; /

6、* 回来（由左向右时）船上的人数 */ 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 =

《传教士与野人过河问题Word版》由会员ni****g分享，可在线阅读，更多相关《传教士与野人过河问题Word版》请在金锄头文库上搜索。