A-star

Posted on 2025-08-25 Edited on 2025-08-25 Word count in article: 2.9k Reading time ≈ 10 mins.

最近需要解决图论的一个问题，找到了很多优化算法但在这些基础的优化算法中，发现了一个比较有趣的算法 A*，为此写下这篇笔记记录“探索”的过程

何为 A* Algorithm?

A* 是应用在网格图当中的 网格搜索算法(Grid-based Search Algorithms)，相较于 Dijkstra 和 BFS, 它能平衡它们之间的优点：既能有像 Dijkstra 数学方法的精准，又能有像BFS(Best First Search) 启发式方法 的迅速。这两个优点是通过一个**评价函数 F(n) **结合起来实现的。

评价函数(Evaluation function) F(n)

A*的核心数学运行逻辑就集成到了这个**评价函数 F(n) **当中了, 他是这样定义的：

F(n) = g(n) + h(n)

先补一句开头没写清楚的地方：我这里写的 BFS 其实是想说 Best-First Search，不是 Breadth-First Search。这两个东西都能缩成 BFS，但在 A* 的语境下差别很大，下面统一写 Best-First Search，免得把自己绕进去。

先把 F(n) 拆开

刚看到这个公式的时候，我第一反应是：g 和 h 都知道，加起来不就完了？真往下走才发现，A* 有意思的地方不是“加法”，而是它怎么用这两个量来分配注意力。

g(n)：从起点走到 n，已经花掉的实际代价。这个是事实，路是怎么走的，加起来就知道。
h(n)：从 n 到终点，大概还要花多少代价。这个是估计，也就是所谓的 heuristic function。
f(n)：从起点经过 n 再到终点，总共预计要花多少代价。

所以 F 不是“已经走过的路”，也不是“完全凭感觉猜的路”，它更像一句话：我已经花了这么多，接下来大概还要花这么多。

把这三个量放在一起比较，会得到一个挺直观的结论：

排序方式	实际含义
`f = g`	只认已经走过的代价，h 相当于 0，退化成 Dijkstra
`f = h`	只看谁看起来离终点近，退化成 Best-First Search
`f = g + h`	既看已经走过的路，也看对剩余路程的估计，这才是我要的 A*

所以 A* 所谓的“平衡”，不是把 Dijkstra 和 Best-First Search 暴力拼起来，而是把“事实”和“猜测”放进同一个优先级里。这个点想通之后，公式就不像一个需要死记的结论了。

A* 到底是怎么跑的

A* 的搜索过程和 BFS 有点像，最大的区别是队列不再先进先出，而是按 f 排序的小根堆。每次从 open set 里取出当前 f 最小的节点，沿着它往外扩一圈。

需要维护的东西大概有这些：

openSet：已经发现、但还没有展开的节点，按 f 排序。
gScore：目前已知的、从起点到某个节点的最小实际代价。其它节点先设成无穷大。
parent：记录每个节点是从哪里来的，最后用来倒推路径。
closedSet：已经确定最短路的节点。注意，不是“访问过”就叫 closed，这个概念后面还会说。

写成伪代码大概是这样：

open = minHeap ordered by f
gScore[start] = 0
open.push(start, heuristic(start, goal))

while open is not empty:
    current = open.pop()

    # 堆里可能留着旧状态，和最新的 gScore 对不上就直接丢掉
    if current.g != gScore[current]:
        continue

    if current == goal:
        return buildPath(parent, goal)

    for next in neighbors(current):
        tentativeG = gScore[current] + cost(current, next)

        if tentativeG >= gScore[next]:
            continue

        parent[next] = current
        gScore[next] = tentativeG
        open.push(next, tentativeG + heuristic(next, goal))

return no path

这里我故意没有写 fScore 的全局数组，因为节点每次更新以后，直接把新的 (节点, f) 塞进堆里更省事。很多语言的标准堆没有 decrease-key，与其自己想办法改堆里的优先级，不如懒更新：发现更短的路径就 push 一份新状态，等旧状态被弹出来的时候，用当前 gScore 一对，发现过期了就跳过。

这个做法会多占一点内存，但代码简单很多，实际写 A* 时很常用。你可能发现伪代码里没有 closedSet，这是故意的：只靠 gScore 和过期状态跳过也能跑；closedSet 是优化，不是算法成立的前提。只有 h consistent 的时候，节点第一次出队就可以放心关掉，否则还要允许它重新打开。

Java 里大概就是：

record NodeState(int x, int y, int g, int f) {}

PriorityQueue<NodeState> open =
        new PriorityQueue<>(Comparator.comparingInt(NodeState::f));

如果在 f 相同的情况下再按 h 从小到大排，也就是优先选更靠近终点的节点，通常能少展开不少无关节点。这个只是调整同优先级节点的顺序，不会把精确 A* 改成近似算法。

这里也可以顺便解释一个现象：在空旷的网格图上，A* 不一定像我一开始想的那么“聪明”。因为很多节点的 f 会一样大，堆先弹谁，很大程度上取决于 tie-break。没有这个处理，A* 可能会像摊大饼一样铺开一片，看起来仍然很努力，实际上没少做无用功。

h(n) 怎么选

A* 里最容易拍脑袋的地方就是 h。它不是随便写个距离函数就行，得跟你的移动规则和边的代价对上。

拿最常见的网格图举例：

移动方式	常用 heuristic
只能上下左右走，每步代价 1	Manhattan：`dx + dy`
八方向都能走，每步代价都是 1	Chebyshev：`max(dx, dy)`
八方向都能走，斜走代价是 `sqrt(2)`	Octile：`max(dx, dy) + (sqrt(2) - 1) * min(dx, dy)`
可以朝任意方向走	Euclidean：`sqrt(dx * dx + dy * dy)`

假设当前点是 (x, y)，终点是 (gx, gy)，dx = abs(x - gx)，dy = abs(y - gy)。如果只能上下左右走，每步代价 1，那从当前点到终点至少要横向走 dx 步、纵向走 dy 步，所以：

1
2
3

int heuristic(int x, int y, int gx, int gy) {
    return Math.abs(x - gx) + Math.abs(y - gy);
}

这个 Manhattan 距离不会高估真实剩余距离，因为不管路怎么绕，横向和纵向的步数都省不掉。注意，如果你允许斜着走，而且斜走一步的代价只有 1，Manhattan 反而会高估：从 (0, 0) 到 (1, 1) 实际一步就到，Manhattan 却算成 2。这时候应该换 Chebyshev，或者按照真实规则换成 octile 距离。

我一开始就觉得，heuristic 不就是“估个距离”吗？后来才反应过来，heuristic 的难点不是想一个距离，而是保证这个估计和真实代价的边界是对的。 你估得太低，A* 会多走一些路；估得太高，最短路的保证直接没了。

A* 为什么能找到最短路

这一段是我觉得 A* 最值得多看一眼的地方，因为它解释了“为什么不是随便给个启发式都能叫 A*”。

A* 能保证最短路，靠的不是 h 猜得准，而是 h 不能高估。这个性质叫 admissible：

对任意节点 n，h(n) 不能大于从 n 到终点的真实最小代价。

如果这个条件成立，可以做一个很直白的反证：

假设 A* 第一次把终点弹出时，实际上还存在一条更便宜的路。那这条更便宜的路上，一定有一个已经发现但还没处理完的节点 n。因为 h(n) 没有高估，所以 f(n) 不会大于那条更便宜路的总代价，也就一定小于当前终点的 f。那 n 应该比终点先出队，和“终点已经被弹出”矛盾。

所以 A* 第一次弹出终点时，拿到的就是最短路。

不过还有一个更实用的性质叫 consistent，也叫 monotone：

h(n) <= cost(n, next) + h(next)

用人话说就是：从 n 到终点的估计，不能比“先走一步到 next，再从 next 估到终点”还要大得离谱。它比 admissible 更强一点，但换来一个很舒服的结果：沿着任意一条路径走，f 不会突然变小。这样每个节点第一次出队时，g 就已经是最小的，可以放心丢进 closed set，不需要再打开。

如果 h 只是 admissible、但不 consistent，A* 仍然可能找到最短路，但你可能需要允许节点重新打开。很多“A* 有时候会返回次优路径”的问题，不是 A* 本身有问题，而是 closed set 用得太死，节点发现更短的 g 之后没有被重新放回 open set。

几个容易踩的坑

不要在生成邻居的时候就直接返回终点。 除非你能确认 heuristic 和堆的 tie-break 都满足你的假设，否则最稳的是等终点从堆里弹出来再判断。否则你可能只是找到“第一条到终点的路”，不是最短路。
不要把“访问过”当成“已经最优”。 节点第一次被看到，不代表当前 g 就是最终的最小 g。只有 consistent heuristic 下，节点出队后才比较有底气做这个判断。
heuristic 一定要和移动规则一致。 八方向、斜走代价、障碍能不能穿，这些规则一变，h 也要跟着变。
边权不能为负。 A* 和 Dijkstra 一样，默认边权非负。图里有负权边，就不是换个 h 能救的问题，要考虑 Bellman-Ford 之类的算法。
A 不是永远快。* 在有限图上、用堆实现，并且 h consistent 的话，通常可以按 O(E log V) 来理解，空间是 O(V)；但搜索树的最坏情况仍然可能是指数级。h 选得不好，A* 也可能铺得很开。

如果实际业务里能接受“次优但更快”，还有个常见的变种：**Weighted A**，把排序改成 f = g + w * h，其中 w > 1。这时 h 被人为放大，搜索会更激进，路径可能不是最短。它不是 A 的 bug，而是主动拿最优性换时间。这个在做游戏寻路、地图导航这种场景其实很常见，但前提是你要清楚自己接受了什么。

写在最后

一开始我想看 A*，是因为它看起来像一个“又准又快”的算法。写到这里我才觉得，它真正有意思的地方不是快，而是它把“已知”和“未知”放在了一起：g 是已经付出的事实，h 是对未来的估计，f 是这两者的折中。

A* 的底线也很朴素：你可以对未来乐观，但不能乐观到高估。 这个限制听起来有点扫兴，但正是因为有了它，算法才能在“看见希望”和“保证正确”之间找到一个平衡。

如果后面真要把这套东西落到代码里，我的顺序大概会是：先把移动规则和代价定义清楚，再选一个 admissible 的 h，最后用一个小网格验证路径长度。先别急着加花哨的 tie-break 和权重，基础版本跑对了，再谈优化。毕竟算法这东西，跑得快但路是错的，也没什么值得高兴的。😄