劉云翔+杜杰+張晴

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

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

中圖分類號： 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]是圖論中網(wǎng)絡分析的經(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ù)有著更高的運算效率，而且利用啟發(fā)信息大幅度提高了搜索速度。這種全新的啟發(fā)式搜索算法[4]將會極大地改變現(xiàn)有的交通管理與服務模式。

1 A*算法原理

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

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

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

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

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

1.1.1 曼哈頓距離

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

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

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

1.1.2 歐式幾何平面距離

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

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

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

1.1.3 切比雪夫距離

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語

從Dijkstra算法和A*算法[2]的實現(xiàn)可知，Dijkstra算法的時間復雜度是其中是有向圖中頂點的個數(shù)。對于不含負權(quán)邊的有向圖來說，Dijkstra算法是目前最快單源最短路徑算法。A*算法兼有Dijkstra算法和廣度優(yōu)先搜索算法的特點，在速度和準確性之間有很大的靈活性。除了調(diào)整和可以獲得不同的效果外，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] 周郭許，唐西林.基于柵格模型的機器人路徑規(guī)劃快速算法[J].計算機工程與應用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動力學約束的機器人無碰運動規(guī)劃[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].系統(tǒng)仿真學報，2007，19（22）：5175?5177.

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

[9] 趙真明，孟正大.基于加權(quán)A～*算法的服務型機器人路徑規(guī)劃[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.