人工智能导论课件：第三章 与或图的搜索

1、上次课程回顾,盲目搜索策略 启发式搜索策略,第三章 与或图的搜索,2 3 1 8 4 7 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,或,或,或,引入,上章介绍了状态空间问题以及搜索算法，其特点是： 结点的后继结点是或的关系，只要一个后继节点得以求解，该节点也就被求解。 从初始结点到目标结点，求解的是一条路径，也就是结点的序列。,引入,方法1 满足子问题1 一个问题有多个解法 方法2 满足子问题2 方法3 满足子问题3 一个结点是否被求解，取决于该结点的部分或者全部结点（与的关系）被求解，而非一个后续结点被求解 用与或图表示。,“或”,“与”,搜索从初始节点到一组终节点集

2、N的一个解图。,与或图的搜索,与的关系（超弧线，连接符）,根结点：没有任何父结点的结点。,端结点：没有任何后继结点的结点。,3.1 基本概念,与或图是一个超图，节点间通过连接符连接。（其特例是普通图) K-连接符： 是从一个父结点指向一组k个后继结点的结点集。,耗散值的计算,k(n, N) = Cn+k(n1, N)+k(ni, N) 其中：N为终节点集 Cn为连接符的耗散值 * 明显的，若n是N的一个 元素，则k(n, N) =0,解图,在普通图中，从初始结点到目标结点，求解的是一条解路径。 与或图中某一个结点n到目标结点集N的解图类似于普通图中的一条解路径。 解图的求法是：从节点n开始，正

3、确选择一个外向连接符，再从该连接符所指的每一个后继结点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。 具有最小耗散值的解图称为最佳解图。,目标,目标,初始节点s,解图：,能解节点（SOLVED),终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子节点至少有一个能解时，该非终节点才能解。 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,不能解节点(UNSOLVED),没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有

4、一个子节点不能解时，该非终节点才不能解。,第10次课 10月07日,上次课程回顾,与或图搜索:搜索从初始节点到一组终节点集N的一个解图。 对于与或图搜索，是通过对局部图的评价来选择待扩展的节点。 解图的求法是：从节点n开始，正确选择一个外向连接符，再从该连接符所指的每一个后继结点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。 具有最小耗散值的解图称为最佳解图。 能解节点 不能解节点,与或图的启发式搜索算法AO*,启发式与或图搜索过程和普通图类似，也是通过评价函数f(n)来引导搜索过程。 对于与或图，由于局部图有多个叶结点，不能象普通图那样，通过

5、对某一个结点的评价来实现对整个局部图的评价。 对于与或图搜索，是通过对局部图的评价来选择待扩展的节点。,普通图的情况,f(n) = g(n) + h(n) 表面上是对结点n的评价，实际上是对从s到目标结点（通过n）的这条路径的评价。,n,s,与或图: 对局部图的评价,目标,目标,初始节点,a,b,c,把普通图的思想应用到与或图中，对解图进行评价，解图相当于解路径。红色和蓝色都是局部图，具体选择那条路径，选择f值最小的。,有与的关系，有或的关系，评价起来复杂一些,AO*算法,过程AO*: 建立一个搜索图G，G:=s，计算q(s)=h(s)，IF GOAL(s) THEN M(s, SOLVED)

6、； Until s已标记为SOLVED, do: Begin G:=FIND(G)； n:=G中的任一非终节点（选一个非终节点作为当前节点）。 EXPAND(n),生成子节点集ni，其中niG， G:=ADD(ni,G),计算q(ni)=h(ni)，IF GOAL(ni) THEN M(ni, SOLVED);,开始时图G只包括s，耗散值估计为h(s)，若s是终节点,则标记上能解。,根据连接符标记（指针）找出一个待扩展的局部解图G,对G中未出现的子结点添加到G中, 并计算其耗散值，若有终节点则加能解标记。,图生成过程,S:=n;建立含n的单一节点集合S.（待修正的节点集合） Until S为空

7、, do: Begin REMOVE(m, S),mc(S);这个m的子结点mc应不在S中。 修改m的耗散值q(m): 对m指向节点集(n1i,n2i,nki)的每个连接符i分别计算qi, qi (m)=Ci+q(n1i)+q(nki), q(m):= minqi(m); 加指针到minqi(m)的连接符上,或把指针修改到minqi(m)的连接符上,即原来指针与新确定的不一致时应删去. IF M(nji,SOLVED) THEN M(m, SOLVED),(j=1,k） IF M(m, SOLVED)(q(m) q0(m) THEN ADD(ma, S); end (与9匹配) end (与3

8、匹配),m 能解或修正的耗散值与 原先估算q0不同,则把m的 所有先辈节点ma,添加到S 中. （修正向上传递）,若该连接符的所有子节点都是能解的,则m也标上能解.,对m的i个连接符，取计算结果最小的哪个耗散值为q（m）,耗散值修正,AO*算法说明,算法划分成两个阶段： 1）是一个自上而下的图生长过程，先通过有标记的连接符，找到目前为止最好的一个局部解图， 2）是一个自下而上的耗散值修正计算，连接符的标记以及结点的能解标记。,AO*算法举例,其中： 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 设

9、：K连接符 的耗散值为K,红色：4 黄色：3,1次循环之后,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：4 蓝色：6,n1,5,2次循环之后,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：5 蓝色：6,2,3次循环之后,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：5 蓝色：6,2,1,4次循环之后,两个过程,图生成过程，即扩展节点 从最优的局部图中选择一个节点扩展 计算耗散值的过程 对当前的局部图重新计算耗散值,对于2次循环中，先扩展结点n4还是n5好呢？ 一般选择一个最可能导致该局

10、部图耗散值发生较大变化的结点先扩展（因为选择这个结点先扩展，会促使及时修改局部解图的标志。,3.3 博弈树搜索,博弈问题 双人 一人一步 双方信息完备 (对垒双方看到的信息是一样的，不存在一方看到另一方看不到的情况） 零和（对一方有利的走棋，对另一方是不利的，不存在对双方均有利或者均无利的棋）,Grundy博弈（分钱币游戏）,有一堆数目为N的钱币，有两个选手轮流分堆，要求每个选手每次只把其中某一堆分成数目不相等的两小堆（如果分的相等的话，输） 以7个钱币为例。,分钱币问题,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,

11、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）,对方先走,我方必胜,分钱币问题状态空间图,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举。 目标：寻找一步好棋，等对手回敬后在考虑寻找另一步好棋这种实际可行的策略。,1，极小极大搜索过程（1）,是博弈树搜索的基本方法，目前常用的-剪枝搜索方法，也从极小极大搜索过程发展而来。 假定一个评价函数可以对所有的棋局进行评价： 当评价函数0时,表示对我方有利，越大越有利； 当评价函数0时,表示对对方有利，越

12、小越有利。,极小极大搜索过程（2）,假定双方都是对弈高手，在决定走棋时，会尽可能多看几步，并都选评价函数有利的走棋。 极小极大搜索过程模拟人下棋的思考过程,策略,极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一个相对较好的走法来走，即在有限的搜索深度范围内进行求解。 定义静态估计函数f, 以便对棋局作出优劣估值，主要对端结点的“价值”进行度量。 f0, 表对我方有利，f0,表对方有利，f=0,表势均力敌；f=,表我方胜，f=- 表对方胜,1，极小极大过程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,端结点给出数字使用静态函数f

13、计算得到，其他的使用倒推方法取值,算法的三个阶段,用宽度优先法生成规定深度的全部博弈树，然后对其端结点计算其静态估计函数。 从底向上逐级求非端结点的倒推估计值，直到求出初始结点的倒推值f(s)为止。 再由f(s)选出相对较好的走步。,算法,极大极小过程MINIMAX： 1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );开始时树由初始节点构成，OPEN表只含有S. 2. LOOP1: IF OPEN =( ) THEN GO LOOP2; 3. n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);将n放到CLOSED表的前面， 4. I

14、F n可直接判定为赢, 输或平局 THEN f(n):= -0，GO LOOP1 ELSE EXPAND(n)ni， ADD (ni ，T) IF dni k THEN ADD(ni, OPEN) ,GO LOOP1 ELSE 计算f(ni); ni达到深度k,计算各端节点f值.,算法(续）,5. LOOP2：IF CLOSED=NIL,THEN GO LOOP3 ELSE nd=FIRST(CLOSED); 6.IF(nd MAX) (f(nci MIN)有值) THEN f(nd):=maxf(nci),REMOVE(nd，CLOSED), GO LOOP2; 若MAX所有子节点均有值,则

15、该MAX取其极大值. ELSE IF(nd MIN) (f(nci MAX)有值) THEN f(nd):=minf(nci),REMOVE(nd，CLOSED), GO LOOP2; 若MIN所有子节点均有值，则该MIN取其极小值. 7. GO LOOP2; 8.LOOP3:IF f(s)NIL THEN EXIT(END M(Move,T) ; s有值,或则结束或标记走步。,算法的一点说明,对手回应后，再以当时的状态作为起始状态s，重复调用该过程。 原理性的，对复杂的问题不实用的,举例九宫格棋牌,在九宫格棋盘上，两选手（MAX和MIN）轮流在棋牌中摆各自的棋子（一次一枚），谁先取得三子一线

16、的结果就获胜。 设MAX用（）表示，MIN用（ O ）表示，f(p)表示对格局p的评价值。 若p对任何一方都不是获胜的格局，则 f(p)=(所有空格都放上MAX的棋子之后，MAX的行，列，对角线成三子一线的总和)-(所有空格都放上MIN的棋子之后，MIN的行，列，对角线成三子一线的总和),f(p)的计算,若当前的格局p如图： 所有空格都放上MAX的棋子之后，MAX的行，列，对角线成三子一线的情况（总数=6）,f(p)的计算,若当前的格局p如图： 所有空格都放上MIN的棋子之后，MIN的行，列，对角线成三子一线的情况（总数=4） 则f(p)=6-4=2,一字棋第1阶段的搜索树,最好走棋是中间位置

17、,引入：-剪枝,MINMAX过程是把搜索树的生成和棋局估值两个过程分开进行： 即先生成全部的搜索树，然后再进行端节点静态估值和倒推值计算， 这会导致效率大大降低（缺点）。 考虑：把生成和倒推估计结合在一起，再根据一定的条件，尽早剪除一些无用的分支- -过程的思想。,回顾：极小极大过程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,端结点给出数字使用静态函数f计算得到，其他的使用倒推方法取值,回顾：极小极大过程,0,-3,3,0,3,0,极大,极小,a,b,端结点给出数字使用静态函数f计算得到，其他的使用倒推方法取值,-搜索过程,可以看到，在

18、上例中，实际上是把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早剪掉一些无用的分支，但不影响效果，这就是-过程的基本思想。,-剪枝,极大节点的下界为。 极小节点的上界为。,剪枝,剪枝：若任一极小值层节点的值它任一先辈极大值层节点的值， 即 后辈节点的值祖先节点的值时， 则终止该极小值层中这个MIN节点以下的搜索，并设置这个MIN节点的最终的倒推值为。(极小值层节点的剪枝),剪枝,剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值， 即（后继层）（先辈层） 则终止该极大值层中这个MAX节点以下的搜索过程，并设置这个MAX节点的最终倒推值为。 (极大值层节点的剪枝),剪枝的条件： 后辈节点的值祖先节点的值时， 剪枝 后辈节点的值祖先节点的值时， 剪枝 简记为： 极小极大，剪枝 极大极小，剪枝,0, (2) 0,(3),5,(4)=0, (5) 0,(6),-3,(7) -3,(8) =0, (9) 0,(10),3,(11) =3,(12) 3,(13) =0, (14) 0,(15),5,(16) 5,(17),4,(18) 4,(19),1,(20) =1,(21) 1