1. 题目
实现 aStar(grid, start, goal)。网格单元要么阻塞，要么有正的通行代价；只允许四方向移动，进入邻居时加上邻居代价。返回路径和总成本；终点不可达时返回 NO_PATH。
2. 约束与澄清
- 坐标是网格内的整数
(row, column)；起点和终点都必须可通行。 - 如果要求最优解，启发式不能高估剩余成本。四方向移动且最小单元代价为
m时，曼哈顿距离乘m是可采纳的。 - 使用按
f排序、再按坐标稳定排序的最小堆。发现更小的g后，堆里可能保留旧项。 - 单元代价不能为负。单线程实现足够；并发修改网格时需要快照或版本校验。
3. 核心思路
用 gScore 保存到每个单元的已知最低成本，用 cameFrom 回溯路径。每次松弛降低 gScore 就压入 (f, g, cell)。弹出时若记录中的 g 大于当前 gScore，说明过期，直接跳过；这样无需实现任意位置的 decrease-key。
启发式一致时，终点第一次以非过期记录弹出即可确定最优。只有可采纳但不一致时，发现更低 g 仍应允许重新打开已处理单元。Red Blob Games 的实现说明了这种优先队列模式，以及启发式质量如何影响搜索量。
4. 参考实现
text
aStar(grid, start, goal):
要求 start、goal 可通行
gScore = map(default=INFINITY); cameFrom = map()
gScore[start] = 0
open = minHeap((heuristic(start, goal), 0, start))
while open 非空:
(f, queuedG, current) = open.pop()
if queuedG != gScore[current]: continue // 过期项
if current == goal: return reconstruct(cameFrom, goal), gScore[goal]
for next in current 的可通行邻居:
tentative = gScore[current] + grid[next].cost
if tentative < gScore[next]:
gScore[next] = tentative; cameFrom[next] = current
open.push((tentative + h(next, goal), tentative, next))
return NO_PATHreconstruct 从终点沿 cameFrom 走回起点，再反转单元列表。优先队列只负责安排候选，gScore 才是事实来源。
5. 复杂度与取舍
可达单元数为 V、邻接边数为 E 时，惰性堆实现的时间复杂度为 O((V + E) log V)，空间复杂度为 O(V)。四邻居网格中 E 为 O(V)。更强且一致的启发式通常能减少展开单元，但不改变最坏界。支持 decrease-key 的堆可减少重复项，却增加实现复杂度。
6. 验证与可观测性
- 覆盖起点等于终点、端点阻塞、空网格、带缺口的墙、加权绕行和终点不可达。
- 在随机非负网格上用
h=0的 Dijkstra 对比返回成本。 - 断言路径每一步相邻且可通行，并独立重算路径成本。
- 记录展开数、过期弹出数、堆峰值和启发式违规数；过期项暴增通常表示重复调度或边界设计有问题。
7. 常见错误
- 首次发现节点就永久关闭，而不是在有效弹出时处理。
- 四方向单位移动直接使用未缩放的欧氏距离，导致启发式不可采纳。
- 加上当前单元代价，而不是进入邻居的代价。
- 终点从过期堆记录弹出时仍返回路径。
- 忘记处理
start == goal或允许阻塞端点。
8. 追问
什么时候曼哈顿距离可采纳？
四方向、非负成本且最小通行代价为 m 时，每个必需的水平或垂直步至少花费 m；曼哈顿距离乘 m 不会超过真实剩余成本。
允许对角线后如何调整启发式？
使用符合直走和斜走成本的八方向下界，例如 octile 或 Chebyshev 风格公式；公式必须对应合法移动组合并保持下界性质。
搜索期间网格发生变化怎么办？
在带版本的快照上搜索，并在使用前校验路径；或者检测版本变化后重启。混用不同版本的代价会破坏最优性和安全性。