A* 是在 Dijkstra 的基础上引入启发函数 h(n) 的最短路径算法，用「到终点的估计代价」引导搜索方向，大幅减少无效节点的探索，是地图导航、游戏寻路的基础算法。
相关文章：双向搜索 · Contraction Hierarchies
目录
| 章节 | 说明 |
|---|---|
| Dijkstra 的局限 | 无方向感，向四面八方展开 |
| 核心思想 | f(n) = g(n) + h(n) 三要素 |
| 启发函数设计 | 可采纳性、一致性，地图常用启发函数 |
| 算法流程 | Open/Closed 集合，逐步推导 |
| Java 实现 | 通用图上的 A* 完整代码 |
| 复杂度与性质 | 时间空间复杂度，最优性证明 |
| 与 Dijkstra 对比 | 搜索范围直观比较 |
| 地图导航中的应用 | 道路网络的启发函数选择 |
| 参考资料 | 论文与文档 |
Dijkstra 的局限
Dijkstra 算法以「已走代价 g(n)」为优先级，向四面八方均匀扩展，直到找到终点。
对于地图路由问题，起点在北京，终点在上海，Dijkstra 会同时探索北京四周所有方向的节点——包括大量向北、向西的无关节点，直到搜索前沿最终覆盖到上海。
Dijkstra 搜索范围（示意）： A* 搜索范围（示意）：
●●●●●●● · · · · ·
●●●●●●●●●●● · · ●●●●● ·
●●●●●S●●●●●●● · · ●S●●● ·
●●●●●●●●●●● · · ●●●●G ·
●●●●G●●● · · · · ·
探索了大量无关节点 集中在起点到终点的通道
A* 的改进：在 g(n) 之外加入启发函数 h(n)，引导搜索朝终点方向推进。
核心思想
A* 对每个节点维护三个值：
| 符号 | 含义 | 来源 |
|---|---|---|
| g(n) | 从起点到节点 n 的已知最短代价 | 实际计算，精确值 |
| h(n) | 从节点 n 到终点的估计代价 | 启发函数，近似值 |
| f(n) | 经过节点 n 的路径总估计代价 | f(n) = g(n) + h(n) |
核心原则：每次从 Open 集合中取出 f(n) 最小的节点展开，而不是 g(n) 最小（Dijkstra）。
以上图为例：
节点 g h f
S 0 7 7 ← 起点
A 2 4 6 ← f 最小，优先展开
B 1 6 7
C 5 2 7 ← 经 A 到达，继续展开
G 7 0 7 ← 到达终点，最优路径 S→A→C→G，代价 7
节点 B（f=7）虽然被探索，但 f 不更优，最终不在路径上。
启发函数设计
可采纳性（Admissibility）
h(n) 永远不高估实际代价，即：
h(n) ≤ h*(n) h*(n) 为 n 到终点的真实最短代价
可采纳的 h(n) 保证 A 找到最优解*。若 h 高估，可能错过最优路径。
一致性（Consistency / Monotonicity）
对任意节点 n 及其后继 n'，有：
h(n) ≤ cost(n, n') + h(n')
即"当前节点的启发值 ≤ 走一步的代价 + 下一节点的启发值"（三角不等式）。
一致性 → 可采纳性（充分不必要），且保证每个节点只被展开一次（无需重新入队）。
地图导航常用启发函数
| 名称 | 公式 | 适用场景 | 是否可采纳 |
|---|---|---|---|
| 欧式距离 | √((x₁-x₂)²+(y₁-y₂)²) | 任意方向移动（道路） | ✅ |
| 曼哈顿距离 | |x₁-x₂| + |y₁-y₂| | 仅四向移动（网格） | ✅（四向网格） |
| 切比雪夫距离 | max(|Δx|, |Δy|) | 八向移动（游戏地图） | ✅（八向网格） |
| h = 0 | 常数 0 | 退化为 Dijkstra | ✅（但无加速） |
道路网络中使用直线距离 / 最高限速：
h(n) = 直线距离(n, goal) / 全网最大限速
这是可采纳的：实际行驶时间 ≥ 直线距离 / 最大限速。
算法流程
初始化：
Open = {start} // 待探索节点（优先队列，按 f 排序）
Closed = {} // 已探索节点
g[start] = 0
f[start] = h(start)
循环：
n = Open.poll() // 取出 f 最小的节点
if n == goal: 返回路径
Closed.add(n)
for 每个邻居 m of n:
if m in Closed: continue
new_g = g[n] + cost(n, m)
if m not in Open or new_g < g[m]:
g[m] = new_g
f[m] = new_g + h(m)
parent[m] = n
Open.add(m) // 更新或插入
路径重建：从 goal 沿 parent 回溯到 start
Java 实现
import java.util.*;
public class AStar {
record Node(int id, double f) implements Comparable<Node> {
public int compareTo(Node o) { return Double.compare(this.f, o.f); }
}
/**
* @param graph 邻接表：graph[u] = [(v, weight), ...]
* @param h 启发函数：h[i] = 节点 i 到终点的估计代价
* @param start 起点
* @param goal 终点
* @return 最短路径节点列表，不可达返回空列表
*/
public static List<Integer> search(List<int[]>[] graph, double[] h, int start, int goal) {
int n = graph.length;
double[] g = new double[n];
int[] parent = new int[n];
Arrays.fill(g, Double.MAX_VALUE);
Arrays.fill(parent, -1);
g[start] = 0;
PriorityQueue<Node> open = new PriorityQueue<>();
boolean[] closed = new boolean[n];
open.offer(new Node(start, h[start]));
while (!open.isEmpty()) {
Node cur = open.poll();
int u = cur.id;
if (closed[u]) continue; // 旧版本，跳过
closed[u] = true;
if (u == goal) return buildPath(parent, start, goal);
for (int[] edge : graph[u]) {
int v = edge[0];
double w = edge[1];
if (closed[v]) continue;
double newG = g[u] + w;
if (newG < g[v]) {
g[v] = newG;
parent[v] = u;
open.offer(new Node(v, newG + h[v])); // 允许重复入队（lazy deletion）
}
}
}
return Collections.emptyList(); // 不可达
}
private static List<Integer> buildPath(int[] parent, int start, int goal) {
LinkedList<Integer> path = new LinkedList<>();
for (int v = goal; v != -1; v = parent[v]) path.addFirst(v);
return path;
}
}
关键点：
- 允许节点重复入队（lazy deletion），通过
closed[]跳过旧条目，比显式删除更简单 - 实际路网中
h数组可替换为函数式接口ToDoubleFunction<Integer>
复杂度与性质
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(b^d)（最坏） | b=分支因子，d=最优路径深度；好的启发函数大幅减少实际搜索量 |
| 空间复杂度 | O(b^d) | Open 集合存储所有边界节点 |
| 最优性 | ✅ h 可采纳时保证最优 | 数学归纳法证明 |
| 完备性 | ✅ 有限图上保证找到解 | 若解存在 |
实际性能：在道路网络上，配合欧式距离启发函数，A* 相比 Dijkstra 减少 70%～90% 的节点展开量。但对于大规模路网（亿级节点）仍不够快，需要 Contraction Hierarchies 等进一步加速。
与 Dijkstra 对比
| 维度 | Dijkstra | A* |
|---|---|---|
| 优先级 | g(n)（已走代价） | f(n) = g(n) + h(n) |
| 搜索方向 | 无方向，全局扩散 | 引导向终点 |
| 是否最优 | ✅ 始终最优 | ✅ h 可采纳时最优 |
| 预处理 | 无 | 需要计算 h（通常 O(1)） |
| 实现复杂度 | 低 | 略高（需定义 h） |
| 适用场景 | 单源最短路（无终点） | 单源单终点（有明确目标） |
Dijkstra = A*（h ≡ 0）的特例。
地图导航中的应用
直接使用 A* 的场景
- 步行导航（< 5km）：节点数量少，A* 够快
- 游戏寻路：格子地图，曼哈顿距离完美可采纳
- 室内导航：楼层有限，节点规模可控
A* 不足以独立应用的场景
全国驾车导航的路网有 数亿节点，即使 A* 减少 90% 探索量，单次查询仍需数百毫秒，无法满足实时要求。
工业解决方案的演进：
A* （基础）
↓ 不够快
双向 A* （两端同时搜索）
↓ 仍不够
Contraction Hierarchies （预处理 + 层级搜索）
↓ 支持实时路况
Customizable CH（CCH）
详见 Contraction Hierarchies。
参考资料
参考资料
- Hart, Nilsson, Raphael — A Formal Basis for the Heuristic Determination of Minimum Cost Paths (IEEE 1968) — A* 原论文
- 双向搜索（在 A* 基础上两端同时搜索，进一步提速）
- Contraction Hierarchies（工业级道路路由算法）
评论 (0)
发表评论