关于A*启发式搜索最优性的证明(图解)

关于A*启发式搜索最优性的证明(图解)

前言

在一开始学习A*搜索时，难以理解为什么当$h(n)$是可采纳时即($h(n)\le h^{\ast }(n)$),$A^{\ast }$ 便是最优的，因为评价函数$h(n)$可能并不是线性的，比如若点a和点b的g(n)相同，点a到目标的真实代价为30，点b到目标点的真实代价为20，但是如果评价函数中$h(a)=10,h(b)=15$，此时就会导致我们会在a、b之间选择a点而不是b点，因为$f(a)=g(a)+h(a)<g(b)+h(b)=f(b)$的，这样以来似乎我们选择的并不是最优的路线

猜想的实现

通过将上面假想实现，来观察我们是否选择了一条比最优线路差的线路

起点位于s点，终点为d点，

根据上面的假设，我们第一步会选择a点

紧接着我们将比较c点和b点，这里我们不妨使得$h(c)$也很小，比如说为3

，这样以来$f(c)=g(c)+h(c)=23,f(b)=g(b)+h(b)=25$

我们就达到了我们的目的，我们会选择走到c点

但是当我们走到c点之后，虽然$h(d)=0$,但是此时的$g(d)=40>f(b)=25$,所以尽管我们已经搜索到了终点，但是我们仍然会选择去走到b点

而到b点之后，我们会发现从b点到达d点的代价不论怎样都是小于c点的，所以最终我们仍然会选择s->b->d的路线！

可能有人会说这里我们给的$h(a),h(c)$可能还是过大，$h(b)$还不够大

于是我们可以直接采取最极端的方式：令$h(a)=0,h(c)=0,h(b)=h^{\ast }(b)=20$，在这样的极限情况下我们可以发现尽管是这样，我们在走到c点之后，在b点和c点之间仍然会选择b点，因为其实到最后评判的关键不是$h(n)$,而是$g(n)$,其实$h(n)$只是带给我们一个大体搜搜的方向，这也是A*搜索区别于uninformed搜索的不同，最后判断是否走的关键还是在于$g(n)$!!

结论的证明

通过上面的猜想，我们会发现只要$h(n)<=h^{\ast }(n)$,由于没有过高地估计某个点到目标点的花费，这样我们必然能够找到最优的线路；而相反，如果某个点的$h(n)>h^{\ast }(n)$，那么我们就很有可能不会走这个点，比如上图中d和b的选择中，我们就会直接走到d点而不是回到b点了。

下面给出一个形式化的证明：

我们假设出发点位于start，G为最优目标点，G1为非最优目标点，n为最优线路上的点，下面我们来分析是否会行至G1点

$$\begin{gathered} \because G_1是某条线路下的目标点 \\ \therefore h(G_1)=0 \\ 同理h(G)=0 \\ 又\because G_1非最优目标点，G为最优目标点 \\ \therefore g(G_1)>g(G),f(G_1)>f(G) \\ 对于n点来说，h(n)\le h^{\ast }(n) \\ \therefore h(n)+g(n)\le h^{\ast }(n)+g(n) \\ 而我们知道G为最优目标点,故f(G)=h^{\ast }(n)+g(n) \\ 综上f(n)=h(n)+g(n)\le f(G)<f(G_1) \\ 所以永远也不会通过走某条非最优路来到达目标点！ \end{gathered}$$

总结

到最后，我们会发现A*算法的精彩绝伦，他成功地摒弃掉了DFS BFS等算法的无脑，通过$h(n)$使得我们的搜索有了大体的方向，并且还保证了搜索的最优性，然而对于相当多的问题而言，在搜索空间中处于目标等值线内的结点数量仍然以解路径的长度呈指数级增长，我们仍然需要按情况来选择使用何种算法！