搜索
4/17/20201第四章可分解产生式系统的搜索策略学习目标：了解一般的与/或图搜索问题，掌握与/或图的启发式搜索算法AO*。了解博弈树搜索问题，掌握博弈树搜索中的极小极大方法和α-β剪枝搜索方法。重点：AO*算法，α-β剪枝算法。4/17/20202第二章可分解产生式系统中提到的与/或树表示，其中加到每一个节点上AND或OR的标记是取决于该节点对其父节点的关系。如复合状态分解后拥有一组“与”关系的后继节点；而分量状态经可应用规则作用后，生成一组“或”关系的后继节点。与/或树是本章介绍的与/或图的特例。在一般与/或图中，一个节点可能是复合状态的组成部分，而同时又是一个规则应用的结果，很难说明它是与后继还是或后继．因此，不再区别AND节点或OR节点．但在称谓上沿用习惯，仍把这种结构称作与/或图。4.1与/或图搜索4/17/20203例.一个与/或图4/17/20204与/或图搜索定义：与/或图是一种超图．在超图中父亲节点和一组后继节点用超弧连接．超弧又叫k-连接符．k-连接符:一个父节点指向一组k个有与关系的后继节点，这样一组弧线称为一个k-连接符．k1时，用一圆弧标记此连接符。Note:若所有的连接符都是1-连接符，则得到的就是与/或图的特例--普通有向图。4/17/20205与/或图搜索与/或树:每一个节点最多只有一个父亲的与/或图．根节点:在AND/OR树或AND/OR图中没有父节点的节点.叶节点:在AND/OR树或AND/OR图中没有后继的节点．终止节点:满足终止条件的节点．4/17/20206与/或图搜索一个可分解的产生式系统定义一个隐含的与/或图．图的根节点表示产生式系统的初始状态描述，连接符表示对一状态描述应用产生式规则或把这一状态描述分解成若干组成部分．可分解产生式系统的任务:从隐含的与/或图出发找出一个从根节点出发到终止节点集的解图。4/17/20207例重写规则：n0→n1n0→n5，n4n1→n2n1→n3n2→n3n2→n5，n4n3→n5，n6n4→n5n4→n8n5→n7,n8n5→n6n6→n7,n84/17/20208练习1：假定我们有一个产生式系统，基于如下重写规则：R1：n0→n1,n2R5：n2→n6,n7R2：n0→n2,n3R6：n3→n5,n6R3：n1→n2R7：n4→n2R4：n1→n4R8：n5→n7请用与/或图表示此产生式系统。4/17/20209练习2：一个产生式系统使用下面一组重写规则，这些重写规则把左面的数字转换成右边的数字串。6→3,34→3,16→4,23→2,14→2,22→1,1使用这些规则把6转换成由1组成的数字串。请用与/或图表示此产生式系统。4/17/202010与/或图搜索定义设N是与/或图G的终止节点集合，图G中无回路，从节点n出发到N的一个解图是与/或图G的一个子图，用G’表示，递归定义如下：1.若n是N中的一个元素，则G’只包括节点n；4/17/202011与/或图搜索2.若n有一个从n出发的连接符k指向后继节点集合｛n1，…，nk｝，而每一个ni都有从ni出发的解图，则G’由节点n、连接符k、｛n1，…，nk｝中的每一个节点到N的解图所构成；3.否则，G没有从n出发到N的解图．4/17/202012n0n1n3n5n6n8n7an0n4n5n7n8bn0n4n5n7n8c4/17/202013与/或图搜索加权与/或图：权加在连接符上。假定所有连接符的费用均大于某一小的正数ε。使用连接符的费用可以计算解图的费用．设从节点n到终止节点集合N的解图的费用用k(n,N)表示，则k(n,N)递归定义如下：1.若n是N中的元素，则k(n,N)=0；4/17/202014与/或图搜索2.若有从n出发的一个连接符指向它的解图后继节点｛n1，…，ni｝，设此连接符的费用为Ci，则:k(n,N)=Ci+k(n1,N)+…+k(ni,N)最佳解图：具有最低费用的解图4/17/202015设k-连接符的费用为k，计算k(n0,N)n0n1n3n5n6n8n7an0n4n5n7n8bn0n4n5n7n8c4/17/202016与/或图搜索假定h*(n)是从n出发的最佳解图的费用，h(n)是h*(n)的估计值。利用h(n)指导对AND/OR图的启发式搜索。4/17/202017与/或图搜索在AND/OR图中，对任意连接符的单调限制是h(n)≤c+h(n1)+…+h(nk)其中，n是任意节点，c是从n出发的连接符的费用，n1，…，nk是n的在此连接符下的后继节点。Note:若对于所有的终止节点，都有h(n)＝0，则单调限制还隐含着h对所有的节点n，都有：h(n)≤h*(n)。4/17/202018搜索过程还要标记能解节点（SOLVED），为此给出如下定义：能解节点（SOLVED）①终止节点是能解节点；②若非终止节点有“或”子节点时，其子节点有一能解，则该非终止节点是能解节点；③若非终止节点有“与”子节点时，若其子节点均能解，则该非终止节点是能解节点。4/17/2020194.2与/或图的搜索算法……算法AO*AO*算法解析：回忆：普通图搜索中的A算法：对当前搜索图的“前沿”（即在OPEN表中的节点）节点进行评价，选取f值最小的节点进行扩展。回想一下，f是如何定义的？f(n)=g(n)+h(n)，其中g(n)：已经求得的当前搜索图中从初始节点到当前节点n的最优路径费用。h(n)：从n到目标节点的最优路径费用的估计值。结论：对节点n的评价，实际上是对初始节点--节点n--目标节点这一条路径的评价。4/17/202020AO*算法解析：在与/或图搜索中，由于“与”节点的存在，单纯对一个节点的评价已经不能反映解图的全面情况。与/或图中的解图相当于普通图中的解路径。从对节点n的评价，实际上是对'初始节点--节点n--目标节点'这一条路径的评价这一思路出发，可以很容易的想到，能否通过对局部解图进行评价，来达到类似于普通图中A*搜索的目的。AO*算法，正是这样的一种适用于与/或图的搜索算法。4/17/202021AO*算法解析：AO*算法可以划分为两个阶段。第一阶段：自顶向下的图生成过程。（对于每一个已经扩展了的节点，算法都有一个指针，指向该节点的后继节点中费用值小的那个连接符。）从初始节点出发，先通过有指针标记的连接符，向下搜索，一直到找到未扩展的节点为止（找到目前为止费用值最小的一个局部解图）。然后对其中一个非终止节点进行扩展，并对其后继节点赋费用值和加能解标记。4/17/202022AO*算法解析：第二阶段：费用值计算过程。完成自下向上的费用值修正计算、指针的标记以及节点的能解标记。4/17/202023AO*算法解析：两个图G：搜索图G’：局部解图（准部分解图）（可能变化的）两个函数h(n)：启发函数（静态）对h*(n)的估计q(n)：费用函数（动态变化）两重循环外层：从上向下扩展内层：从下向上修改费用q值、标记指针4/17/202024AO*算法解析：两种标记SOLVED：标记能解节点—表明此节点的解图已找到指针：标记连接符，用于计算G’4/17/2020251与/或图搜索……算法AO*ProcedureAO*1．建立一个只由根节点构成的搜索图G．s的费用q(s):=h(s),G’:=G．如果s是目标，标记s为SOLVED.2．Untils被标记为SOLVED，do：4/17/2020263．begin4．通过跟踪从s出发的有标记的连接符计算部分解图G’（G的连接符将在以后的步骤中标记）5．在G’中选一个非终止的叶节点n.6．扩展节点n产生n的所有后继，并把它们连到图G上，对于每一个不曾在G中出现的后继nj，q(nj):=h(nj)，如果这些后继中某些节点是终止节点，则用SOLVED标记。与/或图搜索……算法AO*4/17/2020277．S:＝{n}；建立一个只由n构成的单元素集合S。8．UntilS变空，do：9．begin10．从S中删除节点m，满足m在G中的后裔不出现在S中与/或图搜索……算法AO*4/17/20202811．按以下步骤修改m的费用q(m)：对于每一从m出发的指向节点集合{n1i，…，nki}的连接符，计算qi(m)=ci+q(n1i)+…+q(nki)，q(m):＝min{qi(m)}。(1)将指针标记加到实现此最小值的连接符上。(2)如果本次标记与以前的不同，抹去先前的标记。(3)如果这个连接符指向的所有后继节点都标记了SOLVED，则把m标上SOLVED．与/或图搜索……算法AO*4/17/20202912．如果m标记了SOLVED或者如果m的修改费用与以前的费用不同，则把m的通过指针标记的连接的所有父节点加到S中．13．end14．end与/或图搜索……算法AO*4/17/2020302AO*算法应用举例设某个问题的状态空间如图所示。h(n0)＝0，h(n1)＝2，h(n2)＝4，h(n3)＝4，h(n4)＝1，h(n5)＝1，h(n6)＝2，h(n7)＝h(n8)＝0（目标节点）。假设k-连接符的费用值为k。4/17/202031图4.3(a)一次循环后4/17/202032图4.3(b)两次循环后4/17/202033图4.3(c)三次循环后04/17/202034图4.3(d)四次循环后4/17/202035从n0开始，沿指向连接符的指针找到的解图即为搜索的结果。n0给出的修正费用值q(n0)＝5就是解图的费用值。图4.3(e)搜索得到的解图4/17/202036Note（1）在第6步扩展节点n时，若不存在后继节点（即陷入死胡同），则可在第11步中对m（即n）赋一个高的q值，这个高的q值会依次传递到s，使得含有节点n的子图具有高的q（s），从而排除了被当作候选局部解图的可能性。4/17/202037(2)如果一个与／或图存在解图，如果对于图中所有的节点n都有h（n）≤h*（n），并且启发函数h满足单调限制，则AO*算法必然终止于找出最佳解图。4/17/202038练习1’：假定我们有一个产生式系统，基于如下重写规则：R1：n0→n1,n2R5：n2→n6,n7R2：n0→n2,n3R6：n3→n5,n6R3：n1→n2R7：n4→n2R4：n1→n4R8：n5→n7（1）用与/或图表示此产生式系统。（2）若h(n0)=0,h(n1)=2,h(n2)=4,h(n3)=4,h(n4)=3,h(n5)=1,h(n6)=0,h(n7)=0,为启发函数，k-连接符的费用为k，求n0到{n6,n7}的最佳解图。（要求：使用AO*算法，画出各次循环图，标明各点费用q(n)，画出最后的最佳解图，并指明最佳解图的费用）4/17/202039练习2’：一个产生式系统使用下面一组重写规则，这些重写规则把左面的数字转换成右边的数字串。6→3,34→3,16→4,23→2,14→2,22→1,1使用这些规则把6转换成由1组成的数字串。假设k-连接符的费用是k，用数字1标记的节点的h函数值是0，用数字n(n≠1)标记的节点的h函数值是n。请用AO*算法描述解题过程（要求：画出各次循环图，标明各点费用q(n)，画出最后的最佳解图，并指明最佳解图的费用）。4/17/2020404.4博弈树搜索博弈具有竞争或对抗性质的行为称为博弈行为。比如日常生活中的下棋，打牌等。在这类行为中，参加斗争或竞争的各方各自具有不同的目标或利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。博弈论GameTheory博弈论就是研究博弈行为中斗争各方是否存在着最合理的行为方案，以及如何找到这个合理的行为方案的数学理论和方法。博弈论亦名“对策论”、“赛局理论”，属应用数学的一个分支,目前在生物学，经济学，国际关系，计算机科学,政治学，军事战略和其他很多学科都有广泛的应用。4/17/202041博弈论历史博弈论思想古已有之，我国古代的《孙子兵法》就不仅是一部军事著作，而且算是