A*算法证明与详解

背景

在 $A^*$ 算法出现之前，人们都在用DFS和BFS进行搜索，然而，这两种算法在展开子节点时都属于盲目型搜索，也就是说，它不会选择在下一次搜索中更优的那个节点，继而借此跳转到该节点进行下一步的搜索，而是盲目全局搜索。如果运气不好，在此情形中，均需要试探完整个解集空间，显然，DFS和BFS只适用于问题规模不大的搜索问题中。然而，1968年的一篇论文“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”，打破了这个僵局，从此，一种精巧、高效的算法------A*算法横空出世了，而且还在好多领域取得了不错的应用。

算法介绍

$A^*$ 算法属于启发式搜索算法，在寻路方面，它可以是在图形平面上，有多条路径，求出最低成本的算法，是非常流行的该类搜索算法中的一个，它一般被用于路径优化领域，例如导航、游戏里面的人物移动等。它的特别之处是在检查最短路径中时，检查每个可能符合需要的节点时都引入了全局的信息，然后对当前节点距终点的距离做出估计，并作为评价该节点处于最短路线上的可能性的量度。

算法搜索过程

核心

两个集合:Open,Closed和一个公式： $f(n)=g(n)+h(n)$ 。其中Open,Closed都是存储节点的集合，Open存储可到达的节点，Closed存储已经到达的节点；而公式 $f(n)=g(n)+h(n)$ 则是对节点价值的评估， $g(n)$ 代表从起点走到当前节点的成本，也就是走了多少步， $h(n)$ 代表从当前节点走到目标节点的距离，即不考虑障碍的情况下，离目标还有多远。至于 $f(n)$ ，则是对 $g(n)$ 和 $h(n)$ 的综合评估，我们应该尽量选择步数更少，离目标更近的节点，那么 $f(n)$ 的值越小越好。

搜索思路

开始时，Closed表为空，Open表仅包括起始节点，每次迭代中， $A^*$ 算法将Open表中具有最小代价之的节点去除进行检查，检查后的节点放入Closed表，如果这个节点不是目标节点，那么考虑该节点的所有相邻节点。对于每个相邻节点按下列规则处理；

如果相邻节点既不在Open表中，又不在Closed表中，则将它加入Open表中；
如果相邻节点已经在Open表中，并且新的路径具有更低的代价值，则更新它的信息；
如果相邻节点已经在Closed表中，那么需要检查新的路径是否具有更低的代价值，如果是，那么将它从Closed表中移出，加入到Open表中，否则忽略。（这里需要检查Closed表是因为要防止由于h(n)计算不准确而导致的误差）

重复上述步骤，直到到达目标节点。如果在到达目标之前，Open表就已经变空，则意味着在起始位置和目标位置之间没有可达的路径。

算法流程图

A*算法证明与详解

算法正确性证明

前置知识

符号说明：

$g(n)$ 表示从点 $st$ 到达节点 $n$ 的当前最小代价。
$g^*(n)$ 表示从节点 $st$ 到节点 $n$ 的实际最小代价。
$h(n)$ 表示从节点 $n$ 到目标节点 $end$ 的预估代价。
$h^*(n)$ 表示从节点 $n$ 到目标节点 $end$ 的实际最小代价。
$f(n)=g(n)+h(n)$ 。这里 $f(n)$ 的含义为从初始节点 $st$ 出发经过节点 $n$ 再到达目标节点 $end$ 的最小代价的预估。
$f^*(n)$ 。实际的最短路径长度。
$OPEN\ LIST$ （开放列表）， $CLOSE\ LIST$ （封闭列表）。

算法本身性质一： 每次选择的节点是 $f(n)=g(n)+h(n)$ 最小的节点。而且， $OPEN \ LIST$ 上任一具有 $f(n)<f^*(st)$ 的节点 $n$ ，最终都将被 $A^*$ 选作扩展节点。(下面定理推论2.1)

算法本身性质二： $h(n)\le h^*(n)$ ，预估代价小于实际最小代价。

开始证明

先证明，如果有解，那么算法一定可以找到：

定理1： 对有限图，如果从初始节点 $st$ 到目标节点 $end$ 有路径存在，则A*算法一定成功结束。

首先证明算法必定结束。由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，那么必然会因为 $OPEN \ LIST$ 为空而结束。因此A算法必然会结束。
然后证明算法一定会成功结束。由于至少存在一条由初始点到目标点的路径，设此路径为 $P_{st}=st(v_0)\to v_1 \to v_2 \cdots \to end(v_m)$ 那么算法开始时，节点 $v_0$ 在 $OPEN \ LIST$ 中，而且路径中任一节点 $v_k$ 离开 $OPEN \ LIST$ 后，其后继节点 $v_{k+1}$ 一定会在这之前进入 $OPEN \ LIST$ 。这样在 $OPEN \ LIST$ 变空之前，目标节点必然会出现在 $OPEN \ LIST$ 中。因此，算法必定会结束。

引理1： 对无限图，若有从初始节点 $st$ 到目标节点 $end$ 的路径，则 $A^*$ 不结束时，在 $OPEN \ LIST$ 中即使最小的一个 $f(v_n)$ 值也将增到任意大，或有 $f(v_n)>f^*(st)$ 。

设 $d^*(v_n)$ 是 $A^*$ 生成的从初始节点 $v_0$ 到节点 $v_n$ 的最短路径长度（这里的长度指的是要经过多条边），由于搜索图中每条边的代价都是一个正数，令这些正数中最小一个数是 $e$ ，则有 $g^*(v_n)\ge d^*(v_n)\times e$ 。（ $g^*(v_n)$ 是源点到 $v_n$ 的最小代价， $d^*(v_n)$ 是源点到 $v_n$ 的最小长度，长度乘以所有边中的最小代价，得到的肯定比从源点到 $n$ 的最小代价要小）
又因为是最佳路径的代价，所以 $g(v_n)\ge g^*(v_n)\ge d^*(v_n)\times e$
又因为 $h(v_n)\ge 0$ ，所以 $f(v_n)=g(v_n)+h(v_n)\ge g^*(v_n)\ge d^*(v_n)\times e$
所以如果 $A^*$ 算法不终止，从 $OPEN \ LIST$ 中选出的节点必将拥有任意大的 $d^*(v_n)$ 值，因此，也将具有任意大的f值。

引理2： $A^*$ 结束前的任意时刻， $OPEN \ LIST$ 中总是存在结点 $v_k$ ，它是从初始结点 $st$ 到目标节点 $end$ 的一个节点，且满足 $f(v_k)<f^*(v_k)$ 。

设初始点 $st$ 到目标 $end$ 的最佳路径序列 $P_{st}=st(v_0)\to v_1 \to v_2 \cdots \to end(v_m)$ 。

算法开始的时候，节点 $st$ 在 $OPEN \ LIST$ 中，当节点 $st$ 离开 $OPEN \ LIST$ 进入 $CLOSE\ LIST$ 中时，节点 $v_1$ 进入 $OPEN \ LIST$ 。因此， $A^*$ 没有结束之前，在 $OPEN \ LIST$ 中，必然是最佳路径上的节点。设这些节点排在最前面的节点为 $v_k$ ，则有： $f(v_k)=g(v_k)+h(v_k)$
由于 $v_k$ 在最佳路径上，故有 $g(v_k)=g^*(v_k)$ ，从而 $f(v_k)=g^*(v_k)+h(v_k)$ 。
又由于 $A^*$ 算法性质二 $h(v_k)\le h^*(v_k)$ ，故有， $f(v_k)\le g^*(v_k)+h^*(v_k)=f^*(v_k)$ 。
因为在最佳路径上的所有节点的 $f^*$ 值都相同，因此有 $f(v_k)\le f^*(v_k)$ 。

定理2： 对无限图，若从初始节点 $st$ 到目标节点 $end$ 有路径存在，则 $A^*$ 一定成功结束。
反证法：

使用引理1：假设 $A^*$ 不结束，在 $OPEN \ LIST$ 中即使最小的一个 $f(n)$ 值也将增到任意大，或有 $f(n)>f^*(s)$
根据引理2：在 $A^*$ 结束前，必存在节点 $n$ ，使得 $f(n)<=f^*(s)$ ，所以，如果 $A^*$ 不结束，将导致矛盾， $A^*$ 算法只能成功结束。

推论2.1： $OPEN \ LIST$ 上任一具有 $f(n)<f^*(st)$ 的节点 $n$ ，最终都将被 $A^*$ 选作扩展节点。

由定理2，知 $A^*$ 一定结束，由 $A^*$ 的结束条件， $OPEN \ LIST$ 中 $f(end)$ 最小时才结束。
而 $f(end)\ge f^*(end)=f^*(st)$ ，所以 $f(n)<f^*(st)$ ，均被扩展，得证。

根据定理一和定理二可知，不论是在无向图还是在有向图中，如果有解一定可以被 $A^*$ 算法找到

再证明，算法找的的解一定是最优解：

引理一： 已知从初始节点 $st$ 到目标节点 $end$ 的一条最短路径 $P_{st}$ ，路径上任意一点 $n$ ， $g^*(n)= |P_{st}(st\to n)|$ 。

已知一条 $st$ 到 $n$ 的路径长度为 $|P_{st}(st\to n)|$ ，根据 $g^*(n)$ 的最小性 $g^*(n)\le |P_{st}(st\to n)|$ 。

利用反证法证明如下：

假设： $g^*(n)< |P_{st}(st\to n)|$ 。

那么，意味着存在一条路径 $P'$ ，该路径从 $st$ 到 $n$ 的长度 $|P'(st\to n)|<|P_{st}(st\to n)|$ 。

则 $|P'(st\to n)| + |P_{st}(n\to end)| < |P_{st}(st\to end)|$ 。这与 $P_{st}$ 为从 $st$ 到 $end$ 的最短路径矛盾。

所以原假设 $g^*(n) < |P_{st}(st\to n)|$ 不成立，因此 $g^*(n)=|P_{st}(st\to n)|$ 得证。

引理二： 已知从初始节点 $st$ 到目标节点 $end$ 的一条最短路径 $P_{st}$ ，路径上任意一点 $n$ ， $h^*(n)= |P_{st}(n\to end)|$ 。(证明思路和引理1相同)

已知一条 $n$ 到 $end$ 的路径长度为 $|P_{st}(n\to end)|$ ，根据 $h^*(n)$ 的最小性 $h^*(n)\le |P_{st}(n\to end)|$ 。

利用反证法证明如下：

假设： $h^*(n)< |P_{st}(n\to end)|$ 。

那么，意味着存在一条路径 $P'$ ，该路径从 $st$ 到 $n$ 的长度 $|P'(n\to end)|<|P_{st}(n\to end)|$ 。

则 $|P_{st}(st\to n)|+|P'(n\to end)| < |P_{st}(st\to end)|$ 。这与 $P_{st}$ 为从 $st$ 到 $end$ 的最短路径矛盾。

所以原假设 $h^*(n) < |P_{st}(n\to end)|$ 不成立，因此 $h^*(n)=|P_{st}(n\to end)|$ 得证。

引理三： 对于任意节点 $n$ ， $g(n)=g^*(n)$ 时 $f(n)$ 最小。

证明：已知 $f(n)=g(n)+h(n)$ 。对于 $h(n)$ ，在寻路前就已经确定，是一个定值。因此， $argmin(f(n))=argmin(g(n)+h(n))=argmin(g(n))+h(n)$ 。也就是说 $f(n)$ 的值只有在更新 $g(n)$ 时才会变。而 $g(n)$ 最小值是 $g^*(n)$ ，所以对节点n而言， $g(n)=g^*(n)$ 时 $f(n)$ 最小。

我们利用反证法进行证明：

假设： $A^*$ 算法求出的解不是最优，那么我们通过 $A^*$ 算法寻到了一条从 $st$ 到 $end$ 的路径 $P_{A^*}$ ，而这条路径并不是最短路径。

那么则存在最短路径 $P_{st}$ ，有 $|P_{st}|<|P_{A^*}|$ 。设最短路径 $P_{st}=st(v_0)\to v_1 \to v_2 \cdots \to end(v_m)$ 。

以下利用数学归纳法

归纳奠基：

当到节点 $v_n,n=0$ 时： 把节点 $st$ 放入 $CLOSE\ LIST$ 中，把 $st$ 相邻节点放入 $OPEN\ LIST$ 中并更新 $g$ 值。这一步后 $v_1$ 显然应该在 $OPEN\ LIST$ 中，并且因为节点 $v_1$ 为最短路径 $P_{st}$ 上的节点，根据引理一， $g^*(v_1)=|P_{st}(st\to v_1)|$ 。这里发现更新 $g(v_1)$ 时也是根据节点 $st$ 到节点 $v_1$ 的边的长度，即 $g(v_1)$ 更新为 $|P_{st}(st\to v_1)|$ ，这时有 $g(v_1)=g^*(v_1)$ 。根据引理三，这时的 $f(v_1)$ 就是最小值了，以后不会再发生变化。

利用算法本身性质一、引理一、引理二，有 $f(v_1)=g(v_1)+h(v_1)=g^*(v_1)+h(v_1)\le g^*(v_1)+h^*(v_1)=|P_{st}|<|P_{A^*}|$ 。也就是 $f(v_1)<f(end)$ 也成立。由 $A^*$ 算法的性质一可以知道， $v_1$ 节点一定可以在结束之前被选中，用来更新数据。

当到节点 $v_n,n=1$ 时： 若 $v_2$ 不在 $OPEN \ LIST$ 或 $CLOSE \ LIST$ 中，直接更新 $g(v_2)$ ；若在 $OPEN \ LIST$ 或 $CLOSE \ LIST$ 中，接下来由 $g(v_2)$ 与 $g(v_1)+|P_{st}(v_1\to v_2)|$ 的大小关系，判断是否会通过通过 $v_1$ 对 $g(v_2)$ 进行更新。

若更新，则有：

$\begin{aligned}g(v_2)&=g(v_1)+ |P_{st}(v_1\to v_2)|\\&=g^*(v_1)+ |P_{st}(v_1\to v_2)|\\&=|P_{st}（st\to v_1）| + |P_{st}(v_1\to v_2)|\\&=|P_{st}（st\to v_2）|\\&=g^*(v_2)\end{aligned}$

根据引理一，此时的 $g(v_2)$ 是最小的，所以若 $g(v_2)$ 更新，则 $g(v_2)=g^*(v_2)$ 。

若不更新，则说明 $g(v_2)\le g(v_1)+|P_{st}(v_1\to v_2)| = g^*(v_2)$ ，又因为 $g^*(v_2)\le g(v_2)$ ，则 $g(v_2)=g^*(v_2)$ 。

这意味着通过 $v_1$ 对节点 $v_2$ 计算 $g(v_2)$ 后，无论是否更新， $g(v_2)$ 都会取 $g^*(v_2)$ 。那么把 $v_1$ 放入 $CLOSE\ LIST$ 后，无论 $v_2$ 在 $CLOSE\ LIST$ 或 $OPEN \ LIST$ 中，还是不在，最终的 $g(v_2)$ 都等于 $g^*(v_2)$ 。根据引理三，这时的 $f(v_2)$ 就是最小值了，以后不会再发生变化。

归纳假设：对于节点 $v_n,n=k$ 时，满足 $g(v_{k})=g^*(v_{k})$ ，且以后不会发生变化。

归纳递推：对于节点 $v_n,n=k+1,k\le m-1$ 时：

利用算法本身性质一、引理一、引理二，有 $f(v_k)=g(v_k)+h(v_k)=g^*(v_k)+h(v_k)\le g^*(v_k)+h^*(v_k)=|P_{st}|<|P_{A^*}|$ 。也就是 $f(v_k)<f(end)$ 也成立。由 $A^*$ 算法的性质一可以知道， $v_k$ 节点一定可以在结束之前被选中，用来更新数据。

若 $v_{k+1}$ 不在 $OPEN \ LIST$ 或 $CLOSE \ LIST$ 中，直接更新 $g(v_{k+1})$ ；若在 $OPEN \ LIST$ 或 $CLOSE \ LIST$ 中，接下来由 $g(v_{k+1})$ 与 $g(v_{k})+|P_{st}(v_k\to v_{k+1})|$ 的大小关系，判断是否会通过通过 $v_k$ 对 $g(v_{k+1})$ 进行更新。

若更新，则有：

$\begin{aligned}g(v_{k+1})&=g(v_k)+ |P_{st}(v_k\to v_{k+1})|\\&=g^*(v_k)+ |P_{st}(v_k\to v_{k+1})|\\&=|P_{st}（st\to v_k）| + |P_{st}(v_k\to v_{k+1})|\\&=|P_{st}（st\to v_{k+1}）|\\&=g^*(v_{k+1})\end{aligned}$

根据引理一，此时的 $g(v_{k+1} )$ 是最小的，所以若 $g(v_{k+1})$ 更新，则 $g(v_{k+1})=g^*(v_{K+1})$ 。

若不更新，则说明 $g(v_{k+1})\le g(v_k)+|P_{st}(v_k\to v_{k+1})| = g^*(v_{k+1})$ ，又因为 $g^*(v_{k+1})\le g(v_{k+1})$ ，则 $g(v_{k+1})=g^*(v_{k+1})$ 。

这意味着通过 $v_k$ 对节点 $v_{k+1}$ 计算 $g(v_{k+1})$ 后，无论是否更新， $g(v_{k+1})$ 都会取 $g^*(v_{k+1})$ 。那么把 $v_k$ 放入 $CLOSE\ LIST$ 后，无论 $v_{k+1}$ 在 $CLOSE\ LIST$ 或 $OPEN \ LIST$ 中，还是不在，最终的 $g(v_{k+1})$ 都等于 $g^*(v_{k+1})$ 。根据引理三，这时的 $f(v_{k+1})$ 就是最小值了，以后不会再发生变化。

综上所述： $\forall k \in Z, 0\le k \le m, 满足g(k)=g^*(k)$ ，且以后不会发生变化。

因此，最后从 $OPEN\ LIST$ 中取出 $end(v_m)$ 节点的时候， $|P_{A^*}|=f(v_m)=g(v_m)+h(v_m)=g^*(v_m)+h(v_m)=g^*(v_m)=|P_{st}|$ 。这是一条根据 $A^*$ 算法找到的路径 $P_{A^*}$ 。这显然与我们最初的假设“通过 $A^*$ 算法找到的路径不是最小值，也就是 $|P_{st}|<|P_{A^*}|$ ”矛盾。所以假设不成立，通过 $A^*$ 算法找到的就是最短路径。

A*算法证明与详解

目录

背景

算法介绍

算法搜索过程

核心

搜索思路

算法流程图

算法正确性证明

前置知识

开始证明

相关推荐