第二章-与或图搜索问题课件

第二章第二章 与或图搜索问题与或图搜索问题 华北电力大学华北电力大学 计算机系计算机系 刘丽刘丽学习目标学习目标 了解一般的与或图搜索问题掌握与或图的启发式搜索算法AO*了解博弈树搜索问题掌握博弈树搜索中的极小极大方法-剪枝搜索方法7/16/20242华北电力大学华北电力大学知识点知识点 7/16/20243华北电力大学华北电力大学与或图搜索问题与或图搜索问题状态空间搜索问题 一个节点的后继节点之间是“或”的关系 与或图搜索问题一个节点其部分或全部后继节点是“与”的关系博弈树的搜索 7/16/20244华北电力大学华北电力大学简单的与或图例子简单的与或图例子 目标1目标2初始节点sabc超图超弧线（连接符）K-连接符：从父节点指向一组 K个后继节点的节点集（K1 时注意小圆弧）根节点：没有任何父节点的节点端（叶）节点：没有任何后继节点 的节点S两个连接符1-连接符指向a（或节点）2-连接符指向b、c（与节点）目标2b的与节点（2-连接符）c的或节点（1-连接符）7/16/20245华北电力大学华北电力大学2.1 基本概念基本概念与或图是一个超图，节点间通过连接符连接K-连接符：从一个父节点指向一组k个后继节点的节点集.K个7/16/20246华北电力大学华北电力大学基本概念基本概念解图与或图中某一个节点n到节点集N的一个解图类似于普通图中的一条解路径解图的求法：从节点n开始，正确选择一个外向连接符，再从该连接符所指的每一个后继节点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素一个元素为止图2.2给出n0n7，n8的三个解图7/16/20247华北电力大学华北电力大学基本概念基本概念解图：7/16/20248华北电力大学华北电力大学基本概念基本概念解图的递归定义解图的递归定义一个与或图G中，从节点n到节点集N的解图记为G，G是G的子图若n是N的一个元素，则由单一节点组成若n有一个指向节点n1，nk的外向连接符K，使得从每一个ni到N有一个解图（i=1，k），则由节点n，连接符K，及n1，nk中的每一个节点到N的解图所组成否则n到N不存在解图在搜索解图的过程中，还须要进行耗散值的计算 7/16/20249华北电力大学华北电力大学解图耗散值的计算解图耗散值的计算若解图的耗散值记为k(n，N)，则可递归计算如下：若n是N的一个元素，则k(n，N)0若n是一个外向连接符指向后继节点n1，ni，并设该连接符的耗散值为Cn，则 k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N为目标节点集 .i个nn1n2ni7/16/202410华北电力大学华北电力大学例例:k-连接符的耗散为连接符的耗散为kK(n0,n7,n8)=8K(n0,n7,n8)=7K(n0,n7,n8)=5具有最小耗散值的解图称为最佳解图，其值也用h*(n)标记上例中h*(n0)5 h(n)表示节点表示节点n到目标节点集的最佳解图耗散值的估计到目标节点集的最佳解图耗散值的估计 7/16/202411华北电力大学华北电力大学基本概念基本概念局部局部图：图：单一节点是一个局部图对于一个局部图的任意叶节点n，选择一个n的外向连接符K，则该局部图、外向连接符K，以及K所连接的n的后继节点一起组成的图，仍然组成一个局部图局部图的耗散值k(n，N)，则：若n是局部图的一个叶节点，则k(n，N)h(n)若n是一个外向连接符指向后继节点n1，ni,并设该连接符的耗散值为Cn，则 k(n，N)Cn+k(n1，N)+k(ni，N)7/16/202412华北电力大学华北电力大学能解能解节点节点(Solved)终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解7/16/202413华北电力大学华北电力大学不能解节点不能解节点(Unsolved)没有后裔的非终节点是不能解节点若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解7/16/202414华北电力大学华北电力大学普通图搜索的情况普通图搜索的情况f(n)=g(n)+h(n)对n的评价实际是对通过对通过n的这条路径的评价的这条路径的评价ns7/16/202415华北电力大学华北电力大学与或图与或图:对局部图的评价对局部图的评价目标目标初始节点abc7/16/202416华北电力大学华北电力大学AO及及AO*搜索算法搜索算法目目的的：在在问题的的完完整整的的隐含含图中中扩展展生生成成出出包包含含初初始始结点和目的点和目的结点集合的点集合的连通的明通的明显子子图方方法法：必须对当前已生成出的与或图中的所有结点实施是否为可解结点的标注注过程程，如果起始结点被标注为可解的，则搜索过程可成功地结束；如果起始结点还不能被标注为可解的，则应当继续扩展展生生成成结点（尽可能地记录，所有生成的结点中，哪些结点被标注了可解的，以便减少下一次标注过程的工作量）同同样地地，对不不可可解解结点点也同也同样如此如此7/16/202417华北电力大学华北电力大学AO及及AO*搜索算法搜索算法利用结点的可解/不可解性质，能从搜索图中删去可解结点的任何不可解结点的子结点；同样地，能删去不可解结点的所有的子结点搜索这些被删除的结点是没有意义的，而只会降低搜索效率n与普通图搜索算法相类似，与/或图搜索算法有盲目搜索，如广度优先搜索法、深度优先搜索法等；也有启发式搜索，如AO及AO*搜索法 7/16/202418华北电力大学华北电力大学AO*算法算法两个过程两个过程1图生成过程，即扩展节点对于每一个已经扩展了的节点，AO*算法都有一个指针，指向该节点的后继节点中，耗散值小的那个连接符从最优的局部图中选择一个节点扩展图生成过程，就是从初始节点出发，按照该指针向下搜索，一直到找到一个未扩展的节点为止。然后扩展该节点。并对其后继节点赋估计估计耗散值和加能解标记 7/16/202419华北电力大学华北电力大学AO*算法算法两个过程两个过程2计算耗散值的过程对当前的局部图重新计算耗散值，是逆向的计算过程计算出节点n相对于每一个外向连接符的耗散值，从中选择一个最小值作为n的耗散值。并标记一个指针指向产生最小耗散值的外向连接符对于n的父节点，进行同样的计算，重复这一过程，直到初始节点s为止这时，从s出发，选择那些指针所指向的连接符得到的局部图，为当前耗散值最小的局部图7/16/202420华北电力大学华北电力大学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设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n87/16/202421华北电力大学华北电力大学目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：3AO*算法举例算法举例7/16/202422华北电力大学华北电力大学目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5AO*算法举例算法举例7/16/202423华北电力大学华北电力大学目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2AO*算法举例算法举例7/16/202424华北电力大学华北电力大学目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21AO*算法举例算法举例7/16/202425华北电力大学华北电力大学AO*与与A的区别的区别AO*算法不能像A算法那样，单纯靠评价某一个节点来评价局部图由于k-连接符连接的有关子节点，对父节点能解与否以及耗散值都有影响，因而显然不能象A算法那样优先扩展其中具有最小耗散值的节点算法仅适用于无环图的假设，否则耗散值递归计算不能收敛，因而在算法中还必须检查新生成的节点已在图中时，是否是正被扩展节点的先辈节点A算法有OPEN和CLOSED表，而AO*算法只用一个结构G，它代表到目前为止已明显生成的部分搜索图，图中每一个节点的h(n)值是估计最佳解图，而不是估计解路径7/16/202426华北电力大学华北电力大学2.3 博弈博弈树搜索搜索博弈问题双人，一人一步双方信息完备零和：即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋用与或图表示在决定自己走步时只需考虑对自己有利的一步“或”考察对方时,则应考虑对方所有可能的走步“与”两人严格地轮流走步，使博弈状态图呈现出严格的与和或的交替层次可设计特殊的与/或图搜索算法，即博弈树搜索算法7/16/202427华北电力大学华北电力大学分钱币问题（分钱币问题（Grundy博弈）博弈）（7）（6,1）（5,2）（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）对方先走我方必胜对方扩展的节点我方扩展的节点对方扩展的节点我方扩展的节点对方扩展的节点7/16/202428华北电力大学华北电力大学与或图搜索技术与或图搜索技术问题对简单的博弈或复杂博弈的残局，可以用类似于与或图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法对许多博弈问题不可实现：中国象棋：一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年不可能穷举即使用了强有力的启发式搜索技术，也不可能使分枝压到很少 7/16/202429华北电力大学华北电力大学与或图搜索技术与或图搜索技术解决：实用策略：把目标确定为寻找一步好棋，等对手回敬后再考虑寻找另一步好棋每一步结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定搜索策略可采用宽度、深度或启发式方法，一个阶段搜索结束后，要从搜索树中提取一个优先考虑的“最好的”走步，这就是实用策略的基本点极小极大搜索策略就是其中的一种 7/16/202430华北电力大学华北电力大学极小极大搜索过程极小极大搜索过程(1)假定有一个评价函数可以对所有棋局评估：评价函数值大于0，表示棋局对我方有利，对对方不利评价函数小于0时，表示棋局对我方不利，对对方有利评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜7/16/202431华北电力大学华北电力大学极小极大搜索过程极小极大搜索过程(2)假设：双方都是对弈高手在只看一步棋的情况下，我方一定走评价函数值最大的一步棋对方一定走评价函数值最小的一步棋在只看一步的情况下最好的棋，从全局来说不一定就好，还可能很不好为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋 7/16/202432华北电力大学华北电力大学极小极大搜索过程极小极大搜索过程(3)当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步7/16/202433华北电力大学华北电力大学极小极大搜索过程极小极大搜索过程叶节点的评价函数叶节点的评价函数是一个静态估计函数f对棋局的势态（节点）作出优劣估值可根据势态优劣特征来定义（主要用于对端节点的“价值”进行度量）一般规定：有利于MAX的势态，f（p）取正值；有利于MIN的势态，f（p）取负值；势均力敌的势态，f（p）取0值若f（p），则MAX赢，若f（p），则MIN赢顶节点深度d0，MAX代表程序方，MIN代表对手方，MAX先走7/16/202434华北电力大学华北电力大学例例1端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值 当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程7/16/202435华北电力大学华北电力大学例例2：用极大极小方法进行搜索，搜索顺序是从下到上，从左到右用极大极小方法进行搜索，搜索顺序是从下到上，从左到右7/16/202436华北电力大学华北电力大学-剪枝剪枝例子（一字棋）例子（一字棋）在九宫格棋盘上，两位选手轮流摆棋子，谁先取得三子一线的结果就取胜程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走7/16/202437华北电力大学华北电力大学-剪枝剪枝例子（一字棋）（续）例子（一字棋）（续）f(p)规定：若p对任何一方来说都不是获胜的格局，则f(p)(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角)的总数)(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)若p是MAX获胜的格局，则f(p)若p是MIN获胜的格局，则f(p)当p的格局如下时，则可得f(p)642 7/16/202438华北电力大学华北电力大学-剪枝剪枝基本思想：MINI-MAX过程：把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。-剪枝方法剪枝方法：把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝，同样可获得类似的效果7/16/202439华北电力大学华北电力大学-剪枝剪枝例子（一字棋）例子（一字棋）7/16/202440华北电力大学华北电力大学-剪枝规则剪枝规则极大值层的下界值为极小值层的上界值为 7/16/202441华北电力大学华北电力大学-剪枝剪枝极大节点的下界为。极小节点的上界为剪枝的条件：后辈节点的值祖先节点的值时，剪枝，终止该极小值层中这个MIN节点以下的搜索。MIN节点的最终倒推值即后辈节点的 值祖先节点的值时，剪枝，终止该极大值层中这个MAX节点以下的搜索。MAX节点的最终倒推值即简记为：极小极大，剪枝；极大极小，剪枝7/16/202442华北电力大学华北电力大学-剪枝应注意的问题剪枝应注意的问题 1.比较都是在极小节点和极大节点间进行的2.是与“先辈层”节点比较，不只是与父辈节点比较3.只有一个节点的值“固定”后，其值才能向父节点传递4.-剪枝方法与极小极大方法得到的结果是一致的，并没有因为提高效率，而降低得到最佳走步的可能性5.在实际搜索时，是边生成边估值6.在实际程序实现时，首先规定一个搜索深度，然后按类似于深度优先搜索的方式，生成节点。在节点生成过程中，如在某一节点处发生了剪枝，则该节点其余未生成的节点就不再生成了7/16/202443华北电力大学华北电力大学-剪枝（续）剪枝（续）7/16/202444华北电力大学华北电力大学THE END7/16/202445华北电力大学华北电力大学