A* 与 IDA*

算法与题解 →

用于搜索给定起点 $s$ 到给定终点 $t$ 的最短路径。

---

记号与约定#

$\mathbb{G}=(\mathbb{V},\mathbb{E})$ 表示一张图，其中顶点组成的集合是 $\mathbb{V}$，边组成的集合是 $\mathbb{E}$.

$d_{xy}$ 表示图上从点 $x$ 到点 $y$ 的最短路径长度。
由于 A* 是单起点单终点最短路，因此用 $s$ 表示起点，$t$ 表示终点。
$h^*(x)$ 表示从 $x$ 到 $t$ 的最短路径长度，即 $h^*(x)=d_{xt}$.
$h(x)$ 是后文会提到的启发式估价函数，尝试在 $h^*(x)$ 尚且未知的情况下去估计它。
$g(x)$ 表示从 $s$ 到 $x$ 的某条路径的长度，具体指哪一条由上下文确定。

---

A*#

引入#

暴力地来说，如果要搜索从 $s$ 到 $t$ 的最短路径，可以用 BFS 搜索所有路径，然后每次用可能的最短路径更新 $s$ 到 $t$ 的距离。

然而，极端地说，如果我们事先能知道与 $x$ 点相连的每个点 $y$ 到终点的距离 $h^*(y)$，那么我们每次搜索只需要从 $x$ 走到 $\arg\min\limits_y h^*(y)$，就能保证我们一直在最短路径上，最终走到终点得到最优解，复杂度只有 $O(d)$，其中 $d$ 为最短路径的边数。

显然，我们不可能事先知道 $h^*(y)$，否则答案已经给出，根本不用求解。但是，即使没有 $h^*(y)$，我们能否用一些估计函数 $h(y)$ 去估计 $h^*(y)$，以达到优化目的呢？

过程#

我们尝试设计一个 $h(n)$，它在大多数情况下能给出近似的估计。但难免有时会使走到非最优的路径上。此时，我们仍然仅使用 $h(n)$ 去评判从 $s$ 经过 $n$ 到达 $t$ 的路径的优劣显然是不好的，而应当加入已经走过的真实路径长度 $g(n)$，即使用 $f(n)=g(n)+h(n)$ 来评判。

A* 维护一个优先队列，存储当前能到达的每个节点。每次取出 $f(n)$ 最小的节点 $n$，并将 $n$ 的所有后继节点处理并弹入优先队列。

然而，这时的 A* 还没有达到它的最佳性能。设想一下，我们的算法好不容易第一次走到了终点，此时得到了终点的 $g(t)$；但是，由于我们 $h(x)$ 估计是有误差的，万一先前某个由于 $h(x)$ 虚高而未被探索的分支，实际上能给出更优的路径，这又该怎么办呢？如果等待算法搜索完所有的路径，其复杂度甚至可能高于 Dijkstra.

所以，我们希望通过良好的 $h(x)$ 外加严谨的分析推导，保证我们在第一次“走到”（实际上是弹出）终点时，获得的就一定是最优路径。

以下引入两个性质来评价 $h(x)$ 设计的优劣：

• 可采纳性 (Admissibility)

$$\forall x \in \mathbb{V},\ h(x)\le h^*(x)$$

即估价函数给出的代价永远不超过真实代价，又称“不虚高”。

• 一致性(Consistency)/单调性(Monotone)

$$\forall x,y \in \mathbb{V},\ h(x) \le d_{xy} + h(y)$$

可以理解为估价函数满足三角不等式。当 $y$ 位于 $x$ 到 $t$ 的最短路上时，这个不等式实际上表示 $f(x)$ 沿最短路单调不降。

下面证明两个命题：

命题 1：若 $h(x)$ 满足一致性，则任何点 $n$ 对应的 $f(n)$ 第一次从优先队列弹出时，此刻的 $g(n)$ 就是从 $s$ 到 $n$ 的最短路径。#

证明： 题目等同于：如果某个 $f(n)$ 第一次取出时 $g(n)$ 并非最优，那么 $h(x)$ 一定不是一致的。

实际上，如果优先队列中同时存在多个不同的 $f(n)$，那么最小的 $f(n)$ 一定对应最小的 $g(n)$（因为 $h(n)$ 相同），因此任何时刻取出的 $f(n)$ 在优先队列内一定最优。

因此要出现题目所说情况，必然是 $f(n)$ 被弹出后，重新弹入了更优的 $f(n)$. 设先前在优先队列中的为 $f'(n)$，后来进入的为 $f''(n)$，对应的 $n$ 的前序节点分别为 $p,q$，对应时刻的 $g(n)$ 分别为 $g'(n)$ 和 $g''(n)$.

从而有 $g'(n)=g(p)+d_{pn}$ $g''(n)=g(q)+d_{qn}$

此处可以假设从 $s$ 到 $p,q$ 的最短路径就是 $g(p),g(q)$，否则可以令 $n$ 为 $p$ 或 $q$，从头证明。

由于 $f''(n)$ 在 $f'(n)$ 弹出后才进入，因此存在 $f'(n)<f(q)$.

根据定义： $f'(n)=g'(n)+h(n)=g(p)+d_{pn}+h(n)$ $f(q)=g(q)+h(q)$

从而

$$g(p)+d_{pn}+h(n)<g(q)+h(q) \tag{\#}$$

同时，由于我们假设 $g'(n)$ 并非最优，即 $g'(n)$ 劣于 $g''(n)$，也即 $g'(n)>g''(n)$，因此有

$$g(p)+d_{pn} > g(q)+d_{qn} \tag{*}$$

联立 $(\#),(^*)$ 两式，就得到了 $g(q)+d_{qn}+h(n)<g(q)+h(q)$

即 $d_{qn}+h(n)<h(q)$

不满足一致性 $h(q) \le d_{qn}+h(n)$. 证毕。

未完待续 …