算法笔记

A* 搜索算法

过程

$A^*$算法的目标是找到有向图上从起点 $s$ 到终点 $t$ 的最短路径。

设 $d(x, y)$ 为结点 $x$ 与 $y$ 之间的距离，也就是它们之间最短路径的长度。记 $g(x)=d(s, x)$ 为从起点 $s$ 到结点 $x$ 的距离函数，$h^*(x)$为从结点 $x$ 到终点 $t$ 的距离函数，$h(x)$ 为 $h^*(x)$ 的一个估计。

最后，记从 $s$ 出发经由 $x$ 到达 $t$ 的最短路径长度的估计为 $$ f(x)=g(x)+h(x) . $$

搜索时， A 算法每次从优先队列中取出一个 $f$ 最小的结点。然后，将它的所有后继结点 $x$ 都推入优先队列中，并利用实际记录的 $g(x)$ 和估计的 $h(x)$ 更新 $f(x)$ 。

性质

1.可采纳的（admissible）:图上没有负权边，且满足$0\leq h\leq h^*$，这样一定可以找到最短路。

证明（通过反证法）： - 假设A＊算法没有找到最短路径，而是返回了一个代价为 $C$ 的路径（其中 $C>C^*, ~ C^*$ 是最优代价）。 - 由于 $h(n)$ 是可采纳的，对于任何在最短路径上的节点 $n$ ，有：

\[ f(n)=g(n)+h(n) \leq g(n)+h^*(n)=C^* \]

显然矛盾

2.如果 $h$ 不仅是可采纳的，还是 一致的（consistent），即 $$ h(x) \leq h(y)+d(x, y), $$

那么， $\mathrm{A}^*$ 算法不会将已经弹出队列的结点再次加入队列。一致性条件，可以理解为结点 $x, y, t$ 之间的三角形不等式。

当$h\equiv 0$，退化至$Dijkstra$算法；当$h\equiv 0$且边权为1时，就是$BFS$算法。