A* 尋路

你用手機導航從家裡走到某間店，它得在滿是巷子、單行道和死路的地圖上挑出一條最短的路。最笨的做法是四面八方每條巷子都試一遍，很慢；A* 聰明在它會「朝目標的方向」優先探路——就像你雖然不知道確切路線，但知道店在東邊，就先往東走，少繞很多冤枉路。它靠一個直覺取捨：已經走過的路愈短、看起來離終點愈近的方向，愈值得先試。下面你會看到它怎麼一步步在格點上朝終點擴張、繞開牆找出最短路。

A* 是格點 / 地圖上的啟發式最短路徑搜尋：每個節點的評分 f(n) = g(n) + h(n)， g(n) 是從起點走到 n 的實際步數，h(n) 是 n 到終點的估計距離（此處用曼哈頓距離）。 每次從 open set 取出 f 最小的節點展開，直到抵達終點或 open 耗盡（無解）。 比起沒有方向性的 Dijkstra/BFS，A* 會優先朝終點方向擴張，通常更快收斂。