传教士和野人问题48580.doc

传教士和野人问题(Missionaries and Cannibals)传教士和野人问题是一个经典的智力游戏问题在这个 问题中，实际上隐含了这样一个条件：如果在河的某一岸只 有野人，而没有传教士，也同样被认为是合法状态在具体 书写某些条件时，为了简便，这一点有时并没有考虑，但我 们默认这个条件是被考虑了的有N个传教士和N个野人来到河边准备 渡河，河岸有一条船，每次至多可供k人乘 渡问传教士为了安全起见，应如何规划摆 渡方案，使得任何时刻，在河的两岸以及船 上的野人数目总是不超过传教士的数目即 求解传教士和野人从左岸全部摆渡到右岸 的过程中，任何时刻满足M （传教士数）&（野人数）和M+CC，船上 M+C<2LRM30C30B10初始状态LRM03C03B01目标状态图 1.2 M －C 问题实例由于传教士和野人数是一个常数，所以知道了一岸的情 况，另一岸的情况也就知道了因此为了简便起见，在描述 问题时，只描述一岸--如左岸--的情况就可以了。

另外，该问题我们最关心的是在摆渡过程中，两岸状态的 变化情况，因此船上的情况并不需要直接表达出来在一次 摆渡过程中，船上究竟有几个传教士和野人，可以通过两个 相连的状态简单得到这样表达更简练，突出了问题的重点1）综合数据库：用三元组表示左岸的情况，即（ml，Cl，也），其中ClS3，比三｛0，1｝，其中牴表示 在左岸的传教士人数，屁表示在左岸的野人数，比=1表示船 在左岸，比=0表示船在右岸则此时问题描述可以简化为:（3, 3, 1） f （0, 0, 0）N=3的M-C问题，状态空间的总状态数为4x4x2 = 32, 根据约束条件的要求，可以看出只有 20 个合法状态再进 一步分析后，又发现有 4 个合法状态实际上是不可能达到的 因此实际的问题空间仅由 16 个状态构成下表列出分析的 结果：（蚯 CLBL） （血 CLBL）（ 0 0 1 ）达不到（传教士（ 0 0 0）均在右，船在左）（010）( 0 11）（020）( 0 21）（030）达不到( 0 31）（100）不合法（右岸野( 1 01）不合法（右岸野人多）人多）（110）( 1 11）（120）不合法（左岸野( 1 21）不合法（左岸野人多）人多）（130）不合法（左岸野( 1 31）不合法（左岸野人多）人多）（200）不合法（右岸野( 2 01）不合法（右岸野人多）人多）（210）不合法（右岸野( 2 11）不合法（右岸野人多）人多）（230）不合法（右岸野( 2 21）人多）( 2 31）不合法（左岸野（ 300）人多）（220）( 3 01）达不到（310）( 3 11）（320）( 3 21）（330）达不到规则集可以划分为两组：一组是从左岸到右岸，称为p 操作，另一组是从右岸到左岸，称为 q 操作。

按道理，在规 则的前件中应该附加必要的条件，使得产生的状态是合法 的在下一章有关搜索算法的讨论中我们会看到，在每一种 搜索算法中，都有一处判断新产生的状态是否合法对于不 合法的状态，算法会进行相应的处理因此在表达规则时， 那些通过状态的合法性就可以判断的前提条件可以不在规 则中出现这样可以简化规则的表达比如在第一条规则中， 在规则后件中出现了"ML—1"，按道理应该要求ML>0,否 则的话，在左岸的传教士人数就是负数了但这一点完全可 以通过定义什么是合法状态来判断，因此就没有必要将这个 条件写入规则中了但为什么在规则中写入"Bl =1"、"B =I 0"这样的条件呢？其实这样的条件也不是一定要写的，因为 它同样可以通过定义合法状态来判断但由于写上这些条件 后，会使得规则表达更清晰，通过 BL 的取值就可以看出规 则所表达的是船从左岸到右岸，还是从右岸到左岸而且从 左到右，或者从右到左，是交替进行的，因此把这样的条件 明确表达出来，可以提高问题的求解效率所以说，对于通 过状态的合法性可以判断的条件，是否在规则中明确表达出 来，具有一定的灵活性，可以从规则的清晰性、易懂性，以 及求解效率等方面综合考虑。

而对于某些不能通过状态的合 法性来判断的条件，则必须在规则中明确表达出来在传教士和野人问题中，假定了传教士和野人都可以划 船，由于每次摆渡船上最多可以有 2 个人，最少也必须有一 个人（船不会自己前进），因此在船上共有（2，0）、（0 2）、（1，1）、（1，0）和（0，1）这 5种组合其中第 一个数字表示在船上的传教士数，第二个数字表示在船上的 野人数再加上从左岸到右岸和从右岸到左岸这两种情况， 所以共有10种摆渡方法在该例题中，将这10 种摆渡方法 全部以规则的形式，一一列举出来这种方法的好处是，规 则简单、易懂，但不足也很明显：繁琐尤其是对于实际的 复杂问题，如果要全部一一列举出所有规则，其数量太大 表示规则的另一种方式就是引入变量，通过引入变量，将相 近的几条规则组合在一条规则中表示同样是传教士和野人 问题，我们引入i和j两个变量，分别表示此次摆渡时，过 河的传教士数和野人数，则可以将 10条规则组合为两条规 则：IF （m, c, 1） AND 1

2）规则集合：由摆渡操作组成该问题主要有两种操作： 险操作（规定为从左岸划向右岸）和弧操作（从右岸划向左 岸）每次摆渡操作，船上人数有五种组合，因而组成有10 条规则的集合if（Ml- Cl，Bl=1）then （ML-1, CL-比一1）； gio操作）if（MLj Cl，Bl=1） then （ML）CL-1, BL-1）; （p（n操作）if（Ml- Cl- Bl=1）then （ML-1,屁一1，氐一l）；gii操作）if（Ml, % Bl=1） then （ML-2, CL, BL-1）;（阿操作）if（Ml- Cl，Bl=1）then （ML； CL-2,比一1）；（佃操作）if （Ml- Cl，Bl=0） then （ML+h CL- B+l）； 山山操作）if （Ml- Cl，Bl=0） then （ML! CL+h B+l）； （初操作）if （Ml- Cl，Bl=0） then （ML+1, 屁+l，B+l）； （qii操作）if （Ml- Cl，Bl=0） then （ML+2, CL- B+l）； （啦操作）if （Ml- Cl，Bl=0） then （ML?屁+2，B+l）； （血操作）（ 3）初始和目标状态：即（ 3，3，1）和（ 0，0，0）。

和八数码游戏的问题一样，建立了产生式系统描述之 后，就可以通过控制策略，对状态空间进行搜索，求得一个 摆渡操作序列，使其能够达到目标状态在讨论用产生式系统求解问题时，有时引入状态空间图 的概念很有帮助状态空间图是一个有向图，其节点可表示 问题的各种状态（综合数据库），节点之间的弧线代表一些 操作（产生式规则），它们可把一种状态导向另一种状态 这样建立起来的状态空间图，描述了问题所有可能出现的状 态及状态和操作之间的关系，因而可以较直观地看出问题的 解路径及其性质实际上只有问题空间规模较小的问题才可 能作出状态空间图，例如N=3的M-C问题，其状态空间 图如图1.3所示由于每个摆渡操作都有对应的逆操作，即血 对应蚯，所以该图也可表示成具有双向弧的形式从状态空间图看出解序列相当之多，但最短解序列只有 4 个，均由 11 次摆渡操作构成若给定其中任意两个状态分 别作为初始状态和目标状态，就立即可找出对应的解序列 来在一般情况下，求解过程就是对状态空间搜索出一条解 路径的过程以上两个例子说明了建立产生式系统描述的过程，这也 就是所谓问题的表示对问题表示的好坏，往往对求解过程 的效率有很大影响一种较好的表示法会简化状态空间和规 则集表示，例如八数码问题中，如用将牌移动来描述规则， 则 8 块将牌就有 32 条的规则集，显然用空格走步来描述就 简单得多。

又如M-C问题中，用3x2的矩阵给出左、右岸 的情况来表示一种状态当然可以，但显然仅用描述左岸的三 元组描述就足以表示出整个情况，因此必须十分重视选择较 好的问题表示法以后的讨论还可以看到高效率的问题求解 过程与控制策略有关，合适的控制策略可缩小状态空间的搜 索范围，提高求解的效率。