传教士_野人问题参考答案下载_Word模板_4

输入关键词搜索资料

首页 > 行业资料 > 互联网

is_093848

暂无简介

传教士_野人问题参考答案传教士-野人问题有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K=C且M+C =野人数目 f = ...

传教士-野人问

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K=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) 用三元组来

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf 视力表打印pdf 用图表说话 pdf

示（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 ) (3) Q02 if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) (4) 寻找一个启发式函数引导规则的选用右岸总人数6 – ML – CL 两岸中传教士数目>=野人数目 f = –∞ 其它 6.2.3 用状态空间法求解传教士和食人者问题例6-2 传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的

计划

项目进度计划表范例计划下载计划下载计划下载课程教学计划下载

。解我们按上述步骤来进行求解

分析

定性数据统计分析pdf 销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

。（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 状态 m, c, b S0 3,3,1 S8 1,3,1 S16 3,3,0 S24 1,3,0 S1 3,2,1 S9 1,2,1 S17 3,2,0 S25 1,2,0 S2 3,1,1 S10 1,1,1 S18 3,1,0 S26 1,1,0 S3 3,0,1 S11 1,0,1 S19 3,0,0 S27 1,0,0 S4 2,3,1 S12 0,3,1 S20 2,3,0 S28 0,3,0 S5 2,2,1 S13 0,2,1 S21 2,2,0 S29 0,2,0 S6 2,1,1 S14 0,1,1 S22 2,1,0 S30 0,1,0 S7 2,0,1 S15 0,0,1 S23 2,0,0 S31 0,0,0 值得注意的是按照题目规定的条件，我们应该划去不合法的状态，这样可以加快搜索求解的效率。例如，首先可以划去岸边食人者数目超过传教士的情况，即Ｓ4、S8、S9、S20、S24、S25等6种状态是不合法的；其次，应该划去右岸边食人者数目超过修道士的情况，即S6、S7、S11、S22、S23、S27等情况；余下20种合法状态中，又有4种是不可能出现的状态；S15和S16不可能出现，因为船不可能停靠在无人的岸边；S3不可能出现，因为传教士不可能在数量占优势的食人者眼皮底下把船安全地划回来；还应该划去S28，因为传教士也不可能在数量占优势的食人者眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题目规定条件的只有16个合理状态。（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。根据上述分析，共有16个合法状态和允许的操作，可以划出传教士和食人者问题的状态空间图，如图6—4所示。图6—4 传教士和食人者问题的状态空间如图6—4所示，由于划船操作是可逆的，所以图中状态节点间用双向箭头连接，箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。这样，任何一条从S0到达S31的路径都是该问题的解。这样，通过运用状态空间表示法就解决了传教士和食人者问题的求解。 f=3 Q01 f=2 P02 f=1 Q01 f=1 Q11 f=1 P01 f=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 Q11 1 （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 S13 02 310 S18 110 S24 031 S12 S10 221 S5 300 S19 02 11 000 011 01 S13 01 S14 S30 10 02 S29 20 01 331 01 11 01 20 S2 S1 02 10 01 11 S21 S17 S0 020 311 321 220 320 010 111 021

本文档为【传教士_野人问题参考答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

传教士_野人问题参考答案

热门搜索

历史搜索