基于路徑優化的A*算法與Dijkstra算法的性能比較

劉云翔+杜杰+張晴

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

關鍵詞： 最短路徑； A*算法； Dijkstra算法； 路徑優化

中圖分類號： TN911.1?34； TP312 文獻標識碼： 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]是圖論中網絡分析的經典問題，近年來，隨著路徑搜索技術的不斷發展，已經涌現出很多成熟的路徑規劃算法，比如，基于圖論的Dijkstra算法[2?3]，以及關于人工智能領域的啟發式搜索算法和動態規劃算法等。A*啟發式搜索算法作為人工智能領域的重要組成部分，其針對網格數據有著更高的運算效率，而且利用啟發信息大幅度提高了搜索速度。這種全新的啟發式搜索算法[4]將會極大地改變現有的交通管理與服務模式。

1 A*算法原理

傳統的BFS算法的評估函數只考慮當前點與終點的距離，其策略是選擇與終點最近的點進行搜索。而Dijkstra算法則只關注當前點與起點的距離，選擇與起點最近的點開始搜索。A*算法[5]則是將二者結合起來，其啟發函數采用如下的計算公式：

式中：就是A*算法[5]對每個節點的評估函數[2]，其包含兩部分信息：是從起點到當前節點的實際代價，也就是從起點到當前節點的移動距離；相鄰的兩個點的移動距離是1，當前點距離起點越遠，這個值就越大。是從當前節點到終點的距離評估值，這是一個從當前節點到終點的移動距離的估計值。

A*算法的搜索過程需要兩個表：一個是OPEN表，存放當前已經被發現但是還沒有搜索過的節點；另一個是CLOSE表，存放已經搜索過的節點，具體的算法流程圖如圖1所示。

1.1 常用的距離評估函數

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

1.1.1 曼哈頓距離

從數學上描述，曼哈頓距離是兩個點在各個坐標軸上的距離差值的總和，維幾何空間中曼哈頓距離的數學描述為：

對于二維平面上的兩個點和，其曼哈頓距離為：

即歐式幾何平面距離為在直角坐標系中兩個坐標軸上的投影距離和。

1.1.2 歐式幾何平面距離

歐式幾何平面距離（Euclidean distance）又稱為歐式距離或歐幾里得距離[7]，其數學定義是維空間中兩個點之間的真實距離（幾何距離），其數學符號可以描述為：

對于二維平面上的兩個點和其歐式幾何平面距離為：

即平面幾何中兩點之間的幾何距離。

1.1.3 切比雪夫距離

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

特別情況下，對于平面上的兩個點和，其切比雪夫距離為：

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

1.2 A*算法的實現

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

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

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

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

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

搜索效率的對比結果如表2所示。

由表2可以看出：當地圖節點的個數和弧的條數比較多時，A*算法[5]的搜索效率比Dijkstra算法快很多，當節點數不斷增多時，其搜索最短路徑的效率更高。在相同路網和位置信息的條件下進行仿真實驗的結果如圖3所示。

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

3 結 語

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

參考文獻

[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].計算機工程與應用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動力學約束的機器人無碰運動規劃[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] 李得偉，韓寶明，韓宇.一種逆向改進型A*路徑搜索算法[J].系統仿真學報，2007，19（22）：5175?5177.

[8] 林丹.一種室內清潔機器人返回路徑規劃算法[J].重慶科技學院學報（自然科學版），2009，12（1）：110?113.

[9] 趙真明，孟正大.基于加權A～*算法的服務型機器人路徑規劃[J].華中科技大學學報（自然科學版），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.