A*

(Updated: )

A*

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function A*():
  // Step 1 
  Mark s "open" and calculate f(s).
  
  // Step 2 
  Select the open node n whose value of f is smallest.
  Resolve ties arbitrarily, but always in favor of any node n in T.
  
  // Step 3
   If n is in T, mark n "closed" and terminate the algorithm.
  
  // Step 4 
  Otherwise, mark n "closed" and apply the successor operator V to n. 
  
  Calculate f for each successor of n and mark as open each successor not already marked closed.
  
  Remark as open any closed node m, which is a successor of n,
  and for which f(m) is smaller now than it was when m was marked closed. 
  
  Go to Step 2.

定义

我们使用如下定义：

一个图 含有起点 和目标点集 , 边表示为

表示经过 的从 到目标点集 的最短距离

我们有 , 表示从 到 的最短距离， 表示从 到目标点集的最短距离

同时我们需要两个估计函数 和

我们可以取 为当前从 到 的最短距离

, 因为任何局部最优解不会比全局最优解更优

同时可以取 为我们在反图上跑出来的，从目标点集到 的最短距离

这里要求 ，即 是 的一个 lower bound

可容性

A*算法可以找到最优解，则满足可容性/可采纳性 (admissible)

在之前的定义中，, 意为我们不会过分估计未来需要的花费

我们接下来要证明，如果 , 则 A* 算法满足可容性

Lemma 1: 对于任意一个未关闭节点 和对应的从 到 的最短路 , 存在一个节点 使得

证明：

如果 是打开的，那么令 即可

如果 关闭，令 为 上的节点 组成的集合， 满足已关闭且满足

由于 关闭，所以 非空

选出一个标号最大的点 , 由于 未关闭，所以

令 为 的后继节点

由 的定义我们有

同时 , 因为

, 因为 是最短路

所以我们有

而一般地， 一定成立

所以 , 且 未关闭

Corollary: 假设 , 且 A* 算法未停止。那么在任意一条最短路 上, 存在一个 上未关闭点 满足

证明：由引理1，存在一个 使得

所以

而因为是最短路，所以有 对所有 成立

所以存在一个 使得

Theorem 1: 如果 对所有 成立，那么 A* 是 Admissable (可容) 的

证明：反证

假设不成立，有 3 中情况：

  • Case 1: 不会停止在目标点集

这与停止条件矛盾

  • Case 2: 不会停止

假设每条边最小值是 , 那么对于距离 点步数大于 步的所有点 ，我们有 , 这说明这些节点都不会被拓展

这是由于引理1的推论，存在点 使得 , 所以算法选点时会选择 而不是

那么算法不停止只会是因为距离起点 步以内的点被重复打开

表示这些点组成的点集, 表示点集大小

但是经过这些点的路径只有有限条，记为

记

那么经过 步后，所有节点一定都关闭，此时算法结束

  • Case 3: 停止时解不是最优解

假设算法停在了 目标点 上，满足 ，后一个不等式说明了不是最优解

但是由引理1的推论，在终止前存在一个点 满足

所以算法应该先选择 而不是 , 故得出矛盾

综上，三种情况都不满足，命题得证

一致性

如果 , 则满足一致性

这里 , 可以直接看成实际距离

Lemma 2: 在一致性条件下，如果一个节点 被关闭，那么

先说一下这个引理的重要性

它主要重要在两方面：

首先，它可以用来证明 A* 的最优性

其次，它说明算法不需要重新打开一个已经关闭的节点

即 A* 算法不会重复扩展同一节点

这样，我们就可以把算法第 步的重新打开节点的操作省去

这一点与 Dijkstra 是一样的

下面是证明

证明：反证

假设关闭 之前有

此时存在一个从 到 的最短路

因为 ，所以当前的路径不是最短路，即算法尚未发现

根据引理1， 存在一个 上的点 满足

如果 , 我们就证明了这个引理

否则我们有

所以

两边同加 :

由于一致性:

所以

即

这与我们选择 矛盾，因为我们应该选择

故得证

Lemma 3: 令 表示 A* 依次关闭的节点. 那么对于 , 有

这说明了 的单调不降性

证明：

假设 是 A* 关闭 后要关闭的节点

如果到 的最短路不经过 ，说明 不由 拓展，他们是并列关系

在选择 后才选 , 就说明了 , 则引理成立

如果到 的最短路经过 ，我们有

由引理2， 我们有 和

则

故得证

Corollary: 如果 关闭，那么

证明：

由引理3，

最优性

下面的定理和推论我们都不加证明地给出，具体证明参见原论文

首先是没有出现 ties 的情况

这里的 ties 指 A* 同时可以选择两个及以上的节点

具体地，存在 满足 对其他 成立

Theorem 2: 令 A 是任意可容的，不比 A* 有更多信息 (informed) 的算法， 为边权最小值为 ，满足 ， 的图, 且满足一致性。则如果 在 A* 中被拓展，则在 A 中也会被拓展

这里的 informed 未定义，可以感性理解一下，就是 函数包含的信息有效性

比如， 就不如之前从 到 的最短路更有信息

Corollary: 定义 为 A 算法在 图上拓展的节点，那么

这样我们就说 A* 是一个最优的算法， 因为它拓展了最少的节点

然后是有 ties 存在的情况

令 G* 表示所有处理 ties 方式不同的 A* 算法的集合

Theorem 3: 令 A 是任意可容的，不比 G* 有更多信息的算法， 为边权最小值为 ，满足 ， 的图, 且满足一致性。则存在一个 A* G*, 如果 在 A* 中被拓展，则在 A 中也会被拓展

Corollary 1: 存在一个 A* G* 满足

Corollary 2: 定义 为 A* 应用于 上的总 critical ties 个数, 则对任意一个 A* G*, 我们有

对于 noncritical ties, 满足所有其他可选的节点一定同时被 A 和 A* 拓展

critical ties 即为相反定义

可容性与一致性的关系

Theorem 4: 如果启发函数满足一致性， 一定满足可容性

证明：

对于任意节点 , 从 到目标点集的最短路为 ，最短路上节点为

与 的选取

退化为 Dijkstra

且边权为 退化为 BFS

退化为 Greedy Best First Search

参考文献

更加严谨，具体的证明与分析可以见A*算法的原论文

A Formal Basis for the Heuristic Determination of Minimum Cost Paths