1、高级搜索算法之A*A算法 n在BFS搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表(队列）中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法又称为启发式搜索算法。n对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。1.全局择优搜索全局择优搜索n在全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下：n（1）把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；n（2）如果Open
2、表为空，则问题无解，失败退出；n（3）把Open表的第一个节点取出放入Closed表，并记该节点为n；n（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；n（5）若节点n不可扩展，则转到第(2)步；n（6）扩展节点n，生成子节点ni(i=1,2,)，计算每一个子节点的估价值f(ni)(i=1,2,)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；n（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；n（8）转第(2)步。n由于上述算法的第(7)步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第(
3、3)步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。n对上述算法进一步分析还可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例(g(n)是从起点到n的代价，d(n)是从起点到n经过的步数（n在BFS搜索树中的层次数)。一个A算法的例子-八数码再解定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的步数h(n)为当前节点“不在位”的方块数2 8 31 6 47 51 2
4、38 47 6 5h计算举例h(n)=4 2 8 31 6 47 51 2 3457 6 82 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标Sg12345
5、62局部择优搜索局部择优搜索n在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：n(1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；n(2)如果Open表为空，则问题无解，失败退出；n(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；n(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；n(5)若节点n不可扩展，则转到第(2)步；n(6)扩展节点n，生成子节点ni(i=1,2,)，计算每一个子节点的估价值f(ni)(i=1,2,)，并按估价值从小到大的顺序依次放入Op
6、en表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。n由于这一算法的第六步仅仅是把刚生成的子节点按其估价函数值从小到大放入Open表中，这样在算法第(3)步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。n对这一算法进一步分析也可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的深度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。A*算法算法n上一节讨论的启发式搜索算法，都没有对估价函数f(n)做任何限制。实际上，估价函数对搜索过程是十
7、分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。n假设f*(n)为从初始节点S0出发，经过节点n到达目标节点的最小代价值(真实值）。估价函数f(n)则是f*(n)的估计值。显然，f*(n)应由以下两部分所组成：一部分是从初始节点S0到节点n的最小代价，记为g*(n)；另一部分是从节点n到目标节点的最小代价，记为h*(n)，当问题有多个目标节点时，应选取其中代价最小的一个。因此有nf*(n)=g*(n)+h*(n)n把估价函数f(n)与 f*(n)相比，g(n)是对g*(n
8、)的一个估计，h(n)是对h*(n)的一个估计。在这两个估计中，尽管g(n)的值容易计算，但它不一定就是从初始节点S0到节点n的真正最小代价，很有可能从初始节点S0到节点n的真正最小代价还没有找到，故有)()(g*ngn n有了g*(n)和h*(n)的定义，如果我们对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制：ng(n)是对g*(n)的估计，且g(n)0；nh(n)是对h*(n)的下界，即对任意节点n均有n则称得到的算法为A*算法。)()(h*nhn A*算法伪代码：open=Startclosed=while open不为空 从open中取出估价最小的结点n i
9、f n=Target then return 从Start到n的路径/找到了！else for n的每个子结点x if x in open 计算新的f(x)比较open表中的旧f(x)和新f(x)if 新f(x)旧f(x)使用新f(x)来更新open表 else if x in closed 计算新的f(x)比较closed表中的旧f(x)和新f(x)if 新f(x)h1(n)n则在搜索过程中，被A2*扩展(遍历其子节点)的节点也必然被A1*扩展，即A1*扩展的节点不会比A2*扩展的节点少，亦即A2*扩展的节点集是A1*扩展的节点集的子集。n证明：（用数学归纳法）n(1)对深度d(n)=0的节
10、点，即n为初始节点S0，如果n为目标节点，则A1*和A2*都不扩展n；如果n不是目标节点，则A1*和A2*都要扩展n。n(2)假设对A2*搜索树中d(n)=k的任意节点n，结论成立，即A1*也扩展了这些节点。n(3)证明A2*搜索树中d(n)=k+1的任意节点n，如果被A2*扩展，则也要由A1*扩展（用反证法）。n假设A2*搜索树上有一个满足d(n)=k+1的节点n,A2*扩展了该节点，但A1*没有扩展它。根据第(2)条的假设，知道A1*扩展了节点n的父节点。因此，n必定在A1*的Open表中。既然节点n没有被A1*扩展，则根据推论1,有n f1(n)f*(S0)n即 g(n)+h1(n)f*
11、(S0)nh1(n)f*(S0)-g(n)n另一方面，由于A2*扩展了n，因此有n f2(n)f*(S0)n即 g(n)+h2(n)f*(S0)n亦即 h2(n)f*(S0)-g(n)n所以有 h1(n)h2(n)n这与我们最初假设的h1(n)0 n4）h(n)=h*(n)。n5)h函数是相容的，以确保f是递增的。n当此五个条件都满足时，一个具有f(n)=g(n)+h(n)策略的最好优先启发式算法(A算法)能成为A*算法，并一定能找到最优解。nh 相容的定义以及意义如果h函数对任意状态s1和s2还满足：h(s1)g(s1)+h(s1)f(s1)=f(s2)即f是递增的。A*算法应用举例算法应用
12、举例n例例 2 A*算法解决八数码难题n在例1中，我们取h（n）=W（n）（W(n)是不在位的方块数目)。尽管我们对h*（n）不能确切知道，但采用单位代价时，通过对“不在位”数码个数的估计，可以得出至少要移动W（n）.因为，例1所定义的和h（n）满足A*算法的限制条件。n这里再取另一种启发函数h(n)=P（n），P（n）定义为每个数码与目标位置之间距离（不考虑夹在其间的数码）的总和，同样要判定至少要移动P（n）步才能达到目标，因此有 ，即满足A*算法的限制条件。其搜索过程所得到的搜索树如图2所示。在该图中，节点旁边虽然没有标出P（n）的值p,但却标出了估计函数f（n）的f值。对解路径，还给出了
13、各个结点的g*（n）和h*（n）的g*值和h*值。从这些值还可以看出，最佳路径上的节点都有 f*=g*+h*=4.)()(*nhnP图2nA*算法解决八数码难题估计函数选取的另一例子：（ACM/ICPC Regional Contest Kanpur 2001)：有一些打乱的段落，比如：p2,p3,p4,p7,p1,p5,p6每次只能拷贝若干个连续的段落，然后剪切到某个段落前面，最后要形成p1,p2,p3,p4,p5,p6,p7问最少要拷贝粘贴多少次。A*算法算法h(s)选为在状态s下，未“就位”的段落数目？h(s)选为在状态s下，未“就位”的段落到其该呆的位置的距离之和？A*算法算法h(s)
14、选为在状态s下，未“就位”的段落数目？h(s)选为在状态s下，未“就位”的段落到其该呆的位置的距离之和？都不行，h会减少太快，即从某个状态s到s，可能导致 g的值加1，然而h的值减少很多，这样f(s）s，h的值最多减少3.但是g的值只增加1，h还是不相容，怎么办？A*算法算法将连续段落集合 S 从p1后面剪切粘贴到p2后面，后继正确性受到影响的段落最多3个：p1,p2和S中最后的一个段落，因此从s-s，h的值最多减少3.但是g的值只增加1，h还是不相容，怎么办？A*算法算法f(s)=3*g(s)+h(s)迭代加深搜索n算法思路n总体上按照深度优先算法方法进行n对搜索深度需要给出一个深度限制dm
15、，当深度达到了dm的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支继续进行搜索。ndm从1开始，从小到大依次增大（因此称为迭代加深）n迭代加深搜索是最优的，也是完备的n重复搜索深度较小的节点，是否浪费？IDA*:迭代加深的A*算法nIDA*的基本思路是：首先将初始状态结点的估价函数H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求(相容，递增）下，可以证明找到的这个解一定是最优解。在程序实现上，IDA*要比 A*方便，因为不需要保存结点，不需要判重复，也不需要根据 H值对结点排序，占用空间小。在一般的问题中是这样使用IDA*算法的，当前局面的估价函数值+当前的搜索深度 预定义的最大搜索深度时，就停止继续往下搜索。适用题目：poj2286 the rotation gameIDA*:迭代加深的A*算法IDA*与A*nIDA*与A*算法相比，主要的优点是对于内存的需求nA*算法需要指数级数量的存储空间，因为没有深度方面的限制n而IDA*算法只有当节点n的所有子节点n的f(n)小于限制值c时才扩展它，这样就可以节省大量的内存。n另外，IDA*不需要对扩展出的节点按启发值排序。
