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 風格公式；公式必須對應合法移動組合並保持下界性質。
搜尋期間網格改變怎麼辦？
在帶版本的快照上搜尋，並在使用前檢查路徑；或偵測版本變化後重啟。混用不同版本的成本會破壞最佳性與安全性。