传教士-野人问题
有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K 设M为传教士的人数，C为野人的人数，用状态空间发求解此问题的过程如下： M、C = N，boat = k，要求M>=C且M+C <= K 初始状态 目标状态 L R L RM 3 0 M 0 3C 3 0 C 0 3B 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=5 P02 （0，1，1） f=4 Q01 （0，2，1） f=3 Q01 f=4 Q10 （1，1，1） f=3 Q01 （0，0，0） 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 1,3,0 1,2,0 1,1,0 1,0,0 0,3,0 0,2,0 0,1,0 0,0,0 状 态 S0 S1 S2 S3 S4 S5 S6 S7 m, c, b 3,3,1 3,2,1 3,1,1 3,0,1 2,3,1 2,2,1 2,1,1 2,0,1 状 态 S8 S9 S10 S11 S12 S13 S14 S15 m, c, b 1,3,1 1,2,1 1,1,1 1,0,1 0,3,1 0,2,1 0,1,1 0,0,1 状 态 S16 S17 S18 S19 S20 S21 S22 S23 m, c, b 3,3,0 3,2,0 3,1,0 3,0,0 2,3,0 2,2,0 2,1,0 2,0,0 状 态 S24 S25 S26 S27 S28 S29 S30 S31 值得注意的是按照题目规定的条件，我们应该划去不合法的状态，这样可以加快搜索求解的效率。例如，首先可以划去岸边食人者数目超过传教士的情况，即Ｓ4、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 S 29020 20 S10 111 02 10 010 11 310 01 S17 320 S21 S14 011 S13 021 01 000 02 S13 331 S0 11 311 S2 300 S19 01 S30 01 220 221 S5 图6—4 传教士和食人者问题的状态空间 如图6—4所示，由于划船操作是可逆的，所以图中状态节点间用双向箭头连接，箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。这样， 任何一条从S0到达S31的路径都是该问题的解。 这样，通过运用状态空间表示法就解决了传教士和食人者问题的求解。