演算法知識 - A* 搜尋

2021-01-07

字數統計： 226 | 閱讀時間≈ 1分鐘

A* 介紹

A* 搜尋演算法，(A* 讀做 Astar)，在圖形平面上對對多個節點路徑求出最低成本的演算法，是將 BDS 與遍地圖(Graph Travel )的改進演算法。

主體還是以 BFS 為主，但多增加一個函式，啟發式搜尋(heuristic)找出最高的權重在使其進行 BFS，找出最高的權重為 \(f(x) = g(x) + h(x) \)，其中 \(g(x)\) 則是從起點走到當前節點的距離，\(h(x)\) 則是啟發式搜尋，用於猜測當前節點至終點的距離。

在搜尋演算法中作為效率提升的一個手段，對於當前已知的資訊或結點進行評判，並對資訊進行評分，透過評分方式來使搜尋演算法找到最優的搜尋方向。