A* 寻路
A* 用 f(n) = g(n) + h(n) 排列待搜索节点：g 是已经支付的路径成本，h 是剩余成本的估计。在本课不重新打开已关闭节点的实现中，使用一致启发式可保证最优路径，通常比 Dijkstra 扩展更少的格子。
g 记录实际走过的成本，h 提供目标方向。只看 h 的贪心搜索可能选中昂贵路线；令 h = 0，A* 就变成 Dijkstra。地图、游戏、机器人网格和路线规划常能提供便宜的距离下界，因此适合 A*。
启发式过重预设使用 h = 4 × 曼哈顿距离。它高估余下成本，在便宜绕路尚未探索时就弹出目标，返回非最优路径。这说明启发式条件决定了保证是否成立。
A* 寻路如何工作
算法维护三项状态：g[cell] 保存从起点到此格目前找到的最低成本；came_from[cell] 保存产生该成本的父格；开放集是按 f = g + h 排序的优先队列。
每轮弹出最小 f 的条目。若该格已关闭，丢弃过期条目；若是目标，结束并重建路径；否则关闭该格并检查可通行邻居。计算 tentative_g = g[cur] + move_cost，若低于邻居旧 g，就更新父格、g、f，并把新条目压入开放集。
本实现不重新打开已关闭格，因此需要一致性：每条边满足 h(u) <= cost(u, v) + h(v)，且 h(goal) = 0。一致性蕴含可采纳性，即不高估真实剩余成本；只有可采纳但不一致时，算法可能需要重新打开节点，不能套用当前实现的保证。
在一致启发式下，目标第一次被弹出时成本已最优：它具有开放集最小 f，未完成路线的下界不会带来更低的目标成本。本课正常网格中的曼哈顿距离满足这个条件。
A* 寻路逐步演示
默认迷宫有 4 行、7 列，起点为 r1c0，目标为 r1c6。第 3 列的第 0、1、2 行是墙，只能从底部缺口通过，再向上到目标。
下面沿最终路径说明步骤，实际搜索还会扩展其他候选。25 个可通行格中，A* 关闭 15 格，同一迷宫中的 Dijkstra 关闭 23 格。
- 初始化
g[r1c0] = 0。曼哈顿距离为 6，所以f = 0 + 6 = 6。 - 弹出并关闭
r1c0。右邻居r1c1得到g=1, h=5, f=6。上下邻居也进入开放集，但偏离目标所在行，所以f更大。 - 依次弹出
r1c1、r1c2。直线上的格子仍为f=6，但r1c2右侧是墙，无法进入第 3 列。 - 路线向下经过
r2c2、r3c2，从r3c3穿过缺口，到达r3c4。每次成功松弛都写入父指针和g/h/f。 - 从
r3c4经r2c4、r1c4、r1c5到达r1c6。起点后进入十个格子，成本为 10。 - 弹出目标时，没有开放条目的
f更低。依据一致的曼哈顿启发式，算法停止。重建路径为r1c0 -> r1c1 -> r1c2 -> r2c2 -> r3c2 -> r3c3 -> r3c4 -> r2c4 -> r1c4 -> r1c5 -> r1c6。
切换到启发式过重预设，算法返回顶行直路，成本为 13，而底部绕路只需 6。放大的启发式使算法过早信任目标。最终对比中的红色数字是停止前实际记录的成本，绿色 opt 数字是参考最优路径上的真实累计成本。
A* 与 Dijkstra 的搜索量
默认迷宫中两者路径成本都是 10，但 A* 关闭 15/25 格，Dijkstra 关闭 23/25 格。启发式改变优先级，没有改善最坏渐近复杂度。曼哈顿距离引导搜索靠近目标，g 仍累计绕墙的真实成本；Dijkstra 只按已付成本向外扩展。
时间与空间复杂度
| 实现 | 时间 | 空间 |
|---|---|---|
| 二叉堆上的网格或图搜索 | O((V + E) log V) | O(V + E) |
V 为格子或顶点数，E 为边数。四邻居网格中 E 至多约为 4V，因此常写为 O(V log V)。开放集插入、取最小值和边松弛与 Dijkstra 相同，懒删除堆会保留过期条目，所以空间包含 E。
有便宜且一致的启发式时可用本实现；没有合适估计时用 Dijkstra。若更改为允许重新打开节点的版本，应重新分析对应的条件和搜索成本。
边界情况
h=0有效，等价于 Dijkstra，仍最优但没有目标方向提示。- 开放集为空且尚未弹出目标，说明不可达。全部预设都有路径，但代码会为无路情况返回
(None, INF)。 f相同先比较较小h，再比较行、列，保证回放顺序固定。- 加权地形的实际移动成本要加进
g。启发式仍需提供满足条件的剩余成本估计。 h高估时，弹出目标不再证明最优，过重预设就是反例。- 绕路预设中，同一个格子先以成本 4 入队，再被改进为 2。旧条目稍后弹出时被跳过，这就是懒删除。
常见错误
- 只按
h排序，变成贪心最佳优先搜索。A* 比较g + h，更靠近目标也可能因为已付成本太高而落后。 - 忽略启发式条件。当前不重新打开节点的代码需要一致性，放大曼哈顿距离会破坏证明。
- 入队就关闭格子。弹出前仍可能找到更便宜的路线，应在弹出时关闭。
- 忘记过期堆条目。普通二叉堆的懒更新实现会新增条目，并在旧条目弹出时丢弃。
- 把画布距离当成本。算法累加网格或图里的移动成本，屏幕布局只是状态的展示。
展示中的简化
开放集画成完全排序的条带，便于观察优先级。真实二叉堆只保证下一次弹出最小条目，其余元素并未完全排序。网格只允许四方向移动，使用固定预设和小整数成本；本课不包含对角移动、动态障碍、路径平滑或游戏专用的平局规则。