譯者：AI研習(xí)社（季一帆）

雙語原文鏈接：Interactive pathfinding

---

點(diǎn)此鏈接進(jìn)入交互演示頁面：https://interactive-pathfinding.netlify.com/

廣度優(yōu)先搜索、Dijkstra和A*是圖上的三種典型路徑規(guī)劃算法。它們都可用于圖搜索，不同之處在于隊列和啟發(fā)式函數(shù)兩個參數(shù)。

本項(xiàng)目探索并可視化不同算法如何根據(jù)選擇參數(shù)進(jìn)行圖搜索。

算法的一般性原理如下：

將邊界初始化為包含起始節(jié)點(diǎn)的隊列。

當(dāng)邊界隊列不為空時，從隊列中“訪問”并刪除一個“當(dāng)前”節(jié)點(diǎn)，同時將訪問節(jié)點(diǎn)的每個鄰居節(jié)點(diǎn)添加到隊列，其成本是到達(dá)當(dāng)前節(jié)點(diǎn)的成本加上從當(dāng)前節(jié)點(diǎn)訪問鄰居的成本再加上鄰居節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的啟發(fā)式函數(shù)值。其中，啟發(fā)式函數(shù)是對兩個節(jié)點(diǎn)的路徑成本的估計。

存儲訪問路徑（通常存儲在cameFrom圖中），以便后續(xù)重建路徑。如果鄰居節(jié)點(diǎn)已經(jīng)在列表中，同時新路徑的成本較低，那么更改其成本。

找到目標(biāo)路徑（提前退出）或列表為空時，停止算法。

BFS

使用先進(jìn)先出隊列實(shí)現(xiàn)BFS。這種隊列會忽略路徑中鏈接的開銷，并根據(jù)跳數(shù)進(jìn)行擴(kuò)展，因此可以確保找到最短路徑的跳數(shù)，而跳數(shù)相關(guān)的成本。啟發(fā)式函數(shù)的選擇是任意的，因?yàn)樵谶@個過程中其并不起作用。

使用數(shù)組可實(shí)現(xiàn)先進(jìn)先出，即將元素附加到末尾并從頭刪除。

BFS演示動圖。注意邊界節(jié)點(diǎn)（黃色）是如何在網(wǎng)格中擴(kuò)展為正方形的。在這里，正方形是相同“跳距”的節(jié)點(diǎn)集。

Dijkstra

在圖上使用優(yōu)先級隊列和始終返回0的啟發(fā)式函數(shù)，便得到Dijkstra算法。

相比于BFS，Dijkstra最大的不同在于考慮了成本。通過該算法，可以根據(jù)節(jié)點(diǎn)到節(jié)點(diǎn)的成本找到最短路徑。

優(yōu)先級隊列使用數(shù)組實(shí)現(xiàn)，在每次插入新節(jié)點(diǎn)后對該數(shù)組進(jìn)行排序。盡管實(shí)現(xiàn)優(yōu)先級隊列還有其他更高效的方式，但在我們的場景中，數(shù)組是足夠快的，而且實(shí)現(xiàn)起來也簡單。

Dijkstra展示動畫，注意此時的邊界是一個圓。

A*

為實(shí)現(xiàn)A*算法，需要傳遞一個實(shí)際啟發(fā)式函數(shù)，例如兩個節(jié)點(diǎn)之間的歐式距離。通過“節(jié)點(diǎn)成本”+“節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估算成本”對節(jié)點(diǎn)進(jìn)行加權(quán)，通過優(yōu)先搜索更大可能的節(jié)點(diǎn)加快搜索速度。

借助啟發(fā)式方法，A*可以比Dijkstra或BFS更快地找到正確路徑。

非允許的啟發(fā)式函數(shù)

只有應(yīng)用可允許啟發(fā)式函數(shù)，A*才能找到最短路徑，這也意味著算法永遠(yuǎn)不會高估實(shí)際路徑長度。由于歐氏距離是兩點(diǎn)之間的最短距離/路徑，因此歐氏距離絕不會超出。

但如果將其乘以常數(shù)k>0會怎樣呢？這樣會高估距離，成為非允許的啟發(fā)式函數(shù)。

k值越大，算法越容易到達(dá)目標(biāo)，但同時準(zhǔn)確性降低，導(dǎo)致生成的路徑并非總是最短的。

算法實(shí)現(xiàn)

本項(xiàng)目通過Javascript實(shí)現(xiàn)，以便讀者在Web上進(jìn)行訪問。另外，我使用react渲染UI，使用react-konva渲染圖形。

路徑發(fā)現(xiàn)是指接受隊列類型和啟發(fā)式函數(shù)，并返回另一個函數(shù)，即真實(shí)路徑發(fā)現(xiàn)（稱為currying）。

這樣，用戶每次更改設(shè)置后，都會使用確定參數(shù)創(chuàng)建一個新的路徑發(fā)現(xiàn)函數(shù)，并將之用于圖搜索。

為可視化路徑發(fā)現(xiàn)的步驟，我使用javascript生成器，這意味著函數(shù)返回一個迭代器，而不僅僅是一個值。因此，訪客在每一步都可以生成算法的整個狀態(tài)，并將其保存到數(shù)組，然后通過頁面頂部的滑塊顯示特定狀態(tài)。

---

AI研習(xí)社是AI學(xué)術(shù)青年和AI開發(fā)者技術(shù)交流的在線社區(qū)。我們與高校、學(xué)術(shù)機(jī)構(gòu)和產(chǎn)業(yè)界合作，通過提供學(xué)習(xí)、實(shí)戰(zhàn)和求職服務(wù)，為AI學(xué)術(shù)青年和開發(fā)者的交流互助和職業(yè)發(fā)展打造一站式平臺，致力成為中國最大的科技創(chuàng)新人才聚集地。

如果，你也是位熱愛分享的AI愛好者。歡迎與譯站一起，學(xué)習(xí)新知，分享成長。

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。