作者：zjyspeed ?|?

A*算法

學(xué)習(xí)知識(shí)，有一個(gè)由淺入深的過(guò)程．研究圖搜索算法，離不開深度優(yōu)先搜索 (Depth First Search, DFS) 和廣度優(yōu)先搜索 (Breadth First Search, BFS),?大部分算法都是由最基礎(chǔ)的算法演變而來(lái)的．A* 算法的基石，就是廣度優(yōu)先搜索 (BFS)。

本部分將從 BFS 開始介紹，看看算法是如何一步步進(jìn)化到 A* 的。

廣度優(yōu)先搜索(BFS)

廣度優(yōu)先搜索，是算法里老生長(zhǎng)談的話題了．無(wú)論是在數(shù)據(jù)結(jié)構(gòu)面試題還是科研中，都具有舉足輕重的地位。

所謂廣度優(yōu)先，也就是優(yōu)先搜索距源點(diǎn)距離較近的點(diǎn)，如上圖所示，廣度優(yōu)先的視覺效果為以源點(diǎn)為中心的擴(kuò)散搜索．代碼如下：

?frontier表示當(dāng)前的搜索邊界，也可以理解為用于下一步搜索的備用節(jié)點(diǎn)集合(如 gif 中的藍(lán)色方格)，在編程中通常用優(yōu)先級(jí)隊(duì)列來(lái)表示

?came_from記載了從起點(diǎn)到當(dāng)前點(diǎn)的途徑信息，回溯 came_from, 可以得到從起點(diǎn)到當(dāng)前點(diǎn)的路徑

?while循環(huán)非常重要，這個(gè)循環(huán)框架是整個(gè) A* 部分圖搜索算法的核心部分，大致分為如下幾步

按照既定規(guī)則，在當(dāng)前的搜索邊界frontier中選取一個(gè)方格current作為下一步的搜索點(diǎn)(這個(gè)既定規(guī)則，就是區(qū)分 BFS, Dijkstra, A* …等等算法的關(guān)鍵所在)，在 BFS 中的規(guī)則是廣度優(yōu)先，而frontier邊界中的點(diǎn)本來(lái)就是按遍歷順序排列的，直接選取隊(duì)列首元素

為了擴(kuò)展方便，我們把這個(gè)既定規(guī)則，數(shù)學(xué)化表示成代價(jià)函數(shù) f(n)，算法每次都會(huì)選取隊(duì)列中f(n) 最小的進(jìn)行下一步擴(kuò)展，廣度優(yōu)先搜索的代價(jià)函數(shù)f(n) 其實(shí)就是節(jié)點(diǎn)加入隊(duì)列的順序，那么就不需要進(jìn)行優(yōu)先級(jí)比較了，隊(duì)列本來(lái)就是先入先出的。

擴(kuò)展current，得到current的相鄰節(jié)點(diǎn)集合?neighbors, 放入備用節(jié)點(diǎn)集合frontier

Dijkstra

算法的研究，最終是要為應(yīng)用服務(wù)的．在廣度優(yōu)先算法中，我們以當(dāng)前點(diǎn)距起點(diǎn)的距離作為遍歷的優(yōu)先級(jí)．這樣的遍歷順序在普通場(chǎng)景下尚可，但在某些復(fù)雜場(chǎng)景下卻顯得力不從心，例如過(guò)橋和過(guò)河，對(duì)我們來(lái)說(shuō)同樣的距離，過(guò)橋顯然輕松的多．為此，算法將引入代價(jià)?cost 作為新的代價(jià)函數(shù)f(n)=cost：

定義?cost: 從當(dāng)前點(diǎn)?current?到起點(diǎn)的路徑所需要的代價(jià) (根據(jù) cost 定義的不同，又可以誕生其他的算法，比如下文將要介紹到的?Greedy Best First Search?和 A*)

每次選取代價(jià)最小的節(jié)點(diǎn)優(yōu)先遍歷

代碼如下：

相比于 BFS，Dijkstra 算法新增了cost_so_far用于記錄從當(dāng)前點(diǎn)current到起點(diǎn)的路徑所需要的代價(jià)，并將搜索規(guī)則改為優(yōu)先搜索cost最小的點(diǎn)．如下圖所示，，Dijkstra 算法會(huì)繞過(guò)中央難走的草地．

最佳優(yōu)先搜索 Greedy Best First Search

在 BFS 和 Dijkstra 算法中，算法從起點(diǎn)開始向所有方向擴(kuò)散遍歷，直到最外層的擴(kuò)散圈覆蓋目標(biāo)點(diǎn). 這樣的搜索會(huì)同時(shí)計(jì)算出從起點(diǎn)到包括目標(biāo)點(diǎn)在內(nèi)的的大量點(diǎn)的最優(yōu)路徑. 我們不禁思考這樣的搜索有沒有必要.

舉個(gè)例子，我們想去直線距離10km外的商場(chǎng)，需要找到最近的道路，我們難道會(huì)繞著起點(diǎn)一圈一圈擴(kuò)大搜索直到找到商場(chǎng)嗎？這種搜索方法顯然是有悖常理的，正常人的做法是沿著朝向商場(chǎng)的方向搜索，如果路走不通，才有可能往反方向走來(lái)繞過(guò)障礙.

這樣沿著目標(biāo)點(diǎn)方向的搜索，叫做啟發(fā)式搜索 (Heuristic search)，事實(shí)上，一切利用到目標(biāo)點(diǎn)信息的搜索，都叫啟發(fā)式搜索. 啟發(fā)式搜索算法中，都有一個(gè)啟發(fā)式函數(shù)?(Heuristic function)，最簡(jiǎn)單的啟發(fā)式函數(shù)就是當(dāng)前搜索點(diǎn)current到目標(biāo)點(diǎn)的距離：

前文提到，while循環(huán)框架貫穿 A* 類搜索算法的始終，不一樣的只是確定下一個(gè)搜索點(diǎn)的既定規(guī)則， 也叫代價(jià)函數(shù)，也就是優(yōu)先級(jí)隊(duì)列的比較規(guī)則，回顧一下：

?BFS 的規(guī)則:?順序優(yōu)先f(n)= 加入隊(duì)列的順序(廣度優(yōu)先)

?Dijkstra 的規(guī)則:?到起點(diǎn)的距離優(yōu)先:f(n)=cost_so_far

可以看到，相比于啟發(fā)式搜索，BFS和Dijkstra沒有方向性，相應(yīng)的，這類搜索通常也稱為盲目搜索.

在最佳優(yōu)先搜索 (Greedy Best First Search) 中，?while循環(huán)框架中確定下一個(gè)搜索點(diǎn)的代價(jià)函數(shù)修改為啟發(fā)函數(shù):f(n)=heuristic(n,goal)

如果使用當(dāng)前搜索點(diǎn)current到目標(biāo)點(diǎn)的距離(這里的距離是曼哈頓距離)為啟發(fā)函數(shù)，則最佳優(yōu)先搜索的優(yōu)先級(jí)隊(duì)列比較規(guī)則為到目標(biāo)點(diǎn)的距離優(yōu)先，代碼如下：

相比于 Dijkstra，最佳優(yōu)先搜索直接朝著目標(biāo)點(diǎn)方向行進(jìn)：

當(dāng)然，現(xiàn)實(shí)的情況沒有這么理想，每一條路不可能都是坦途，如果有障礙物怎么辦呢：

可以看到，最佳優(yōu)先搜索仍然朝著目標(biāo)點(diǎn)方向搜索，搜索空間雖然比 Dijkstra 小，但是走了彎路，也就是雖然搜索快，但是找到的路徑不是最短路徑.

那有沒有方法，幫助我們找到又快又短的路徑呢？

A*

受 Dijkstra 和 GBFS(Greedy Best First Search) 的啟發(fā)，A* 決定博采眾長(zhǎng).

?Dijkstra:?到起點(diǎn)的距離優(yōu)先 ：f(n)=cost_so_far

?Greedy Best First Search：到目標(biāo)點(diǎn)的距離優(yōu)先?:f(n)=heuristic(n,goal)

?A*:到起點(diǎn)和目標(biāo)點(diǎn)的距離之和優(yōu)先：f(n)=cost_so_far+heuristic(n,goal)

代碼如下：

可以看到，博采眾長(zhǎng)之后，在上述地圖，與 Dijkstra 相比， A* 算法能找到最短路徑，且搜索空間更??；與 GBFS 相比，A* 算法能找到最短路徑，但搜索空間更大.

到這里，就不得不提到算法最優(yōu)性、完備性和效率之間的折衷了.

最優(yōu)性：指規(guī)劃得到的路徑在某個(gè)評(píng)價(jià)指標(biāo)上是最優(yōu)的，例如經(jīng)常使用的路徑長(zhǎng)度指標(biāo)，最短路徑即是最優(yōu)路徑. 在上述算法中，Dijkstra 是最優(yōu)的， 對(duì)A* 算法來(lái)說(shuō)，只要啟發(fā)函數(shù)沒有低估到目標(biāo)點(diǎn)的距離(稱為啟發(fā)函數(shù)的一致性(admissible))，A* 算法也是最優(yōu)的.

完備性：如果在起點(diǎn)和目標(biāo)點(diǎn)之間有解存在，算法一定能找到解. 在上述算法中，BFS、Dijkstra、A* 都是完備的，在有限狀態(tài)空間圖搜索中，最佳優(yōu)先搜索 GBFS 也是完備的.

算法的效率取決于算法的平均搜索空間，用算法術(shù)語(yǔ)來(lái)說(shuō)叫時(shí)間復(fù)雜度. 這里就不展開介紹了，上面的幾個(gè) gif 展示的搜索過(guò)程，可以直觀的看到各個(gè)算法的搜索空間. 完備性、最優(yōu)性與算法效率往往是矛盾的. 完備、最優(yōu)注定了精益求精，更快的算法通常是次優(yōu)的.?沒有最好的算法，只有最適合的算法.

以下介紹的 A* 變種算法的提出，大都由于最優(yōu)性、完備性和效率之間的折衷。限于篇幅和博主能力，A* 變種算法只簡(jiǎn)要的概括思想，具體內(nèi)容可以閱讀每個(gè)算法給出的參考文獻(xiàn)。

為了便于下文介紹，我們需要對(duì) A* 算法的術(shù)語(yǔ)描述進(jìn)行一些修改：

上文提到，A* 算法的代價(jià)函數(shù)為:f(n)=cost_so_far+heuristic(n,goal) .

在這里需要簡(jiǎn)化一下A* 算法的代價(jià)函數(shù)的表示方法，這也是大部分文獻(xiàn)中所采用的:f(n)=g(n)+h(n)

其中，g(n) 代表著當(dāng)前點(diǎn)n到起點(diǎn)的距離，也就是上文的cost_so_far，h(n) 代表著啟發(fā)函數(shù)heuristic. 這里插一句題外話，規(guī)定h是因?yàn)閔是heuristic的首字母，那么g代表著什么？答案是沒有什么，因?yàn)?A* 算法提出者在文章里就是這么規(guī)定的…

上文提到，frontier?表示當(dāng)前的搜索邊界，也即為用于下一步搜索的備用節(jié)點(diǎn)集合，在一般的編程框架里，frontier通常被稱為open list，一般翻譯過(guò)來(lái)叫Open 表. 相應(yīng)于open list，還有一個(gè)closed list，每次從open list 中取出的優(yōu)先級(jí)最高的節(jié)點(diǎn)current 都會(huì)被放入closed list 中，表示該節(jié)點(diǎn)已經(jīng)被探索過(guò).

這里推薦一個(gè)非常好的網(wǎng)站，里面包括了很多圖搜索算法和采樣搜索算法的可視化搜索過(guò)程和編程實(shí)現(xiàn):?https://github.com/zhm-real/PathPlanning，下文的 gif 示例大部分取自該網(wǎng)站.

Bidirectional A*（雙向A*）

雙向 A* 算法維護(hù)兩套 A* ，最精髓的思想在于從起點(diǎn)和終點(diǎn)分別、同時(shí)向?qū)Ψ剿阉鳎请p向搜索過(guò)程中的處理邏輯有很多需要考慮的地方：例如是輪流搜索還是優(yōu)先搜索起點(diǎn)開始的 A*？

一種可能的搜索過(guò)程如下:

次優(yōu)算法

Weighted A* （WA*）

回顧一下經(jīng)典算法的代價(jià)函數(shù)：

A*:f(n)=g(n)+h(n)

Dijkstra:f(n)=g(n)

GBFS:f(n)=h(n)

Weighted A* 集思廣益，為了滿足用戶各種情景的需求，設(shè)計(jì)了一個(gè)權(quán)重因子 ω

f(n)=g(n)+ω×h(n)

觀察上述代價(jià)函數(shù)，發(fā)現(xiàn)：

?ω=0 時(shí)，Weighted A* 退化為 Dijkstra

?ω=1 時(shí)，Weighted A* 退化為 A*

?ω=∞ 時(shí)，Weighted A* 退化為 GBFS

在有限狀態(tài)空間圖搜索中，上述算法都是完備的，調(diào)整參數(shù)ω便是算法最優(yōu)性與求解速度之間的折衷。

Anytime Repairing A* （ARA*）

參考文獻(xiàn): ARA*: Anytime A* with Provable Bounds on Sub-Optimality（https://proceedings.neurips.cc/paper_files/paper/2003/file/ee8fe9093fbbb687bef15a38facc44d2-Paper.pdf）

ARA* 做了兩件事情:

?快速找到一條可用的路徑

?用剩余時(shí)間對(duì)這條路徑進(jìn)行優(yōu)化

當(dāng)然，這個(gè)邏輯的提出已經(jīng)不是什么新鮮事情了，ARA* 的精髓在于 用剩余時(shí)間對(duì)這條路徑進(jìn)行優(yōu)化 這件事情是如何復(fù)用優(yōu)化前的搜索路徑結(jié)果、大大降低計(jì)算量的。具體可以參考論文。

Focal Search （A ??）

參考文獻(xiàn)：Studies in Semi-Admissible Heuristics（https://ieeexplore.ieee.org/document/4767270）

這篇論文介紹了三種次優(yōu)算法，這里簡(jiǎn)要介紹其中最著名的 FOCAL Search，也叫A ??，這是一種有界次優(yōu)算法。

?

動(dòng)態(tài)搜索

動(dòng)態(tài)搜索(Dynamic search)，也叫增量搜索(Incremental search)和長(zhǎng)期規(guī)劃(Lifelong search)，可以在環(huán)境地圖改變時(shí)，基于先前路徑快速搜索出新的規(guī)劃路徑，而無(wú)需從頭開始搜索。

Lifelong Planning A* (LPA*)

參考文獻(xiàn): Lifelong Planning A*（https://www.cs.cmu.edu/~maxim/files/aij04.pdf）

論文講解: 終身規(guī)劃A* 算法（LPA*）：Lifelong Planning A*（https://blog.csdn.net/lqzdreamer/article/details/85175372）

Dynamic A* (D*)

參考文獻(xiàn)：Optimal and Efficient Path Planning for Partially-Known Environments（http://web.mit.edu/16.412j/www/html/papers/original_dstar_icra94.pdf）

論文講解：D*路徑搜索算法原理解析及Python實(shí)現(xiàn)（https://blog.csdn.net/lqzdreamer/article/details/85055569）

D* Lite

D* Lite 基于 Lifelong Planning A*.

參考文獻(xiàn)：D* Lite（http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf）

論文講解：D* Lite路徑規(guī)劃算法（https://blog.csdn.net/lqzdreamer/article/details/85108310?spm=1001.2101.3001.6650.17&utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-17.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~Rate-17.pc_relevant_default&utm_relevant_index=21）

結(jié)語(yǔ)

限于筆者精力和能力，后半部分沒有講述的算法導(dǎo)向了一些熱門講解文章，大家可以參考。如果英語(yǔ)能力足夠，還是建議大家直接看原網(wǎng)站和論文，翻譯和表達(dá)總會(huì)有一些不盡如人意的地方。

編輯：黃飛

?