人工智能考试重点总结42.doc

人工智能考试重点总结42 例：设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵循两个约束：（1）船上的 人数不得超过载重限量，设为K个人；（2）为预防野人攻击，任何时刻（包含两岸、船上）野 人数13不得超过传教士数目。应如何规划渡河方案？ 为便于憧得状态空间表示法，可简化该问题到一个特例：N=3, K=2。 解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数与野人 数，还需要考虏船在左岸还是在右岸.从丽用一个三状态 S=（m, c, b） 其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。 右岸的状态可由下式确定： 右岸修道士数m=3-m 右岸野人数 c?=3.c 右岸船数 b=l-b 在这种表示方式下，m与c都可取0、1、2、3中之一，b可取。与1中之一,因此，共 有4X4X2=32种状态。 这32种状态并非全有意义，除去不合法状态与修道士被野人吃掉的状态，有意义的状态只有 16种： S0=(3,3,1) Sl=(3, 2,1) S2=(3,1,1) S3=(2, 2,1) S4=(l,l,l) S5=(0,3,l) S6=(0,2,1) S7=(0,1,1) S8=(3,2,0) S9=(3,1,0) S10=(3,0,0) Sll=(2,2,0) S12=(l, 1.0) S13=(0, 2, 0) S 14=(0,1,0) S15=(0,0,0) 有了这些状态，还需要考處可进行的操作。 操作是指用船把修道士或者野人从河的左岸运到右岸，或者从河的右岸运到左岸。 每个操作都应当满足如下条件： 一是船至少有一个人（m或者c）操作，髙开岸边的m与c的减少数目应该等于到达岸边 的m与c的増加数目； 二是毎次操作船上人数不得超过2个； 三是操作应保证不产生耳曜状态. 因此，操作应由条件部分与动作部分， 条件：只有当其条件具备时才能使用 动作：刻划了应用此操作所产生的结果。 操作的表示： 用符号1勺表示从左岸到右岸的运人操作 用符号Qij表示从右岸到左岸的操作 其中， ［表示船上的修道士人数 j表示船上的野人数 操作集 本问题有10种操作可供选择， F={P01. PIO, Pll, P02, P20.Q01. Q10, QH. Q02, Q20} 下面以P01与Q01为例来说明这些操作的条件与动作. 动作 b=0, c=c-l b=l, c=c+l 操作符号 P01 Q01 因此，从初始状态出发， b=l. m=0 或者 3,cNl b=0. ni=O 或者 3, cW2 可画出该问题的状态空间右向图，见图1.1 o(220) (110)o o(021) 11 / 10 20 11 01 02 (331)c. 0； o(320) o (321) o(221)(031)n 02 .(010) (01 Do 01 o(000) 02 mr 低 -31 20 01 10 1 : o(310) o(300) a(020) 水111) 图1. 1 传教士与野人问题的状态空间图 二阶梵塔问题 ■ 设用Sk=(Sk().Skl)表示问題的状态，SkO表示金片A所在钢针号，Ski表示金片B所在 钢针号，全部可能的状态有九种： SO=(I.I),SI=(I,2), S2=(l,3) S3=(2,I).S4=(2.2). S5=(2.3) S6=(3,I). S7=(3.2).S8=(3.3) 问题的初始状态集合为S={S0} 目标状态集合为G={S4,S8} 初始状态S。与目标状态S4、S8如图所示 S, (2,2)土 S, (2,2) 二阶梵塔问题的初始状态和B标状态 操作分别用A(i, j)与B(i, j)表示 A(i, j)表示把金片A从第i号钢针移到j号钢针上. B(i, j)表示把金片B从第i号钢针一到第j号钢针上。共有12种操作，它 们分别是: A(l, 2) A(l, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2) B(l, 2) B(l, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2) 根据上述9种可能的状态与12种操作，可构成二阶梵塔问题的状态空间图, 如下图所示。 二阶梵塔的状态空间图 从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径鄰是问朝的一 个州..共中，最短的路彼长应是3,它由3个操作组成“例如，从(1,1)开 始，通过使用操作A“，3)、B(1, 2)及A(3, 2),可到达(3, 3)? ?s--指示初始状态节点：G…指示有哪些信誉好的足球投注网站图； ?OPEN…用于存放待扩展节点的表： CLOSE---用于存放已扩展节点的表； ?FIRST(OPEN)--指示取OPEN表首的节点作为当前要被扩展的节点n； REMOVE(