启发式图搜索.ppt

1.4 启发式图搜索1. 1.启发式搜索启发式搜索• 定义：为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息此种信息叫做启发信息利用启发信息的搜索方法叫做启发式搜索方法•特点：重排OPEN表，选择最有希望的节点加以扩展•种类：最佳优先搜索、A*算法等启发式搜索策略•有关具体问题领域的信息常常可以用来简化搜索一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function) •估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 f(n)——表示节点n的估价函数值 •建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数这些特点被认为与向目标节点前进一步的希望程度有关。

•应用节点“希望”程度（估价函数值）重排OPEN表2.登山法和最佳优先搜索•登山法的引入 瞎子在山上某点，想要爬到山顶，怎么办？从立足处用明杖向前一试，觉得高些，就向前一步，如果前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这样一步一步地走，就走上了山顶 这个向各方向的测试“步”，就是“登山法”的估价函数f(n)登山法算法步骤：①设定初始节点n；②如果n是目标，则成功退出；③扩展n，得到其子节点集合；④从该集合中选取f(n)为最小的节点n’；⑤将n’设为n，返回第②步最佳优先搜索算法•是“登山法”的推广，但它是对OPEN表中所有节点的f(n)进行比较，按从小到大的顺序重排OPEN表•其算法效率类似于纵向搜索算法，但使用了与问题特性相关的估价函数来确定下一步待扩展的节点，因此是一种启发式搜索方法开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f (s)OPEN表为空表？表为空表？把把OPEN表中的第一个节点表中的第一个节点n放入放入CLOSED表表n为目标节点吗？为目标节点吗？扩展扩展n，计算所有子节点的估价函数值，，计算所有子节点的估价函数值，并提供它们返回节点并提供它们返回节点n的指针。

的指针失败失败成功成功最佳优先搜索算法框图最佳优先搜索算法框图是是否否是是否否把子节点送入把子节点送入OPEN表，并对其中的所有表，并对其中的所有节点按估价函数值由小到大重排节点按估价函数值由小到大重排迷宫问题如下，F是入口，B是出口，试采用最佳优先搜索算法进行求解举例：迷宫问题举例：迷宫问题0123x123yFGHECADB22241111解：估价函数f(n)采用每个节点与目标节点在坐标系上的距离来表示例如，E点与目标节点B之间的空间距离是2+2=4，两个2分别是E与B在x轴及y轴上的距离注：每个节点小括号内的数值表示该节点到目标的空间距离，即该点的估价函数值搜索得到的路径如黄线所示F(6)G(5)H(3)E(4)A(2)B(0)12345C(3)6• 举例：八数码魔方（8-puzzle problem）12384567（目标状态）12384567（初始状态）57①①④④⑤⑤⑥⑥③③123845671238456712384567 (3) (5) (5)②②123845671238456712384567 (4) (3) (3)1238456712 384567 (2) (4)1238456712384567 (3) (4)12384567 (1)813245671 2384567 (0)(2)八数码魔方的最八数码魔方的最佳优先搜索树佳优先搜索树123846(4)75⑦⑦搜索得到的路径如黄线所示搜索得到的路径如黄线所示•本题采用了简单的估价函数 f(n)=W(n)其中：W(n)用来计算对应于节点n的数据库中错放的棋子个数。

因此，初始节点棋局的f(n)值等于412384567•第②步有三种情况,我们选择其中f(n)最小的: •其它依次类推.最后用了7步得出了结果. 123845671238456712384567 (3)(5)(5) 3.A算法•最佳优先算法有时无法得到最优解，因为它的估价函数f的选取时，忽略了从初始节点到目前节点的代价值所以，可考虑每个节点n的估价函数f(n)分为两个分量：从起始节点到节点n的代价g(n)以及从节点n到达目标节点代价的估算值h(n) f(n)=g(n)+h(n)•f(n)——节点n的估价函数； g(n)——评价函数，从初始节点S到n节点的实际代价； h(n)——启发函数，从n到目标节点Sg最佳路径的估计 代价•这里h(n)体现了搜索的启发信息，因为g(n)是已知的如果说详细点，g(n)代表了搜索的宽度优先趋势但是当h(n)g(n) 时，可以省略g(n),而提高效率A算法的引入：g(n)的计算方法：•g(n)就是在搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。

h(n)的计算方法：•h(n)依赖于有关问题的领域的启发信息这种信息可能与八数码魔方问题中的函数W(n)所用的那种信息相似把h(n)叫做启发函数• 举例：八数码魔方（8-puzzle problem）12384567（目标状态）12384567（初始状态）57①①④④⑤⑤⑥⑥③③123845671238456712384567(1+3=4)(1+5=6)(1+5=6)②②123845671238456712384567(2+4=6)(2+3=5)(2+3=5)1238456712 384567(3+2=5)(3+4=7)1238456712384567(3+3=6)(3+4=7)12384567(4+1=5)813245671 2384567(5+0=5)(5+2=7)八数码魔方的八数码魔方的A A算法搜索树算法搜索树123846(0+4=4)75⑦⑦搜索得到的路径如黄线所示搜索得到的路径如黄线所示•本题采用的估价函数为： f (n)=g (n)+W (n)其中：W (n)用来计算对应于节点n的数据库中错放的棋子个数；g (n)为从起点到n的代价值因此，第二层的棋局的f (n)= 1 + 5 = 6。

12384567g (n)h (n)4.最佳图搜索算法A*（A*算法）•在A算法中，如果满足条件：h(n)≤h*(n)则A算法称为A*算法对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始通过节点n的一条最佳路径的代价估价函数f 定义为：f(n)=g(n)+h(n) —— g是g*的估计 ，h是h*的估计定义定义1 在图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法定义定义2 在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计定义定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法 A*条件举例•8数码问题–h1(n) = “不在位”的将牌数–h2(n) = 将牌“不在位”的距离和2 8 31 6 47 51 2 3457 6 8将牌1：1将牌2：1将牌6：1将牌8：257①①④④⑤⑤⑥⑥③③123845671238456712384567(1+4=5)(1+6=7)(1+6=7)②②123845671238456712384567(2+5=7)(2+5=7)(2+3=5)1238456712 384567(3+2=5)(3+4=7)12384567(4+1=5)813245671 2384567(5+0=5)(5+2=7)123846(0+5=5)7⑦⑦八数码魔方的八数码魔方的A A* *算法搜索树算法搜索树。