BFS 不管方向、往四面八方均匀扩展——A* 多了一个"感觉离终点还有多远"的估计，优先朝着这个方向探索，能少走很多冤枉路。
14.1 节的 BFS 像一圈圈扩散的水波——不管终点在哪个方向，它都会均匀地往四面八方探索，一层一层扩大范围，直到扩散到终点为止。如果终点其实就在正前方不远处，BFS 依然会把"背对终点"的方向也探索个遍，才轮到终点所在的方向——这些背离终点方向的探索，其实是白费的。
A* 算法在 BFS（严格说是 Dijkstra，见 ⑥）的基础上，多引入了一条信息：每个位置"大概"离终点还有多远（不要求精确，只要是一个合理的估计）。有了这条信息，搜索就能优先朝着"感觉更接近终点"的方向扩展，像手里多了一个指南针，不再是无差别地往四周探索。
A* 给每个待探索的节点算一个分数 f(n)，由两部分相加组成：
| 符号 | 含义 |
|---|---|
| g(n) | 从起点实际走到 n 已经花费的代价（这部分是精确值，不是估计） |
| h(n) | 从 n 估计还要多少代价才能到达终点（启发式函数，Heuristic） |
| f(n) = g(n) + h(n) | "如果经过 n"，从起点到终点的总代价估计 |
A* 用一个优先队列（小顶堆）代替 BFS 的普通队列，每次弹出 f(n) 最小的节点来扩展——也就是"当前看起来最有希望、总代价最小"的那个节点优先探索，而不是像 BFS 那样按入队顺序（也就是纯粹按距离远近）挨个处理。
在网格寻路里，最常用的启发式函数是曼哈顿距离（只能上下左右移动时）：h(n) = |n.x - T.x| + |n.y - T.y|——横纵坐标差的绝对值之和，也就是"不考虑障碍物，直着走过去需要几步"。
启发式函数 h(n) 有一条必须遵守的规则：永远不能高估真实代价（这样的 h 称为"可采纳的"，admissible）。如果 h(n) 估得比实际需要的步数还多，A* 可能会因为"觉得这条路太远"而提前放弃一条其实更优的路径，导致算出的答案不是最短路。曼哈顿距离在只能上下左右移动的网格里，天然满足"不高估"——真实路径可能因为障碍物绕远，但绝不会比直线距离更短。
h(n) 恒为 0，A* 就退化成了普通的 Dijkstra／BFS——没有方向指引，纯粹按已走代价排序。h 估计得越准（同时不高估），A* 能"提前排除"的无关方向就越多，效率提升越明显；估得越不准，效率提升就越有限。在一张 5×7 的空网格上，起点 S 在最左列正中间，终点 T 在最右列正中间，两者相距 4 步（无障碍物）。对比 BFS 和 A*（曼哈顿距离启发）各自访问过的格子：
(col=1, row=2) 为例：g（从 S 走到这里）需要 2 步，h（曼哈顿估计到 T）是 3+1=4，f = 2+4 = 6；而直线上的格子 (col=1, row=3)：g=1，h=3，f=1+3=4。优先队列每次弹出 f 最小的节点，f=4 的这一整行会被优先处理完，等不到 f=6 的格子被拿出来，S 到 T 之间的最短路已经找到了。| 1 | int n, m, er, ec; // 网格大小、终点坐标 |
| 2 | int g[MAXN][MAXN]; // g[r][c]：从起点到 (r,c) 的实际步数，-1 表示未访问 |
| 3 | int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; |
| 4 | |
| 5 | int H(int r, int c) // 曼哈顿距离估价 |
| 6 | { |
| 7 | return abs(r - er) + abs(c - ec); |
| 8 | } |
| 9 | |
| 10 | // 队列里存 (f, r, c)；pair 默认按 f 从小到大比较，用 greater 做小顶堆 |
| 11 | int AStar(int sr, int sc) |
| 12 | { |
| 13 | memset(g, -1, sizeof(g)); |
| 14 | priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq; |
| 15 | g[sr][sc] = 0; |
| 16 | pq.push({H(sr, sc), sr, sc}); // f = g(0) + h |
| 17 | |
| 18 | while (!pq.empty()) |
| 19 | { |
| 20 | auto [f, r, c] = pq.top(); pq.pop(); // ★ 每次取 f 最小的节点 |
| 21 | if (r == er && c == ec) return g[r][c]; // 第一次弹出终点，g 就是最短距离 |
| 22 | if (f > g[r][c] + H(r, c)) continue; // 过时的队列项，跳过（见 ⑦ 陷阱） |
| 23 | |
| 24 | for (int k = 0; k < 4; k++) |
| 25 | { |
| 26 | int nr = r + dx[k], nc = c + dy[k]; |
| 27 | if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue; |
| 28 | int ng = g[r][c] + 1; |
| 29 | if (g[nr][nc] == -1 || ng < g[nr][nc]) // 没访问过，或者找到了更短的路 |
| 30 | { |
| 31 | g[nr][nc] = ng; |
| 32 | pq.push({ng + H(nr, nc), nr, nc}); // f = 新的 g + h |
| 33 | } |
| 34 | } |
| 35 | } |
| 36 | return -1; |
| 37 | } |
f 排序）代替普通队列；每次入队时多加一项 H(nr, nc) 算出 f。除此之外的骨架——记录已走距离、四方向扩展、越界检查——和 14.1 节的 BFS 完全一样。观察 f(n) = g(n) + h(n)：如果把 h(n) 恒定设为 0，A* 的优先队列就完全按 g(n)（实际已走代价）排序——这正是 Dijkstra 算法的做法。再进一步，如果每条边的代价都固定是 1（无权图），按 g(n) 排序又和"先入队的先处理"的普通队列（BFS）等价。可以说，BFS ⊂ Dijkstra ⊂ A*——A* 是在 Dijkstra 的基础上加上了"目标方向感"，Dijkstra 又是 BFS 在带权图上的推广。
h 有时比真实代价小、有时因为四舍五入等问题反而更大。只要 h 存在高估的可能，A* 就不再保证找到最短路——设计启发式函数时，宁可估得保守一些（偏小），也不能有高估的风险。g 并重新入队"，这意味着同一个坐标可能同时有好几条记录躺在优先队列里，其中大部分已经"过时"（后来被更小的 g 覆盖了）。第 22 行 if (f > g[r][c] + H(r,c)) continue; 就是用来识别并跳过这些过时记录的——如果漏掉这一行判断，程序不会出错，但会重复处理很多已经不需要再处理的节点，白白浪费时间。h 函数可能不再满足"不高估"，需要重新设计（比如允许斜走时改用切比雪夫距离）。f 值"，用 DFS 的低内存开销实现和 A* 一样的启发式剪枝效果。