人工智能第二章

1、1第二章 与或图搜索问题目标目标初始节点sabc2基本思想基本思想 当一问题较复杂时，可通过分解或变换，将其转化为一系列较简当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。 分解分解 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且只有当所有，并且只有当所有子问题子问题Pi都有解时原问题都有解时原问题P才有解，任何一个子问题才有解，任何一个子问题Pi无解都会导致原无解都会导致原问题问题P无解，则称此种归约为问题的分解。无解，则称

2、此种归约为问题的分解。 即分解所得到的子问题的即分解所得到的子问题的“与与”与原问题与原问题P等价。等价。等价变换等价变换 如果一个问题如果一个问题P可以归约为一组子问题可以归约为一组子问题P1,P2,Pn，并且子问题，并且子问题Pi中只要有一个有解则原问题中只要有一个有解则原问题P就有解，只有当所有子问题就有解，只有当所有子问题Pi都无解时都无解时原问题原问题P才无解，称此种归约为问题的等价变换，简称变换。才无解，称此种归约为问题的等价变换，简称变换。 即变换所得到的子问题的即变换所得到的子问题的“或或”与原问题与原问题P等价。等价。2.1 问题归约法问题归约法3PP1 P2 P3 与树与树

3、P1 P2 P3 或树或树PPP1 P2 P3 P12 P12 P31 P32 P33 与与/或树或树(1)与树与树 分解分解(2) 或树或树 等价变换等价变换(3) 与与/或树或树2.1 问题归约法问题归约法2. 问题的与问题的与/或树表示或树表示4(4) 端节点与终止节点端节点与终止节点 在与在与/或树中，没有子节点的节点称为或树中，没有子节点的节点称为端节点端节点；本原问题所对应的节；本原问题所对应的节点称为点称为终止节点终止节点。可见，终止节点一定是端节点，但端节点却不一定是。可见，终止节点一定是端节点，但端节点却不一定是终止节点。终止节点。(5) 可解节点与不可解节点可解节点与不可解

4、节点 在与在与/或树中，满足以下三个条件之一的节点为或树中，满足以下三个条件之一的节点为可解节点：可解节点： 任何终止节点都是可解节点。任何终止节点都是可解节点。 对对“或或”节点，当其子节点中至少有一个为可解节点时，则该或节点节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。就是可解节点。 对对“与与”节点，只有当其子节点全部为可解节点时，该与节点才是可节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。解节点。 同样，可用类似的方法定义同样，可用类似的方法定义不可解节点：不可解节点： 不为终止节点的端节点是不可解节点。不为终止节点的端节点是不可解节点。 对对“或或”

5、节点，若其全部子节点都为不可解节点，则该或节点是不可节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。解节点。 对对“与与”节点，只要其子节点中有一个为不可解节点，则该与节点是节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。不可解节点。5Pt t t 解树解树(6) 解树解树 由可解节点构成，并且由这些可解由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原节点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。始问题）为可解节点的子树为解树。在解树中一定包含初始节点。在解树中一定包含初始节点。 例如，右图给出的与或树中，用红例如，右图给出的与或树中

6、，用红 线表示的子树是一个解树。在该图中，线表示的子树是一个解树。在该图中，节点节点P为原始问题节点，用为原始问题节点，用t标出的节标出的节点是终止节点。根据可解节点的定义，点是终止节点。根据可解节点的定义，很容易推出原始问题很容易推出原始问题P为可解节点。为可解节点。 问题归约求解过程就实际上就是生问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，的过程。这一过程涉及到搜索的问题，对于与对于与/或树的搜索将在后面详细讨论。或树的搜索将在后面详细讨论。6 例例4.4 三阶梵塔问题。要求把三阶梵塔问题。要求把1号钢针上

7、的号钢针上的3个金片全部移到个金片全部移到3号钢针号钢针上，如下图所示。上，如下图所示。 解：解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。用归约法来解决问题。 为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组用三元组 (i, j, k)表示问题在任一时刻的状态，用表示问题在任一时刻的状态，用“”表示状态的转换。上述三元组中表示状态的转换。上述三元组中 i 代表金片代表金片C所在的钢针号所在的钢针号 j 代表金片代表金片B所在

8、的钢针号所在的钢针号 k 代表金片代表金片A所在的钢针号所在的钢针号1231232.1 问题归约法问题归约法2. 问题的与问题的与/或树表示或树表示7利用问题归约方法，原问题可分解为以下利用问题归约方法，原问题可分解为以下三个子问题：三个子问题： (1) 把金片把金片A及及B移到移到2号钢针上的双金片移动问题。即号钢针上的双金片移动问题。即(1, 1, 1)(1, 2, 2) (2) 把金片把金片C移到移到3号钢针上的单金片移动问题。即号钢针上的单金片移动问题。即 (1, 2, 2)(3, 2, 2) (3) 把金片把金片A及及B移到移到3号钢针的双金片移动问题。即号钢针的双金片移动问题。即(

9、3, 2, 2)( (3, 3, 3)其中，子问题其中，子问题(1)和和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解；都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题子问题(2)是本原问题，它已不需要再分解。是本原问题，它已不需要再分解。 三阶梵塔问题的分解过程可用如下图与三阶梵塔问题的分解过程可用如下图与/或树来表示或树来表示 (1,1,1)(3,3,3) (1,1,1)(1,2,2) (1,2,2)(3,2,2) (3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,1,3)(1,2,3) (1,2,3)(1,2,2) (3,2,2)(3,2,1) (3,2,1

10、)(3,3,1) (3,3,1)(3,3,3) 在该与在该与/或树中，有或树中，有7个终止节点，它们分别对应着个终止节点，它们分别对应着7个本原问题。如果把个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：这些本原问题从左至右排列起来，即得到了原始问题的解： (1, 1, 1)(1, 3, 3) (1, 3, 3)(1, 2, 3) (1, 2, 3)(1, 2, 2) (1, 2, 2)(3, 2, 2) (3, 2, 2)(3, 2, 1) (3, 2, 1)(3, 3, 1) (3, 3, 1)(3, 3, 3) 82.2基本概念l与或图是一个超图，节点间通过连接符连

11、接。lK-连接符：.K个9耗散值的计算k(n, N) = Cn+k(n1, N)+k(ni, N)其中：N为终节点集 Cn为连接符的耗散值.i个nn1n2ni10目标目标初始节点 解图：11l递归定义局部图：定义：单一节点是一个局部图；对于一个局部图的任意叶节点n，选择一个n的外向连接符K，则该局部图、外向连接符K，以及K所连接的n的后继节点一起组成的图，仍然组成一个局部图。12l解图可递归定义如下：定义：一个与或图G中，从节点n到节点集N的解图记为 ， 是G的子图。若n是N的一个元素，则 由单一节点组成；若n有一个指向节点n1，nk的外向连接符K，使得从每一个ni到N有一个解图（i=1，k）

12、，则 由节点n，连接符K，及n1，nk中的每一个节点到N的解图所组成；否则n到N不存在解图。13l解图的耗散值记为k（n，N），则可递归计算如下：若n是N的一个元素，则k（n，N）0；若n是一个外向连接符指向后继节点n1，ni，并设该连接符的耗散值为Cn，则k（n，N）Cn+ k（n1 ，N） + + k（ni ，N）14能解节点l终节点是能解节点l若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。l若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。15不能解节点l没有后裔的非终节点是不能解节点。l若非终节点有“或”子节点，当且仅当所有子节点均

13、不能解时，该非终节点才不能解。l若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。16普通图搜索的情况f(n) = g(n) + h(n)对n的评价实际是对从s到n这条路径的评价ns17与或图: 对局部图的评价目标目标初始节点abc18l局部图的耗散值记为k（n，N），则：若n是局部图的一个叶节点，则k（n，N）h(n)；若n是一个外向连接符指向后继节点n1， ，并设该连接符的耗散值为Cn，则k（n，N）Cn+ k（n1 ，N） + + k（ni ，N）其中，h(n)表示节点n到目标节点集的最佳解图耗散值的估计。19两个过程l图生成过程，即扩展节点从最优的局部途中选择

14、一个节点扩展l计算耗散值的过程对当前的局部图从新计算耗散值20AO*算法举例其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n821目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：322目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)523目标目标初始节点n0n1n2n3n4n5n6n7n

15、8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)224目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2125l AO*算法过程 ：1、建立一个搜索图G，G:s，计算q（s）h（s），IF GOAL（s）THEN M（s，SOLVED）；开始时图G只包括s，耗散值估计为h（s），若s是终节点，则标记上能解。2、Until s已标记上SOLVED，do：3、begin4、G:FIND（G）；根据连接符标记（指针）找出一个待扩展的局部

16、解图G。5、n:G中的任一非终节点；选一个非终节点作为当前节点。6、EXPAND（n），生成子节点集nj，计算q（nj）h（nj），其中nj G，G:ADD（nj，G），IF GOAL（nj） THEN M（nj， SOLVED）；对G中未出现的子节点计算耗散值，若有终节点则加能解标记，然后把n的子节点添加到G中。7、S:n；建立含n的单一节点集合S。8、Until S为空，do：9、begin10、REMOVE（m，S）， ；这个m的子节点mc应不在S中。11、修改m的耗散值q（m）：对m指向节点集n1i，n2i，nki的每一个连接符i分别计算qi：qi（m）Ci+q（n1i）+q（nki）

17、，q（m）:min qi（m）；对m的i个连接符，取计算结果最小的那个耗散值为q（m）。加指针到min qi（m）的连接符上，或把指针修改到min qi（m）的连接符上，即原来指针与新确定的不一致时应删去。IF M（nji， SOLVED） THEN M（m， SOLVED）；若该连接符的所有子节点都是能解的，则m也标上能解。12、IF M（m， SOLVED）（q（m）q0（m）THEN ADD（ma， S）；m能解或修正的耗散值与原先估算q0不同，则把m的所有先辈节点ma添加到S中。13、end14、end26l 这个算法可划分成两个操作阶段：l 第一阶段是4-6步，完成自顶向下的图生成操

18、作，先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终节点进行扩展，并对其后继节点赋估计耗散值和加能解标记。l 第二阶段是7-12步，完成自下向上的耗散值修正计算、连接符（即指针）的标记以及节点的能解标记。耗散值的修正从刚被扩展的节点n开始，其修正耗散值q（n）取估计h（n）的所有值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈节点的耗散值，只有下层节点耗散值修正后，才可能影响上一层节点的耗散值，因此必须自底向上一直修正到初始节点。这由算法中的内循环过程完成， 272.3 博弈树搜索l博弈问题双人一人一步双方信息完备零和28分钱币问题（7）（6,1）（5,2）

19、（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走我方必胜291，极小极大过程l评价函数: 可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。 3031l 过程MINIMAX：T:（s，MAX），OPEN:（s），C

20、LOSED:（ ）；开始时树由初始节点构成，OPEN表只含有s。LOOP1:IF OPEN（ ）THEN GO LOOP2；n:FIRST（OPEN），REMOVE（n，OPEN），ADD（n，CLOSED）；IF n可直接判定为赢、输或平局THEN f（n）:0，GO LOOP1ELSE EXPAND（n）ni，ADD（ ni，T）IF d（ni）k THEN ADD（ni ，OPEN），GO LOOP1ELSE计算f（ni ），GO LOOP1；ni达到深度k，计算各端节点f值。LOOP2：IF CLOSEDNIL THEN GO LOOP3ELSE np :FIRST（CLOSED）；IF（np MAX）（f（ nciMIN）有值）THEN f（ np ）:maxf（ nci ），REMOVE np ，CLOSED）；若MAX所有子节点均有值，则该MAX取其极大值。IF （ np MIN）（f（ ncjMAX）有值）THEN f np ）:minf (ncj ），REMOVE（ np ，C