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

传教士-野人问题 有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），KN，在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。 设M为传教士的人数，C为野人的人数，用状态空间发求解此问题的过程如下： 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 用三元组来表示（ML , CL , BL） 其中0=ML , CL = 3 , BL ∈{ 0 , 1} (3 , 3 , 1) (0 , 0 , 0) 规则集合 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 ) 寻找一个启发式函数引导规则的选用 右岸总人数6 – ML – CL 两岸中传教士数目=野人数目 f = –∞ 其它 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 状 态 m, c, b S0 3,3,1 S8 1,3,1 S