系列文章目錄

路徑規劃之Dijkstra算法
路徑規劃之Best-First Search算法

---

---

前言

Best-First Search算法和Dijkstra算法類似，都屬于BFS的擴展或改進

一、Best-First Search算法

1.1 起源

Best-First Search算法又稱最佳優先搜索算法，屬于BFS的擴展，最開始人們也嘗試過使用DFS來實現路徑規劃，效果圖如下

上圖中可以看出，在實際情況中DFS處于不撞南墻不回頭的狀態，它找到的路徑并不是機器人運行的最優路徑；相比之下BFS雖然耗費時間長，代價大，但是可以找到機器人運行的最優路徑。

雖然BFS能有效找到最優路徑，但是它耗費的代價過大，時間過長，于是在BFS的基礎上提出了最佳優先搜索（Best-First Search）。
Best-First Search和Dijkstra不同的地方在于每次選擇新的遍歷節點時，Dijkstra選擇離起點代價最小的點，而Best-First Search選擇離終點代價最小的節點。

1.2 過程

1. 初始化一個優先隊列用于存儲已遍歷但未找到離終點最短路徑的結點，隊列開始只有起點；
2. 遍歷當前節點相鄰的結點，將它們加入優先隊列中，選擇其中到終點代價最小的結點作為下一次遍歷的結點（該結點從優先隊列中踢出，成為已擴展的結點）；
3. 如果相鄰的結點中已存在優先隊列中，更新它到終點的代價；否則加入優先隊列；
4. 重復2、3步驟直至到達終點。

該算法到終點的代價可以使用歐氏距離或者曼哈頓距離來計算，如圖所示

三、簡單使用

以下就是Best-First Search算法在一個比較簡單的地圖中進行路徑規劃的過程，但該算法在應用中非常容易陷入局部最優解，使用頻率遠低于Dijkstra算法