Dijkstra 加上「方向感」。多算一個「猜還要多遠」,就能朝終點直奔、少走很多冤枉路。
g(n) —— 已經走的:從起點到 n 實際花的成本(跟 Dijkstra 的 dist 一樣)。
h(n) —— 猜還要走的:從 n 到終點的估計距離(啟發函數,例如格子上的曼哈頓距離)。
f(n) = g(n) + h(n) —— 估計總長:走這條路、經過 n,「大概」總共要多長。
優先佇列挑 f 最小的 —— 跟 Dijkstra 幾乎一模一樣,只是排序的鑰匙從 g 換成 f = g + h。h 恆為 0 就退化回 Dijkstra;h 猜得越準,越像一條直線衝向終點。
可採納(admissible):h 永遠不高估 —— 只要 h(n) ≤ 從 n 到終點的真實最短距離,A* 就保證找到最短路。曼哈頓距離對「只能上下左右」的格子就永遠不高估(直線最少要走這麼多步)。
一致(consistent):h 沿邊變化不會太猛 —— 更強的條件,滿足時「節點一出佇列就定案」,不用回頭重算,效率最好。
高估會怎樣? —— h 灌太大,A* 會更快(更貪心地衝),但可能回傳比最短長的路 —— 失去最短保證。要不要用,看你能不能接受「快但不一定最短」。
選跟移動方式匹配的 h —— 只能上下左右用曼哈頓;可以斜走用切比雪夫;連續空間用直線(歐幾里得)距離。挑錯會高估或低估。
h 好的時候,實際展開的節點少非常多。g / 前驅,節點級。h 少探很多沒必要的節點」。h 越接近真實剩餘距離,越快;h=0 時就完全退回 Dijkstra。Dijkstra 沒方向感,東南西北都探;A* 知道「終點在東邊」,就先往東找,少走冤枉路。
h 就像「離終點越近越熱」的提示,A* 專挑熱的方向挖,不往冷的地方浪費力氣。
RTS、RPG 裡的單位點一下就自己繞過障礙走到目的地,底層幾乎都是 A*。
從 S 走到 G,中間一小塊牆。每一步挑邊界(琥珀)裡 f = g + h 最小的格子展開(格子裡的數字就是 f),綠色是已定案、紫圈是這步正在展開的。看它怎麼幾乎直奔 G、繞過牆又貼回來,不往反方向亂逛。按「下一步」。
從格子 A* 基本版、三種啟發函數、還原路徑、h=0 退化成 Dijkstra,到加權 A*、圖版、八方向、可採納性、地形成本,最後一張尋路挑工具表。
❌ 用了會高估的 h —— 例如能斜走卻用曼哈頓距離(會高估)。A* 可能回傳非最短的路。要最短,就用不高估的 h。
❌ 沒記 closed / 沒擋重複展開 —— 同一個點被重複挑出來處理,效率崩壞。出佇列時檢查是否已定案就好(或用「過期跳過」那招)。
❌ h 配錯移動方式 —— 只能上下左右卻用直線距離會低估(變慢、退化成 Dijkstra);能斜走卻用曼哈頓會高估(失去最短)。h 要跟著移動規則選。
❌ 以為 A* 一定比 Dijkstra 快 —— h 很爛(≈0)時它就是 Dijkstra;h 亂高估則可能不最短。A* 的好壞全看 h。
h 改成「永遠回傳 0」,A* 會變成哪一個演算法?為什麼?把答案打到對話裡,我幫你對。