传教士和野人问题

状态空间法详解传教士和野人问题 传教士和野人问题（The Missionaries and Cannibals Problem） 在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过 河去，但是受到以下条件的限制： ① 教士和野人都会划船，但船一次最多只能装运两个； ② ②在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至 被吃掉。 此外，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。 （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 个，如表所示。 表 1 传教士和野人问题的全部可能状态 注意：按题目规定条件，应划去非法状态，从而加快搜索效率。 1）首先可以划去左岸边野人数目超过传教士的情况，即 S4、S8、S9、S20、S24、S25 等 6 种状态是不合法的； 2）应划去右岸边野人数目超过修道士的情况，即 S6、S7、S11、S22、S23、S27 等情 况； 3）应划去 4 种不可能出现状态：划去 S15 和 S16——船不可能停靠在无人的岸边；划去 S3——传教士不可能在数量占优势的野人眼皮底下把船安全地划回来；划去 S28——传教 士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。可见，在状态空间中，真正 符合题目规定条件的只有 16 个合理状态。 （5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求 解。 根据上述分析，共有 16 个合法状态和允许的操作，可以划出传教士和食人者问题的状态空 间图，如图所示。 图 2 传教士和野人问题的状态空间 任何一条从 S0 到达 S31 的路径都是该问题的解。 A*算法详解传教士和野人问题 评估函数为 f=h+d=M+N-2*B+d.。 M 表示左岸的传教士的人数，N 表示左岸野人的数目，B 取 值为 0 或 1 。1 表示船在左岸，0 表示船在右岸。d 表示节点 的深度。 下面来 h(n)＝M+C-2B 是满足 A*条件的。 分两种情况考虑。先考虑船在左岸的情况。如果不考 虑限制条件，也就是说，船一次可以将三人从左岸运到右岸， 然后再有一个人将船送回来。这样，船 一个来回可以运过河 2 人，而船仍然在左岸。而最后剩下的三个人，则可以一次将 他们全部从左岸运到右岸。所以，在不考虑限制条件的情况 下，也至少需要摆渡 [(M+N-3)/2]*2+1 次。其中分子上的"－ 3"表示剩下三个留待最后一次运过去。除以"2"是因为一个来 回可以运过去 2 人，需要[(M+N- 3)/2]个来回，而"来回"数不 能是小数，需要向上取整，这个用符号[ ]表示。而乘以"2"是 因为一个来回相当于两次摆渡，所以要乘以 2。而最后的" ＋ 1"，则表示将剩下的 3 个运过去，需要一次摆渡。 化简有： M+N-2。 再考虑船在右岸的情况。同样不考虑限制条件。船在右 岸，需要一个人将船运到左岸。因此对于状态(M，N，0)来说， 其所需要的最少摆渡数，相当于船在左岸时状态(M+1，N， 1)或(M，N+1，1)所需 要的最少摆渡数，再加上第一次将船 从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为： (M+N+1)-2+1。其中(M+N+1)的"＋1"表示送 船回到左岸的那 个人，而最后边的"＋1"，表示送船到左岸时的一次摆渡。 化简有：(M+N+1)-2+1=M+N。 综合船在左岸和船在右岸两种情况下，所需要的最少摆 渡次数用一个式子表示为：M+N-2B。其中 B＝1 表示船在左 岸，B＝0 表示船在右岸。 由于该摆渡次数是在不考虑限制条件下，推出的最少所 需要的摆渡次数。因此，当有限制条件时，最优的摆渡次数 只能大于等于该摆渡次数。所以该启发函数 h 是 A*条件的。