人工智能引论课件 第六章 基于经验的启发式搜索

第六章基于经验的启发式搜索6.1启发式搜索的基本思想6.2状态空间的启发式搜索6.3与或图的启发式搜索6.4博弈树的搜索6.1启发式搜索的基本思想前面讨论的搜索方法都是按事先规定的、根据结点的深度制定的路线进行搜索，搜索过程机械，具有较大的盲目性,生成的无用结点较多，搜索空间较大，因而效率不高。除了结点的深度信息之外，如果能够利用结点暗含的与问题相关的一些特征信息来预测目标结点的存在方向，并沿着该方向搜索，则有希望缩小搜索范围，提高搜索效率。利用结点的特征信息来引导搜索过程的一类方法称为启发式搜索。任何一种启发式搜索算法在生成一个结点的全部子结点之前，都将使用算法设计者提供的评价函数判断这个“生成”过程是否值得进行。评价函数通常为每个结点计算一个整数值，称为该结点的评价函数值。通常，评价函数值小的结点被认为是值得进行“生成”过程。按照惯例，将“生成结点n的全部子结点”称为“扩展结点n”。启发式搜索（最好优先搜索）确定路径6.1.1启发信息与评价函数用来评估结点重要性的函数称为评价函数。评价函数f（n）对从初始结点S0出发经过、结点n到达目标结点Sg的路径代价进行估计。其一般形式为g（n）表示从初始结点S0到结点n的已获知的最小代价；h（n）表示从n到目标结点Sg的最优路径代价的估计值，它体现了问题的启发式信息。所以，h（n）被称为启发式函数。f（n）由g（n）和h（n）两部分组成，启发式搜索算法可以使用f（n）的不同组合，进而表现出不同的特性。例如，有的算法使用f（n）=g（n），有的算法使用f（n）=h（n），有的算法使用f（n）=g（n）+h（n）6.1.2启发式搜索策略启发式搜索策略的目标是，通过优先考察最有希望出现在较短解路径上的节点，来显著提高搜索的有效性。启发式搜索是利用启发性信息进行指导的搜索。启发性信息就是有利于尽快找到问题之解的信息，按其用途可分为如下3种：（1）用于扩展节点的选择。即决定应先扩展哪一个节点，以免盲目地扩展。（2）用于生成节点的选择。即在扩展一个节点的过程中，用于决定将生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。（3）用于删除节点的选择。即决定应该从搜索树中抛弃或修剪哪些节点，以免造成进一步的时空浪费。需要指出的是，不存在适合所有问题的万能启发性信息，即不同的问题有不同的启发性信息。本章只讨论利用上述第一种启发性信息的状态空间的搜索方式，即决定哪个是下一步要扩展的节点。6.2状态空间的启发式搜索状态空间的启发式搜索指在状态空间中，利用启发式信息来指导搜索过程的一类算法。其目标是通过评估每个状态到目标状态的估计成本，从而优先探索那些看起来更有希望的路径，以提高搜索效率和找到最优解。启发式搜索结合了传统的状态空间搜索和启发式方法，通过减少需要探索的状态数量来加快问题求解过程。下面分别介绍以启发式函数f（n）=h（n）作为指导节点扩展的搜索算法，即最好优先搜索算法（全局最优法）；以代价函数f（n）=g（n）指导节点扩展的搜索算法，即分支限界法；以评价函数f（n）=g（n）+h（n）作为指导节点扩展的搜索算法的最佳图搜索法A*6.2.1最好优先搜索算法为了处理环，最好优先搜索算法用OPEN表和CLOSED表记录状态空间中那些被访问过的所有状态。这两个表中的结点及它们关联的边构成了状态空间的一个子图，称为搜索图。OPEN表存储一些结点，其中每个结点n的启发式函数值已经计算出来，但是n还没有被“扩展”。CLOSED表存储一些结点，其中每个结点已经被扩展。该类算法每次选代从OPEN表中取出一个较优的结点n进行扩展，将n的每个子结点根据情况放入OPEN表。算法循环直到发现目标结点或者OPEN表为空。算法中的每个节点带有一个父指针，该指针用于合成解路径。6.2.1最好优先搜索算法ProcedureBest-FirstSearchBegin建立只含初始结点S0的搜索图G，计算f（S0）；将S0放入OPEN表；将CLOSED表初始化为空。WhileOPEN表不空DoBegin从OPEN表中取出f（n）值最小的结点n，将从OPEN表中删除并放入CLOSED表。If

n是目标结点Then根据n的父指针指出从S0到n的路径，算法停止。ElseBegin扩展结点nIf

结点n有子结点ThenBegin（1）生成n的子结点集合{mi}把mi作为n的子结点加入到G中，并计算f（mi）。（2）Ifmi未曾在OPEN和CLOSED表中出现，Then将它们配上刚计算过的f值，将mi的父指针指向n，并把它们放入OPEN表。（3）Ifmi已经在OPEN表中，Then该结点一定有多个父结点。在这种情况下比较mi相对于n的f值和mi相对于其原父指针指向的结点的值，若前者不小于后者，则不做任何更改；否则将mi的f值更改为mi相对于n的f值，mi的父指针更改为n。最好优先搜索算法流程：6.2.1最好优先搜索算法（4）Ifmi已经在CLOSED表中，Then该结点同样也有多个父结点。在这种情况下，比较mi相对于n的f值和mi相对于其原父指针指向的结点的值如果前者不小于后者，则不作任何更改；否则将mi从CLOSED表移到OPEN表，置mi的父指针指向n。

（5）按f值从小到大的次序，对OPEN表中的结点进行重新排序。EndEndEndEnd最好优先搜索算法流程（接上表）：上述搜索算法生成一个明确的图G（称为搜索图）和一个G的子集T（称为搜索树），图G中的每一个结点也在树T上。搜索树是由结点的父指针来确定的。G中的每一个结点（除了初始结点S0）都有一个指向G中一个父辈结点的指针。该父辈结点就是那个结点在T中的唯一父辈结点。算法中（3）、（4）步保证对每一个扩展的新结点，其父指针的指向是已经产生的路径中代价最小的。6.2.1最好优先搜索算法贪婪最好优先算法：最好优先搜索算法是一个通用的算法框架。如果将该框架中的

f（n）实例化为h（n），则得到一个具体的算法，称为贪婪最好优先搜索（GreedyBest-FirstSearch，GBFS）算法。GBFS算法在判断是否优先扩展一个结点n时仅以n的启发值为依据。n的启发值越小，表明了从n到目标结点的代价越小，因而GBFS算法沿着n所在的分枝搜索就越可能发现目标结点。6.2.1最好优先搜索算法以八数码问题为例，令启发函数h（x）为节点x的棋局与目标棋局相比数码位置不同的个数，则搜索树如下图所示，图中节点旁边的数字为该节点启发函数的值6.2.2分支限界法分支限界法在文献中通常称为统一代价搜索（Uniform-CostSearch）。按照递增的代价--更精确地说，按照非递减代价制订路径。路径的估计代价很简单：f（n）=g（n），不采用剩余距离的启发式搜索；或等价地说，估计h（n）处处都为0。这种方法与广度优先搜索的相似性显而易见，即首先访问最靠近起始节点的节点。但是，使用分支限界法，代价值可以假设为任何正实数值。这两个搜索之间的主要区别是，最好优先搜索努力找到通往目标的某一路径，然而分支限界法努力找到一条最优路径。使用分支限界法时，一旦找到了一条通往目标的路径，这条路径很可能是最优的。为了确保这条找到的路径确实是最优的，分支限界法继续生成部分路径，直到每条路径的代价大于或等于所找到的路径的代价6.2.2分支限界法//BranchandBoundSearch.

BranchBound（Root_Node，goal）{CreateQueueQInsertRoot_NodeintoQWhile（QIsNotEmpty）{G=RemovefromIf

（G=goal）ReturnthepathfromRoot_NodetoG；elseInsertchildrenofGintotheQSortQbypathlength}//andwhileReturnfailure}分支限界法流程：6.2.2分支限界法没有启发式估计值的搜索树分支限界法（a）从根节点A开始。生成从根开始的路径（b）因为B具有最小代价，所以被扩展（c）在3个选择中，C具有最小代价，因此被扩展（d）节点H代价最低，因此被扩展（e）发现了到G2的路径，但为查看是否有路径到目标的距离更小，需扩展到其他分支（f）F和N的节点都具有15的代价：最右边的节点首先扩展（g）分支限界法其余部分6.2.2分支限界法遵循分支限界法，寻求一条到达目标的最佳路径的（a）~（f）和（g）。我们观察到，节点按照递增的路径长度扩展。搜索在（f）和（g）中继续，直到任何部分的路径的代价大于或等于到达目标的最短路径21。如（g）所示，请观察分支限界的其余部分。分支限界算法接下来的4个步骤如下。步骤1：到节点N的路径不能被延长。步骤2：下一条最短路径，A→B-E被延长了；当前，它的代价超过了21。步骤3：到节点M和N的路径不能被延长。步骤4：最小部分路径，具有的代价≤21被延长了。当前，代价是29，超过了开始到目标最短路径。在（g）中，分支限界法发现到达目标的最短路径是A到C到H到G2，代价为21。6.2.2分支限界法下图是五个城市交通路线图，A城市是出发地，E城市是目的地，两城市之间的交通费用（代价）如图中数字所示。试求从A到E最小费用的旅行路线。画出其如（b）所示的代价树。在代价树中，首先对A进行扩展，得到C1和B1，由于C1的代价小于B1的代价，所以把C1送入CLOSED表进行考察。对C1扩展得到D1，由于B1的代价小于D1，所以把B1送入CLOSED表进行考察。扩展B1得到D2和E1在OPEN表中的D1，D2和E1三个节点中，它们的代价g（D1）<g（D2）<g（E1），所以把D1送入CLOSED表进行考察。扩展D1得到E2和B2在OPEN表中g（E2）=g（D2）<g（B2）<g（E1），所以考察E2。E2是目标状态节点。所以采用分支限界法得到路径为ACBE，这是一条最小费用路径。6.2.3最佳图搜索算法A*如果最好优先搜索算法中的f（n）被实例化为f（n）=g（n）+h（n），则称之为A算法。进一步细化，如果启发函数h满足对于任一结点n，h（n）的值都不大于n到目标结点的最优代价，则称此类A算法为A*算法。A*算法在一些条件下能够保证找到最优解即A*算法具有最优性。下面首先以八数码为例介绍A算法的运行过程，然后介绍对A*算法最优性的分析。6.2.3最佳图搜索算法A*在A算法运行的初始时刻，OPEN表中只有初始结点，因此我们扩展它，得到右图中的第二层结点，将这些结点全部放入OPEN表。6.2.3最佳图搜索算法A*在第二次迭代过程中，A算法选择OPEN表中具有最小f值为1+3=4的结点扩展，得到第三层的3个结点，并将它们放入OPEN表。在第三次迭代中，A算法选择OPEN表中f值为2+3=5的结点进行扩展。在第四次迭代中，A算法选择OPEN表中f值为2+3=5的另一个结点进行扩展。在第五次迭代中，A算法选择OPEN表中f值为3+2=5的结点进行扩展。在第六次迭代中，A算法选择OPEN表中f值为4+1-5的结点进行扩展。在第七次迭代中，A算法选择OPEN表中f值为5＋0=5的结点进行扩展。通过此例可以发现，A算法相对于宽度优先搜索和深度优先搜索都具有优势。6.2.3最佳图搜索算法A*但是，由于对启发函数h没有任何限制，A算法不能保证找到最优解。经研究发现，A算法在如下3个条件成立时能够保证得到最优解：（1）启发函数h对任一结点n都满足h（n）不大于n到目标的最优代价。（2）搜索空间中的每个结点具有有限个后继。（3）搜索空间中每个有向边的代价均为正值。为了表明此类A算法的重要性，将此类A算法称为A*算法，称上述3个条件为A算法的运行条件。6.2.3最佳图搜索算法A*对h的限制可以更为正式地表述如下：令h*是能计算出任意结点到目标的最优代价的函数，称之为“完美启发函数”。如果

n：h（n）≤h*（n），则称h为可采纳的启发函数（admissibleheuristicfunction），或者称h是可采纳的，或者简称为可纳的。此外，也引入函数g*，它能计算从开始结点到任意结点的最优代价。定义估价函数：f*（n）=g*（n）+h*（n）。这样f*（n）就是从起始结点出发经过结点到达目标结点的最佳路径的总代价。把评价函数f（n）和f*（n）相比较，g（n）是对g*（n）的估价。h（n）是对h*（n）的估价。在这两个估价中，尽管g（n）容易计算，但它不一定就是从起始结点S。到结点n的真正的最短路径的代价，很可能从初始结点S到结点n的真正最短路径还没有找到，所以一般都有g（n）>g*（n）。但应注意，A*算法的步骤（3）和（4）保证了如果发现n的更好的g（n）值，则以此值作为n的最新的g（n），并相应地修改n的父指针，步骤（4）还在n已被扩展的情况下将n移回OPEN表，使得会被再次扩展。6.2.3最佳图搜索算法A*现在给出一些关于算法性质的定义，为了叙述方便，将一个算法记作M。完备性：如果存在解，则M一定能找到该解并停止，则称M是完备的。可纳性：如果存在解，则M一定能够找到最优的解，则称M是可纳的。优越性（DoMINance）：一个算法M1称为优越于另一个算法M2，指的是如果一个结点由M1扩展，则它也会被M2扩展，即M1扩展的结点集是M2扩展的结点集的子集。最优性：在一组算法中一个算法M称为最优的，如果M比其他算法都优越。A*算法的完备性和可纳性。为了证明该定理，我们首先介绍引理6.16.2.3最佳图搜索算法A*引理6.1在A*算法停止之前的每次结点扩展前，在OPEN表上总是存在具有如下性质的结点n*：（a）n*位于一条解路径上。（b）A*算法已得出从初始结点S0到n*的最优路径。（c）f（n*）≤f*（S0）。证明：为证明此引理在A*算法的每次结点扩展前都成立，只需证明：（1）本引理在A*算法初始执行时成立；（2）若本引理在一个结点被扩展之前成立，则在该结点被扩展之后本引理同样成立。按照此思路，将采用归纳法进行证明。6.2.3最佳图搜索算法A*归纳基础：在A*算法在第1次结点扩展前（即，S0被选择进行扩展之前），S0在OPEN表中，S0位于一条最优解路径上（因为所有的解路径都以为S0起点），并且A*已得知从S0到S0的最优路径。此外，根据f的定义，因此，在第1次结点扩展前，S0就是满足引理结论的n*。归纳步骤：假设引理在第m次（m≥0）结点扩展后成立，证明本引理在第m+1次结点扩展后仍成立。假定A*算法在扩展m个结点后，OPEN表中存在一个结点n*，A*算法已知从S0到n*的最优路径。那么，若n*在第m+1次扩展中未被选择，则它在第m+1次扩展后是满足引理要求的结点n*，在此情况下引理得证。6.2.3最佳图搜索算法A*另一方面，若n*在第m+1次扩展时被选择，则n*的每一个未在OPEN表和CLOSED表中出现的子结点都将被放入OPEN表，而且，这些新的子结点中必然存在一个结点（记为np）位于最优解路径上（因为经过n*的最优解路径必然在经过n*后再经过n*的某个子结点，所以np必然存在）。np也满足性质（b），即A*已得出从S0到np的最优路径，该路径记为P1：由到达n*的最优路径再连接上n*到np的有向边而组成。如果从S0到达np的最优路径不同于P1，则P1不构成最优解路径，从而与n*在最优解路径上的假设相矛盾。因此，np满足性质（a）和（b）。下面还需证明性质（c）在所有归纳步骤中成立，即证明性质（c）在A*停止前的0~m次扩展时都成立。6.2.3最佳图搜索算法A*对于任一结点n*（n*在最优解路径上；且A*算法已得出从S0到n*的最优路径，即g（n*）=g*（n*）），它满足如下不等式：因此，性质（c）成立。至此，引理得证。6.2.3最佳图搜索算法A*定理6.1若A*算法的运行条件成立，并且搜索空间中存在从初始结点S0到目标结点的代价有穷的路径，则A*算法保证停止并得出S0到目标结点的最优代价路径。证明：在引理6.1的基础上，证明本定理。首先证明如果搜索空间存在目标结点，则A*必然停止，然后证明A*在停止时已找到最优解路径。首先证明A*必然停止：假设它不停止，则它将不断扩展OPEN表中的结点。我们已假定搜索空间的分枝因子（每个结点的平均子结点数目）为一个有穷值，且每条有向边的权值为正数。所以，随着OPEN表上的结点在搜索树中的深度增加，它们的g值将无限增长。这种增长必然导致A*在未来的一次结点扩展时OPEN表中所有结点的g值都大于f（S0），此情况与引理6.1矛盾。因此A*算法必然停止。6.2.3最佳图搜索算法A*其次证明A*算法停止时已找到一条最优的解路径。A*只有在OPEN表为空或者当前扩展的结点为目标结点时才停止。前一个停止条件在不存在目标结点的搜索空间上发生。而本定理要求搜索空间存在目标结点。因此A*必然在扩展一个目标结点时停止。那么，现在只需说明该目标结点是否是最优的。假设A*算法在停止时扩展的目标结点不是最优的，并记此结点为ng2，而最优目标结点为ng1。易知，在此情况下，f*（ng2）>f*（S0），f*（ng1）=f*（S0）。此假设与引理6.1矛盾。因为引理6.1说明：在A*选择ng2之前，OPEN表上必然存在一个结点n*满足f*（n*）≤f*（S0）。由于f*（n*）≤f*（S0），所以A*在考察ng2和n*时必然选择n*而不是ng2，这与假设选择了ng2相矛盾。至此，定理6.1得证。6.3与或图的启发式搜索启发式搜索可以应用的第二个问题是AND-OR图（与或图）的反向推理问题。AND-OR图的反向推理过程可以表示一个问题归约过程。问题规约的基本思想是：在问题求解过程中，将一个大的问题变换成若干个子问题，再将这些子问题分解成更小的子问题，这样继续分解，直到所有的子问题都能被直接求解为止。问题规划方法之所以可行，是因为根据全部子问题的解就能构造出原问题的解。一般地，待求解的问题称为初始问题，能直接求解的问题称为本原问题。问题归约是不同于状态空间法的另一种问题描述和求解的方法。6.3.1

问题归约表示以一个自动推理的例子介绍基于问题归约思想求解问题的过程。例6.1给定如下一组命题公式，给出证明命题r成立的证明序列。解：该问题的解是这样一个证明序列：p，t，p⋀t→q，p→m，s→q，q→r。那么，如何得到这个解?可以采用正向的思考，也可以采用反向的思考。正向思考过程通常如下：根据p和p→m可以得出m成立，根据p，t和p⋀t→q得出q成立，根据q成立和q→r得出r成立。基于此过程，构造出证明序列。反向思考过程通常如下：若要证明r成立，就必须利用能推导出r的蕴涵式q→r；进而要证明q成立，可以利用蕴涵式s→q或者p⋀t→q；如果利用蕴涵式s→q，则要证明s成立，但给出的公式集合中不含s，而且也不含后件为s的蕴涵式，所以此条路径不通；如果利用p⋀t→q证明q成立，则要求p和t都成立，由于p和t都在给定的公式集中存在，所以无须继续证明。至此，能够构造出证明序列。6.3.1

问题归约表示在此例中，反向思考的过程就是问题归约的思想。例如，将“证明r成立”的问题通过蕴涵式q→r转化为“证明q成立”的问题；将“证明q成立”的问题通过p⋀t→q转化为“证明p成立”与“证明t成立”两个问题；“证明p成立”的问题由于p在命题集合中存在而能被立即解决；同理，“证明t成立”的问题也能被立即解决。正向思考和反向思考在效率上存在差别，但取决于具体的问题，没有绝对的优劣之分。例如，对于给定{p，p→q，p→r，p→s}，要证明s成立，则应用反向思考的效率高；对于给定{p，t→s，r→s，p→s}，要证明s成立，则应用正向思考的效率高。6.3.1

问题归约表示基于问题归约思想求解问题的基本概念和方法。从问题归约的角度，一个问题表示为三元组：（S0，O，P），其中：S0是初始问题，即要求解的问题：P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题；O是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。这样，基于问题归约的求解方法就是由初始问题出发，运用操作算子生成一些子问题，对子问题再运用操作算子生成子问题的子问题，如此进行到产生的问题均为本原问题为止，则初始问题得解。6.3.2与或图及解图将例6.1的问题被表示为右图，其中，方块结点表示问题，结点之间的有向边表示源结点对应的问题可分解为目标结点对应的问题。在该图中，最特殊的结点是q，另一个最特殊的是从q指向p和的有向边。q指向p和的两条有向边被一个圆弧连接，用于表示q被分解（归约）为q与t：只有当p和t对应的问题都被解决时，q才能被解决。将右图抽象为一种称为超图的结构，用二元组（N，H）表示：N为结点的有穷集合；H为超边的集合；一个超边表示为<s，D>，其中s∈N，称s为该超边的源结点，D⊆N，称D为该超边的目的结点集。超边也称为“k连接符”，其中k=|D|。问题归约的图形化表示（N1，H1），N1={r，q，p，t，m}，H={<r，{q}>，<q，{p，t}>，<q，{m}>}超图表示6.3.2与或图及解图从问题归约的角度看，一个问题可以用超图表示其中所有的问题以及问题的分解方法。此外，为了表示本原问题集合、初始问题，需要再增加两个元组。我们称此类图为与或图（AND-OR图），它的四元组表示为（N，n0，H，T），其中：N是结点集合，其中每个结点对应一个唯一的问题。n∈N，对应于初始问题。H是超边的集合，其中每个超边<s，D>表示结点s对应的问题的一个可行的分解方法；若|D|=1，则该超边称为“或弧”，同时称D中结点为s的“或子结点”（OR-node），也称它为s的“或后继”（OR-descendents）；若|D|>1，则该超边称为“与弧”，同时称D中结点为s的“与子结点”（AND-node），也称它们为s的“与后继”（AND-descendents）。T是N的子集，其中每个结点对应的问题都为本原问题，T中的结点也称为叶结点6.3.2与或图及解图与或图（N，n0，H，T）的每个以n0为根结点的子图可以表示一种对原始问题逐步分解的过程。下图（a）和图（b）分别是问题归约表示图中的两个不同的子图，其中图（a）所表示的分解过程能够解决原始问题，称这样的图为与或图的解图，而图（b）所表示的分解过程不能解决原始问题。如果能设计一种算法，它能从一个与或图中找出性质如图（a）的解图，则该算法就找到了解决原始问题的一个分解过程。与或图的子图6.3.2与或图及解图可解结点（SolvedNodes）和不可解结点（UnsolvableNodes）的概念假定AND-OR图的子图中每个结点至多有一个k连接符，其中的一个可解结点递归地定义如下：（1）叶结点是可解结点。（2）一个结点是可解的，当且仅当以它为源结点的某一条k连接符可解。（3）一个k连接符可解，当且仅当该连接符的每个目的结点都可解。将不是叶结点的结点简称为非叶结点，并递归定义不可解结点如下：（1）无后继的非叶结点是不可解的。（2）一个结点是不可解的，当且仅当以它为源结点的所有k连接符都不可解。（3）一个k连接符是不可解的，当且仅当该连接符存在一个不可解的目的结点。能导致初始结点可解的那些可解结点及相关的超边组成的子图称为该AND-OR图的解图。6.3.2与或图及解图一个归约问题的AND-OR图可能有多个解图，那么，其中哪个解图更优?为了评价解图的优劣，根据归约问题为每个本原问题赋予相应的权重，为每个操作算子赋予相应的权重，由这些权重来表示相应的费用。父结点的费用定义为相应的操作算子的费用与子节点费用之和。一个解图的费用定义为该图中初始结点的费用。计算一个归约问题的最优解的问题对应于计算该问题的AND-OR图的一个费用最小的解图的问题。称具有最小费用的解图为最优解图。假设任一结点n到目标集Sg的费用估计为h（n）。结点n的费用按下面的方法计算（1）如果n∈Sg，则h（n）=0，否则h（n）为以n为源结点的k连接符的费用的最小值。（2）一个k连接符<n，{n1，n2，…，nm}>的费用为h（n）=m+h（n1）+h（n2）+h（nm）。6.3.3AO*算法为了在AND-OR图中找到最优解图，需要一个类似于A*的算法，Nilsson因而提出了AO*算法，它和A*算法是不同的，主要有以下两个区别。区别1：AO*算法能考虑“与弧”的费用，而A*算法不能。与或图6.3.3AO*算法为了保证搜索到一个最优解图，在搜索AND-OR图时，每步需做3件事：（1）遍历图，从初始结点开始，沿当前最优路径，记录在此路径上未扩展的结点集。（2）从这些未扩展的结点中选择一个进行扩展。将其后继结点加入图中，计算每后继结点的f值（只需计算h，不计算g）。（3）改变最新扩展结点的f估值，以反映由其后继结点提供的新信息。将这种改变往上回传至整个图。在往后回传时，每到一个结点就判断其后继路径中哪一条最有希望并将它标记为目前最优路径的一部分。这样可能引起目前最短路径的变动。这种图的往上回传以修正费用估计的工作在A*算法中是不必要的，因为A*只需考察未扩展结点。但现在必须考察已扩展结点以便挑选目前的最优路径。6.3.3AO*算法第一步：A是唯一结点，因此它在目前最优路径的末端。第二步：扩展A后得结点B、C和D，因为B和C的费用为9，得出A的费用为6，所以把到D的路径标记为出自A的最有希望的路径（被标记的路径在图中用箭头指出）第三步：沿着最优希望的路径扩展D，得到E和F的与弧，得出D的费用估计为10，故将D的f值修改为10。往上退一层发现，A到与结点集{B，C}的耗费为9，所以，从A到{B，C}是当前最有希望的路径，因此，对<A，{B，C}>进行标记。6.3.3AO*算法第四步：扩展结点B，得结点G、H，且它们的费用分别为5、7。往上传其f值后，B的f值改为6（因为G的弧最佳）。往上一层继续回传，A到结点集{B，C}的费用更新为12，即（6+4+2）。因此，D的路径再次成为更好的路径，所以取消<A，{B，C}>的标记，再次标记<A，{D}>。A的费用为：f（A）=MIN{12，4+4+2+1）=116.3.3AO*算法区别2：如果有些路径通往的结点是其他路径上的“与”结点扩展出来的结点，那么不能像“或”结点那样只考虑从结点到结点的个别路径，有时候路径长一些可能会更好。下图中结点已按生成它们的顺序给了序号。现假定下一步要扩展结点10，其后继结点之一为结点5，扩展后的结果如图（b）所示。到结点5的新路径比通过3到5的先前路径长。但因为若要经由结点3而通向结点5，还必须解决结点4，而结点4是不可解结点，所以经由结点10而通向结点5的路径更好。长路径和短路径6.3.3AO*算法AO*算法的主要思想：在A*算法中用了两张表：OPEN表和CLOSED表。AO*算法只用一个结构G，它表达了至今已明显生成的部分搜索图。图中每一结点向下指向其直接后继结点，向上指向其直接前趋结点。同图中每一结点有关的还有h值它估计了从该结点至一组可解结点那条路径的费用。AO*算法还使用一个称为FUTILITY的值。若一解的估计费用大于FUTILITY的解，则放弃搜索该路径FUTILITY相当于一个阈值，它的选择应使得大于费用FUTILITY的任一解即使存在也因为代价大而无法使用。6.3.3AO*算法ProcedureAO*Begin设G仅由代表初始问题的结点n0构成，计算h（n0）。Repeat（1）沿着从n开始的带标记的k连接符，如果存在，挑选在此路径上但未扩展的一个结点进行扩展，记该结点为n。（2）生成n的后继结点。If

n没有后继结点，Then令h（n）=FUTILITY，标记n为不可解结点；ElseBegin记n的后继结点集为Suc。For每个不是结点n祖先的后继结点s∈Suc，DoBegin①把s加到图G中。②若s是一个叶结点，则标记s为SOLVED，并令h（s）=0。③若s是非叶结点，则计算它的h值。EndEndAO*算法流程：6.3.3AO*算法（3）将最新发现的信息向上回传。具体做法为：设C为一结点集，C包括已经做了SLOVED标记或者h值已经发生了改变的结点。将初始化为{n}。（4）Repeat①从C中挑选一个结点，该结点在G中的子孙均不在C中出现（即，保证对于每一正在处理的结点，是在处理其任一祖先之前来处理该结点）称此结点为c并令C=C-{c}。②计算以c为源结点的每条k连接符的费用，其费用等于其目的结点的h值之和加上该连接符自身的费用。从刚刚计算过的始于c的所有k连接符的费用中选出极小费用作为c的新h值。③把在②中计算出来的带极小费用的k连接符标记为始于c的最佳路径④If

c的带标记的连接符是SOLVED，Then

把c标记为SOLVED。⑤If

c已标记为SOLVED，或c的费用刚才已经改变，Then应把其新状态往回传。因此，把c的所有祖先结点加到C中。Unti1

C为空；Unti1n0标为SOLVED（求解成功），或n0的h值大于FUTILITY（无解）。EndAO*算法流程（接上表）：6.3.3AO*算法下图为AO*算法示例：开始时，在算法的步骤（3）处可知：C={A}，在步骤（4）的①步可知：c=A。由于有A到{B，C}的k连接符，根据该连接符知c的费用为：2+h（B）+h（C）=9；另外有A到{D}的k连接符，根据该连接符知c的费用为：1+h（D）=6，所以A的较好费用为6，将<A，{D}>作上标记。这样，在下一次循环的步骤（1）处，可得n=D，扩展D后得：Suc={E，F}，执行之后的步骤得到D的新费用为10，向上回传，由于连接符<A，{D}>的新费用大于连接符<A，{B，C}>的费用，所以A的费用更新为连接符<A，{B，C}>的费用（即9），此外，撤销对<A，{D}>的标记，同时对<A，{B，C}>做标记。6.4博弈树的搜索博弈一向被认为是富有挑战性的智力活动，如下棋、打牌、作战和游戏等。二人博弈、二人零和、全信息、非偶然博弈，博弈双方的利益是完全对立的（1）对垒的双方MAX和MIN轮流采取行动，博的结果只能有3种情况：MAX胜、MIN败；MAX败，MIN胜；和局。如果记“胜利”为+1分，“失败”为-1分，“平局”为0分，则双方在博弈结束时的总分总是为“零”，称此类博弈为“零和”。（2）“全信息”是指对垒过程中，任何一方都了解当前的格局和过去的历史。（3）“非偶然”是指任何一方都根据当前的实际情况采取行动，选择对自己最有利而对对方最不利的对策，不存在“碰运气”如掷骰子）的偶然因素。具有以上特点的博弈游戏有一字棋、象棋和围棋等。围棋的博弈树6.4.1博弈树假设有7枚钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个选手遇到不能再分的情况，则为输（取胜的策略用双线箭头表示）。分钱币的博弈无论MIN开始时怎么走法，MAX总可以获胜6.4.1博弈树如果站在某一方（如MAX方，即MAX要取胜），把上述博弈过程用图表示出来，则得到的是一棵“与”关系和“或”关系组成的树。当这颗树描述的是博弈过程的时候，我们称其称为博弈树，它有如下特点：（1）博弈的初始格局是初始结点。（2）在博弈树中，“或”结点和“与”结点是逐层交替出现的。自己一方扩展的结点之间是“或”关系，对方扩展的结点之间是“与”关系。双方轮流地扩展结点。（3）所有自己一方获胜的终局都是本原问题，相应的结点是可解结点；所有使对方获胜的终局都认为是不可解结点。6.4.2极小-极大搜索过程在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树，如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的最常使用的分析方法是极大极小分析法。其基本思想或算法如下：（1）设博弈的双方中一方为MAX，另一方为MIN。设计算法为其中的一方（例如MAX）寻找一个最优行动方案。（2）为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。（3）为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端结点的得分。此时估算出来的得分称为静态估值。6.4.2极小-极大搜索过程在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树，如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的最常使用的分析方法是极大极小分析法。其基本思想或算法如下：（4）当末端结点的估值计算出来后，再推算出父结点的得分，推算的方法是：对“或结点，选其子结点中一个最大的得分作为父结点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”结点，选其子结点中一个最小的得分作为父结点的得分，这是为了立足于最坏的情况。这样计算出的父结点的得分称为倒推值。（5）如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。6.4.2极小-极大搜索过程//MinMaxSearch.

functionminimax(node,depth)//指定当前节点和搜索深度//如果能得到确定的结果或者深度为零，使用评估函数返回局面得分ifnodeisaterminalnodeordepth=0returntheheuristicvalueofnode//如果轮到对手走棋，是极小节点，选择一个得分最小的走法iftheadversaryistoplayatnodeletα:=+∞foreachchildofn