如何在加權網格上實作 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 風格公式；公式必須對應合法移動組合並保持下界性質。

搜尋期間網格改變怎麼辦？

在帶版本的快照上搜尋，並在使用前檢查路徑；或偵測版本變化後重啟。混用不同版本的成本會破壞最佳性與安全性。