A* 寻路
回溯与搜索 · 启发式搜索 · f = g + h
给搜索装上方向感
同一张网格找最短路：迷宫 DFS 一条道走到黑再回头，BFS 则像水一样不认方向地洪泛——终点在东边，它也先把西边淹一遍。A* 的改进只有一行：给每个格子打分 f = g + h——g 是起点到此的实际步数，h 是到终点的估计距离（网格用曼哈顿距离）——每次从候选（open 集）里扩展 f 最小的格子。
看它怎么「省」
下面 S 到 🚩 之间隔着一道 L 形墙。每格数字是它的 f 值：A* 先沿 f=6 的格子直奔终点，撞墙后 f 抬到 8、自动改道下侧绕行——全程只扩展 10 个格子（浅蓝 = closed），而 BFS 要淹掉全部 22 个可达格。终局沿 parent 指针回溯，8 步最优路径整条点亮。右侧代码随每一步同步高亮。
6
🚩
找 S 到 🚩 的最短路。BFS 不认方向地洪泛，A* 给每格打分 f = g + h：g 是起点到此的实际步数，h 是到终点的曼哈顿估计——每次扩展 f 最小的格子，朝终点「有方向感」地推进
1function astar(grid: Grid, s: Cell, t: Cell): Cell[] {
2 const open = new MinHeap<Cell>(); // 按 f = g + h
3 g.set(s, 0); open.push(s, h(s));
4 while (!open.empty()) {
5 const cur = open.pop(); // 弹出 f 最小
6 if (cur === t) break; // 终点出队 → 已最优
7 for (const nb of neighbors(cur)) { // 四方向邻居
8 const ng = g.get(cur) + 1;
9 if (ng < (g.get(nb) ?? Infinity)) { // 松弛
10 g.set(nb, ng); parent.set(nb, cur);
11 open.push(nb, ng + h(nb)); // f = g + h 入队
12 }
13 }
14 }
15 return tracePath(parent, t); // 沿 parent 回溯
16}
规则f = g + h（h = 曼哈顿距离）
open{ (1, 0) f=6 }
已扩展0
1 / 13
为什么最优，何时会退化
可采纳：h 从不高估真实剩余距离 ⟹ 终点出队那一刻 g 已是最短（曼哈顿在 4 向网格恰好可采纳）。
三兄弟：h ≡ 0 时 A* 退化成 Dijkstra；只用 h 不看 g 是贪婪最佳优先（快但不保证最优）。
退化：h 越接近真实距离越省；h 信息量为零时与 Dijkstra/BFS 同量级。
变体：IDA*（迭代加深省内存）、JPS（网格跳点加速）、双向 A*。
三兄弟：h ≡ 0 时 A* 退化成 Dijkstra；只用 h 不看 g 是贪婪最佳优先（快但不保证最优）。
退化：h 越接近真实距离越省；h 信息量为零时与 Dijkstra/BFS 同量级。
变体：IDA*（迭代加深省内存）、JPS（网格跳点加速）、双向 A*。
游戏单位寻路、地图导航、机器人运动规划，跑的都是 A* 家族。它也把本大类的故事说完整了：盲目搜索（DFS 回溯、BFS 洪泛）在没有先验时兜底，启发式搜索拿一点点关于目标的知识，换来数量级的加速。