1.启发式搜索算法A
启发式搜索算法A,一般简称为A算法,是一种典型的启发式搜索算法。其基本思想是:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。
评价函数的形式如下:
f(n)=g(n)+h(n)
其中n是被评价的节点。
f(n)、g(n)和h(n)各自表述什么含义呢?我们先来定义下面几个函数的含义,它们与f(n)、g(n)和h(n)的差别是都带有一个“*”号。
g*(n):表示从初始节点s到节点n的最短路径的耗散值;
h*(n):表示从节点n到目标节点g的最短路径的耗散值;
f*(n)=g*(n)+h*(n):表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。
而f(n)、g(n)和h(n)则分别表示是对f*(n)、g*(n)和h*(n)三个函数值的的估计值。是一种预测。A算法就是利用这种预测,来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序,f值小的节点放在前面,而f值大的节点则被放在OPEN表的后面,这样每次扩展节点时,总是选择当前f值最小的节点来优先扩展。
过程A
①OPEN:=(s),f(s):=g(s)+h(s);
②LOOP: IF OPEN=( ) THEN EXIT(FAIL);
③n:=FIRST(OPEN);
④IF GOAL(n)THEN EXIT(SUCCESS);
⑤REMOVE(n,OPEN),ADD(n,CLOSED);
⑥EXPAND(n)→{mi},计算f(n,mi)=g(n,mi)+h(mi);g(n,mi)是从s通过n到mi的耗散值,f(n,mi)是从s通过n、mi到目标节点耗散值的估计。
·ADD(mj,OPEN),标记mi到n的指针。
·IF f(n,mk)<f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针;比较f(n,mk)和f(mk),f(mk)是扩展n之前计算的耗散值。
·IF f(n,m1)<f(m1)THEN f(m1):=f(n,m1),标记m1到n的指针,ADD(m1,OPEN);当f(n,m1)<f(m1)时,把m1重放回OPEN中,不必考虑修改到其子节点的指针。
⑦OPEN中的节点按f值从小到大排序;
⑧GO LOOP;
A算法同样由一般的图搜索算法改变而成。在算法的第7步,按照f值从小到大对OPEN表中的节点进行排序,体现了A算法的含义。
算法要计算f(n)、g(n)和h(n)的值,g(n)根据已经搜索的结果,按照从初始节点s到节点n的路径,计算这条路径的耗散值就可以了。而h(n)则依赖于启发信息,是与问题有关的,需要根据具体的问题来定义。通常称h(n)为启发函数,是对未来扩展的方向作出估计。
算法A是按f(n)递增的顺序来排列OPEN表的节点,因而优先扩展f(n)值小的节点,体现了好的优先搜索思想,所以算法A是一个好的优先的搜索策略。图1.6表示出当前要扩展节点n之前的搜索图,扩展n后新生成的子节点m1(∈{mj})、m2(∈{mk})、m3(∈{m1})要分别计算其评价函数值:
f(m1)=g(m1)+h(m1)
f(n,m2)=g(n,m2)+h(m2)
f(n,m3)=g(n,m3)+h(m3)
然后按第6步条件进行指针设置和第7步重排OPEN表节点顺序,以便确定下一次要扩展的节点。
下面再以八数码问题为例说明A算法的搜索过程。
设评价函数f(n)形式如下:
f(n)=d(n)+W(n)
其中d(n)代表节点的深度,取g(n)=d(n)表示讨论单位耗散的情况;取h(n)=W(n)表示以“不在位”的将牌个数作为启发函数的度量,这时f(n)可估计出通向目标节点的希望程度。
“不在位的将牌数”计算方法如下:
我们来看下面的两个图。
其中左边的图是8数码问题的一个初始状态,右边的图是8数码问题的目标状态。我们拿初始状态和目标状态相比较,看初始状态的哪些将牌不在目标状态的位置上,这些将牌的数目之和,就是“不在位的将牌数”。比较上面两个图,发现1、2、6和8四个将牌不在目标状态的位置上,所以初始状态的“不在位的将牌数”就是4,也就是初始状态的h值。其他状态的h值,也按照此方法计算。
图1.7表示使用这种评价函数时的搜索树,图中括弧中的数字表示该节点的评价函数值f。算法每一循环结束时,其OPEN表和CLOSED表的排列如下:
OPEN表 |
CLODED表 |
初始化 (s(4)) 第一循环结束 (B(4) A(6) C(6)) 第二循环结束 (D(5) E(5) A(6) C(6) F(6)) 第三循环结束 (E(5) A(6) C(6) F(6) G(6) H(7)) 第四循环结束 (I(5) A(6) C(6) F(6) G(6) H(7) J(7)) 第五循环结束 (K(5) A(6) C(6) F(6) G(6) H(7) J(7)) 第六循环结束 (L(5) A(6) C(6) F(6) G(6) H(7) J(7) M(7)) 第七循环结束 第四步成功退出 |
( ) (s(4)) (s(4) B(4)) (s(4) B(4) D(5)) (s(4) B(4) D(5) E(5)) (s(4) B(4) D(5) E(5) I(5)) (s(4) B(4) D(5) E(5) I(5) K(5)) |
根据目标节点L返回到s的指针,可得解路径S(4),B(5),E(5),I(5),K(5),L(5)
2. 最佳图搜索算法A﹡(Optimal Search)
当在算法A的评价函数中,使用的启发函数h(n)是处在h*(n)的下界范围,即满足h(n) ≤h*(n)时,则我们把这个算法称为算法A*。A*算法实际上是分支界限和动态规划原理及使用下界范围的h相结合的算法。当问题有解时,A*一定能找到一条到达目标节点的最佳路径。例如在极端情况下,若h(n)≡0(肯定满足下界范围条件),因而一定能找到最佳路径。此时若g≡d,则算法等同于宽度优先算法。前面已提到过,宽度优先算法能保证找到一条到达目标节点最小长度的路径,因而这个特例从直观上就验证了A*的一般结论。
一般地说对任意一个图&#