基于路徑優(yōu)化的A*算法與Dijkstra算法的性能比較

劉云翔+杜杰+張晴

摘 要： 路徑優(yōu)化成為解決道路擁擠和阻塞的重要途徑。傳統(tǒng)單源最短路徑的Dijkstra算法可以找到從起始點(diǎn)到其他點(diǎn)的最短路徑信息，在地圖障礙物較多的情況下，其搜索時(shí)間較長。人工智能領(lǐng)域帶啟發(fā)式函數(shù)的A*算法由于本身就具有記憶性的功能，在路網(wǎng)中可以自主性的選擇最優(yōu)路徑，并且隨著障礙物信息和地理位置信息的增多，其搜索效率更高。通過實(shí)驗(yàn)將A*算法與傳統(tǒng)的Dijkstra算法進(jìn)行仿真比較，對比它們的搜索速度和搜索效率，結(jié)果證明在實(shí)際路網(wǎng)中A*算法的搜索效果更明顯。

關(guān)鍵詞： 最短路徑； A*算法； Dijkstra算法； 路徑優(yōu)化

中圖分類號： TN911.1?34； TP312 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）13?0181?03

Abstract： The path optimization is an important way to solve the traffic congestion and blocking. The traditional Dijkstra algorithm based on monophyletic shortest path can find the shortest path information from the starting point to other points， but its search time is long in the situation of various map obstacles. The A* algorithm with heuristic function in the field of artificial intelligence can select the optimum path by itself because of its memory function. With the increase of obstacle information and location information， the search efficiency of A* algorithm becomes higher. The A* algorithm and traditional Dijkstra algorithm were simulated and compared with experiments， and their search speed and search efficiency were compared. The simulation results show that the search effect of A* algorithm is more effective in the actual road network.

Keywords： shortest path； A* algorithm； Dijkstra algorithm； path optimization

最短路徑問題[1]是圖論中網(wǎng)絡(luò)分析的經(jīng)典問題，近年來，隨著路徑搜索技術(shù)的不斷發(fā)展，已經(jīng)涌現(xiàn)出很多成熟的路徑規(guī)劃算法，比如，基于圖論的Dijkstra算法[2?3]，以及關(guān)于人工智能領(lǐng)域的啟發(fā)式搜索算法和動態(tài)規(guī)劃算法等。A*啟發(fā)式搜索算法作為人工智能領(lǐng)域的重要組成部分，其針對網(wǎng)格數(shù)據(jù)有著更高的運(yùn)算效率，而且利用啟發(fā)信息大幅度提高了搜索速度。這種全新的啟發(fā)式搜索算法[4]將會極大地改變現(xiàn)有的交通管理與服務(wù)模式。

1 A*算法原理

傳統(tǒng)的BFS算法的評估函數(shù)只考慮當(dāng)前點(diǎn)與終點(diǎn)的距離，其策略是選擇與終點(diǎn)最近的點(diǎn)進(jìn)行搜索。而Dijkstra算法則只關(guān)注當(dāng)前點(diǎn)與起點(diǎn)的距離，選擇與起點(diǎn)最近的點(diǎn)開始搜索。A*算法[5]則是將二者結(jié)合起來，其啟發(fā)函數(shù)采用如下的計(jì)算公式：

式中：就是A*算法[5]對每個(gè)節(jié)點(diǎn)的評估函數(shù)[2]，其包含兩部分信息：是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)，也就是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動距離；相鄰的兩個(gè)點(diǎn)的移動距離是1，當(dāng)前點(diǎn)距離起點(diǎn)越遠(yuǎn)，這個(gè)值就越大。是從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的距離評估值，這是一個(gè)從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的移動距離的估計(jì)值。

A*算法的搜索過程需要兩個(gè)表：一個(gè)是OPEN表，存放當(dāng)前已經(jīng)被發(fā)現(xiàn)但是還沒有搜索過的節(jié)點(diǎn)；另一個(gè)是CLOSE表，存放已經(jīng)搜索過的節(jié)點(diǎn)，具體的算法流程圖如圖1所示。

1.1 常用的距離評估函數(shù)

是A*算法的距離估計(jì)值[6]，A*算法需要一個(gè)距離評估函數(shù)來計(jì)算這個(gè)值。常用的距離評估函數(shù)有曼哈頓距離、歐式幾何平面距離和切比雪夫距離。在沒有障礙物的地圖上，這三種距離評估函數(shù)得到的效果是一樣的，但是在有障礙物的情況下，這三種距離評估函數(shù)的效果略有差異。當(dāng)距離評估函數(shù)總是0時(shí)，A*算法就退化為Dijkstra算法[6]的效果。

1.1.1 曼哈頓距離

從數(shù)學(xué)上描述，曼哈頓距離是兩個(gè)點(diǎn)在各個(gè)坐標(biāo)軸上的距離差值的總和，維幾何空間中曼哈頓距離的數(shù)學(xué)描述為：

對于二維平面上的兩個(gè)點(diǎn)和，其曼哈頓距離為：

即歐式幾何平面距離為在直角坐標(biāo)系中兩個(gè)坐標(biāo)軸上的投影距離和。

1.1.2 歐式幾何平面距離

歐式幾何平面距離（Euclidean distance）又稱為歐式距離或歐幾里得距離[7]，其數(shù)學(xué)定義是維空間中兩個(gè)點(diǎn)之間的真實(shí)距離（幾何距離），其數(shù)學(xué)符號可以描述為：

對于二維平面上的兩個(gè)點(diǎn)和其歐式幾何平面距離為：

即平面幾何中兩點(diǎn)之間的幾何距離。

1.1.3 切比雪夫距離

切比雪夫距離（Chebyshev Distance）是由一致范數(shù)（或稱上確界范數(shù)）衍生的度量，從數(shù)學(xué)角度上理解，對于兩個(gè)向量和其切比雪夫距離就是向量中各個(gè)分量的差的絕對值中最大的那一個(gè)，用數(shù)學(xué)符號可以描述為：

特別情況下，對于平面上的兩個(gè)點(diǎn)和，其切比雪夫距離為：

距離評估函數(shù)與A*算法的結(jié)果之間存在很微妙的關(guān)系，如果令始終為0，相當(dāng)于一點(diǎn)啟發(fā)信息都沒有，則A*算法[5]退化為Dijkstra算法，這種情況即為最差的A*算法。的值越小，啟發(fā)信息越少，搜索范圍越大，速度越慢，但是越有希望得到最短路徑；的值越大，啟發(fā)信息越多，搜索的范圍越大，但是其有可能得不到真正的最短路徑。當(dāng)大到一定程度時(shí)，公式中的就可以忽略不計(jì)，則A*算法演化成為BFS（廣度優(yōu)先搜索算法），速度最快，但是不一定能夠得到最短路徑。所以通過調(diào)整和函數(shù)，可以使得A*算法[6]在速度與準(zhǔn)確性之間獲得一個(gè)折中的效果。

1.2 A*算法的實(shí)現(xiàn)

A*算法實(shí)現(xiàn)的關(guān)鍵在于維護(hù)OPEN表和CLOSE表，其中對于OPEN表的主要操作就是查詢最小的節(jié)點(diǎn)以及刪除節(jié)點(diǎn)，因此考慮在算法實(shí)現(xiàn)時(shí)將OPEN表[7]設(shè)計(jì)為有序表。這樣在OPEN列表存儲數(shù)據(jù)時(shí)就可以自動將數(shù)據(jù)按照距離進(jìn)行排序，這樣算法的執(zhí)行效率比較高。A*算法的參數(shù)設(shè)置見表1，參數(shù)的迭代次數(shù)見圖2。

通過仿真實(shí)驗(yàn)分析可以得出，A*算法[5]在有障礙物的情況下中和了BFS算法和Dijkstra算法的優(yōu)點(diǎn)，能夠更有效地找到最終的最短路徑。

2 A*算法與Dijkstra算法效率的比較

Dijkstra算法是典型的單源最短路徑算法，其適用于求解沒有負(fù)權(quán)邊的帶權(quán)有向圖的單源最短路徑問題。由于Dijkstra算法[2?3]使用了廣度優(yōu)先搜索的策略，它可以一次得到所有點(diǎn)的最短路徑。但是，它只是簡單地做廣度優(yōu)先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗費(fèi)很多時(shí)間和空間?？紤]到實(shí)際地圖上面兩點(diǎn)之間存在位置和距離等信息，A*算法既能夠像Dijkstra算法那樣搜索到最短路徑，又能像BFS（廣度優(yōu)先搜索算法）一樣使用啟發(fā)式函數(shù)進(jìn)行啟發(fā)式搜索，是目前各種尋徑算法中最受歡迎的選擇。

將A*算法同Dijkstra算法[6]進(jìn)行仿真比較，用于比較性能的主要指標(biāo)有：時(shí)間復(fù)雜度分析；搜索到最短路徑的成功率分析。利用C++語言編制了三種算法的最短路徑搜索程序，運(yùn)行在本地計(jì)算機(jī)上，并得出仿真模擬圖。

搜索效率的對比結(jié)果如表2所示。

由表2可以看出：當(dāng)?shù)貓D節(jié)點(diǎn)的個(gè)數(shù)和弧的條數(shù)比較多時(shí)，A*算法[5]的搜索效率比Dijkstra算法快很多，當(dāng)節(jié)點(diǎn)數(shù)不斷增多時(shí)，其搜索最短路徑的效率更高。在相同路網(wǎng)和位置信息的條件下進(jìn)行仿真實(shí)驗(yàn)的結(jié)果如圖3所示。

由圖3可以看出，兩種算法在相同障礙物條件下進(jìn)行模擬仿真時(shí)，A*算法的搜索效率和時(shí)間復(fù)雜度要明顯優(yōu)于Dijkstra算法，并對不同實(shí)驗(yàn)場景下的效率進(jìn)行對比，結(jié)果如圖4所示。

3 結(jié) 語

從Dijkstra算法和A*算法[2]的實(shí)現(xiàn)可知，Dijkstra算法的時(shí)間復(fù)雜度是其中是有向圖中頂點(diǎn)的個(gè)數(shù)。對于不含負(fù)權(quán)邊的有向圖來說，Dijkstra算法是目前最快單源最短路徑算法。A*算法兼有Dijkstra算法和廣度優(yōu)先搜索算法的特點(diǎn)，在速度和準(zhǔn)確性之間有很大的靈活性。除了調(diào)整和可以獲得不同的效果外，A*算法還有很多可以提高效率的改進(jìn)方法。比如，在地圖比較大的情況下使用二叉堆來維護(hù)OPEN表以獲得更好的運(yùn)算效率。

參考文獻(xiàn)

[1] WORBOYS M. Event?oriented approaches to geographic phenomena [J]. International journal of geographical information science， 2010， 19（1）： 1?28.

[2] NARAYANASAMY V. Game programming gems 6 [EB/OL]. [2015?05?12]. www.download.csdn.net/data.

[3] DYBSAND E. A finite state machine class [J]. Game programming gems， 2000（1）： 237?248.

[4] 周郭許，唐西林.基于柵格模型的機(jī)器人路徑規(guī)劃快速算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動力學(xué)約束的機(jī)器人無碰運(yùn)動規(guī)劃[J].機(jī)器人，1990（5）：14?19.

[6] VIDALVERD? F， BARQUERO M J， CASTELLANOSRAMOS J， et al. A large area tactile sensor patch based on commercial force sensors [J]. Sensors， 2010， 11（5）： 5489?5507.

[7] 李得偉，韓寶明，韓宇.一種逆向改進(jìn)型A*路徑搜索算法[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（22）：5175?5177.

[8] 林丹.一種室內(nèi)清潔機(jī)器人返回路徑規(guī)劃算法[J].重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2009，12（1）：110?113.

[9] 趙真明，孟正大.基于加權(quán)A～*算法的服務(wù)型機(jī)器人路徑規(guī)劃[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2008（z1）：196?198.

[10] KHATIB M， CHATILA R. An extended potential field approach for mobile robot sensor?based motions [C]// Proceedings of 1995 IEEE International Conference on Intelligent Autonomous Systems. [S.l.]： IEEE， 1995： 490?496.

[11] SILVERMAN M C， NIES D， JUNG B， et al. Staying alive： a docking station for autonomous robot recharging [C]// Procee?dings of 2002 IEEE International Conference on Robotics and Automation. Washington， DC： IEEE， 2002： 1050?1055.