传教士和野人问题48580

传教士和野人问题(Missionaries and Cannibals)传教士和野人问题是一个经典的智力游戏问题。在这个 问题中，实际上隐含了这样一个条件：如果在河的某一岸只 有野人，而没有传教士，也同样被认为是合法状态。在具体 书写某些条件时，为了简便，这一点有时并没有考虑，但我 们默认这个条件是被考虑了的。有N个传教士和N个野人来到河边准备 渡河，河岸有一条船，每次至多可供k人乘 渡。问传教士为了安全起见，应如何规划摆 渡方案，使得任何时刻，在河的两岸以及船 上的野人数目总是不超过传教士的数目。即 求解传教士和野人从左岸全部摆渡到右岸 的过程中，任何时刻满足M （传教士数）&（野人数）和M+CC，船上 M+C0,否 则的话，在左岸的传教士人数就是负数了。但这一点完全可 以通过定义什么是合法状态来判断，因此就没有必要将这个 条件写入规则中了。但为什么在规则中写入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 1i+j2 THEN （m-i, c-j, 0） 从左岸到右岸IF （m, c, 0） AND li+j2 THEN （m+i, c+j, 0） 从右岸到左 岸也可以表示为：IF (m, c, b=1) AND 1i+j2 THEN (m-i, c-j, b-1)IF (m, c, b=0) AND 1i+j2 THEN (m+i, c+j, b+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+hCL-B+l）；山山操作）if （Ml-Cl，Bl=0）then（ML! CL+hB+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的矩阵给出左、右岸 的情况来表示一种状态当然可以，但显然仅用描述左岸的三 元组描述就足以表示出整个情况，因此必须十分重视选择较 好的问题表示法。以后的讨论还可以看到高效率的问题求解 过程与控制策略有关，合适的控制策略可缩小状态空间的搜 索范围，提高求解的效率。