如何在带权网格上实现 A*？

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. 参考实现

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_PATH

reconstruct 从终点沿 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 风格公式；公式必须对应合法移动组合并保持下界性质。

搜索期间网格发生变化怎么办？

在带版本的快照上搜索，并在使用前校验路径；或者检测版本变化后重启。混用不同版本的代价会破坏最优性和安全性。