本文轉(zhuǎn)自雷鋒網(wǎng)，如需轉(zhuǎn)載請至雷鋒網(wǎng)官網(wǎng)申請授權(quán)。

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

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

算法的一般性原理如下：

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

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

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

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

BFS

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

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

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

Dijkstra

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

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

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

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

A*

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

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

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

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

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

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

算法實現(xiàn)

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

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

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

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

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