资源描述
传教士和野人问题(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的矩阵给出左、右岸 的情况来表示一种状态当然可以,但显然仅用描述左岸的三 元组描述就足以表示出整个情况,因此必须十分重视选择较 好的问题表示法。以后的讨论还可以看到高效率的问题求解 过程与控制策略有关,合适的控制策略可缩小状态空间的搜 索范围,提高求解的效率。
展开阅读全文