传教士与野人过河问题
更新时间:2023-12-03 06:32:01 阅读量: 教育文库 文档下载
- 传的多音字推荐度:
- 相关推荐
传教士-野人问题
有N个传教士和N个野人要过河,现在有一条船只能承载K个人(包括野人),K M、C = N,boat = k,要求M>=C且M+C <= K 初始状态 目标状态 L R L R M 3 0 M 0 3 C 3 0 C 0 3 B 1 0 B 0 1 (1) 用三元组来表示(ML , CL , BL) 其中0<=ML , CL <= 3 , BL ∈{ 0 , 1} (3 , 3 , 1) (0 , 0 , 0) (2) 规则集合 P10 if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 ) P01 if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 ) P11 if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) P20 if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 ) P02 if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 ) Q10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) Q01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) Q11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 ) Q02 if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) (3) 寻找一个启发式函数引导规则的选用 右岸总人数6 – ML – CL 两岸中传教士数目>=野人数目 f = –∞ 其它 f=2 P11 (2,2,0) f=1 Q11 (3,3,1) f=1 P01 (3,2,0) f=2 P02 (3,1,0) f=1 Q01 (3,2,1) f=3 P02 (3,0,0) f=2 Q01 (3,1,1) f=4 P20 (1,1,0) f=2 Q11 (2,2,1) f=4 P20 (1,1,0) f=2 Q11 (2,2,1) f=4 P20 (0,2,0) f=3 Q01 (0,3,1) f=4 Q01 (0,2,1) f=3 Q01 (0,0,0) f=5 P02 (0,1,1) f=4 Q10 (1,1,1) f=3 Q01 6.2.3 用状态空间法求解传教士和食人者问题 例6-2 传教士和食人者问题(The Missionaries and Cannibals Problem)。在河的左岸有3个传教士、1条船和3个食人者,传教士们想用这条船将所有的成员运过河去,但是受到以下条件的限制:(1)传教士和食人者都会划船,但船一次最多只能装运两个;(2)在任何岸边食人者数目都不得超过传教士,否则传教士就会遭遇危险:被食人者攻击甚至被吃掉。此外,假定食人者会服从任何一种过河安排,试规划出一个确保全部成员安全过河的计划。 解 我们按上述步骤来进行求解分析。 (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) 初始状态只有一个: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个,如表6—1所示。 表6—1 传教士和食人者问题的全部可能状态 状 态 状 态 m, c, b 状 态 m, c, b m, c, b S0 S1 S2 S3 S4 S5 S6 3,3,1 3,2,1 3,1,1 3,0,1 2,3,1 2,2,1 2,1,1 S8 S9 S10 S11 S12 S13 S14 1,3,1 1,2,1 1,1,1 1,0,1 0,3,1 0,2,1 0,1,1 S16 S17 S18 S19 S20 S21 S22 3,3,0 3,2,0 3,1,0 3,0,0 2,3,0 2,2,0 2,1,0 状 态 S24 S25 S26 S27 S28 S29 S30 m, c, b 1,3,0 1,2,0 1,1,0 1,0,0 0,3,0 0,2,0 0,1,0 S7 2,0,1 S15 0,0,1 S23 2,0,0 S31 0,0,0 值得注意的是按照题目规定的条件,我们应该划去不合法的状态,这样可以加快搜索求解的效率。例如,首先可以划去岸边食人者数目超过传教士的情况,即S4、S8、S9、S20、S24、S25等6种状态是不合法的;其次,应该划去右岸边食人者数目超过修道士的情况,即S6、S7、S11、S22、S23、S27等情况;余下20种合法状态中,又有4种是不可能出现的状态;S15和S16不可能出现,因为船不可能停靠在无人的岸边;S3不可能出现,因为传教士不可能在数量占优势的食人者眼皮底下把船安全地划回来;还应该划去S28,因为传教士也不可能在数量占优势的食人者眼皮底下把船安全地划向对岸。可见,在状态空间中,真正符合题目规定条件的只有16个合理状态。 (5) 当状态数量不是很大时,按问题的有序元组画出状态空间图,依照状态空间图搜索求解。 根据上述分析,共有16个合法状态和允许的操作,可以划出传教士和食人者问题的状态空间图,如图6—4所示。 S18 02 S24 110 01 S1 321 02 10 20 11 S12 031 01 020 20 S10 111 02 10 010 11 310 01 S17 320 S21 S29 S14 011 S13 021 01 000 02 S13 331 S0 11 311 S2 01 300 S19 221 S5 S30 01 220 图6—4 传教士和食人者问题的状态空间 如图6—4所示,由于划船操作是可逆的,所以图中状态节点间用双向箭头连接,箭头旁边所标的数字表示了P或Q操作的下标,即分别表示船载的传教士数和食人者数。这样,任何一条从S0到达S31的路径都是该问题的解。 这样,通过运用状态空间表示法就解决了传教士和食人者问题的求解。 源代码: #include #define maxloop 100 /* 最大层数,对于不同的扩展方法自动调整取值 */ #define pristnum 3 /*初始化时设定有3个野人3个传教士,实际可以改动*/ #define slavenum 3 struct 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 <= loop ; i++ ) { newnode = (struct SPQ*) malloc (sizeof(spq)); if(newnode==NULL) { printf(\内存不够!\\n\ exit(0); } newnode -> sr = ntx -> sr; newnode -> pr = ntx -> pr;
正在阅读:
传教士与野人过河问题12-03
广东省学位英语语法04-02
平安夜为什么送苹果 送几个苹果好02-22
【秋季学期高一二地理备课组工作计划】秋季学期高一、二地理备课04-18
SL176-2007《水利水电工程施工质量检验与评定规程》 - word版06-26
工业设计公司问题研究 - 图文06-22
焊工技能评定08-27
议论文设计并列式结构范文03-13
03~solutions_for_chapter_3_exercises05-15
大体积混凝土施工10-27
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 传教士
- 野人
- 过河
- 问题
- 流体力学习题集
- 西南政法大学2010级博士拟录取名单
- 高三基本能力复习信息技术:第五章 信息的表达与交流
- 小学英语对话教学很重要
- 江阴历史文化概况
- 2013-2014第二学期模拟电子技术期末试卷A详细答案
- FLUENT知识点解析
- 基于+CRUISE+的纯电动汽车动力系统参数匹配与仿真 - 图文
- 《小学科学课堂教学有效追问的研究》中期报告
- 借贷记账法练习题1
- 职能部门职责和岗位的职责
- 金融工程-李飞版本课后习题-答案
- 人事问题集锦
- 2015年中级社会工作师《社会工作综合能力》试卷、答案与解析
- 东北师范大学首届数学建模大赛
- 水文地质学基础习题和答案
- 中考研讨会心得体会
- 施工企业年会总结发言稿
- 《全新版大学英语阅读教程4(高级本)》译文(部分) - - 普通高等教育“十五”国家级规划教材
- 2018高考数学冲刺试卷(江苏卷12)(每题均有详细解答)