基于改進A*算法的最優路徑搜索

朱云虹，袁 一

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.南京大學 地理與海洋科學學院，江蘇 南京 210093)

0 引 言

近年來，隨著地圖應用和導航技術的迅速發展，在覆蓋GPS的移動設備上(例如手機和汽車)利用地圖應用程序來搜索目的地路線的行為已經越來越普遍。當輸入初始地點和目的地后，幾秒鐘最短路線將顯示在移動設備上。目前地圖應用程序通過路網進行搜索，通常有兩個重要功能，分別是距離查詢和路徑查詢。距離查詢是查詢地圖中兩點之間的最短距離，路徑查詢是查詢地圖中兩點之間具有最短距離的路徑。

最短路徑[1]作為路網中的焦點問題之一，目前已在計算機通信、運籌學以及地理信息系統等領域得到廣泛應用，主要涉及智能交通[2]、地理信息系統[3]、路徑規劃[4]、計算機網絡[5]等。從20世紀50年代起，研究者們就對最短路徑問題展開了深入探索，研究最短路徑問題的目標是在網絡中搜索兩個節點之間最有效的最短路徑。一系列經典算法的誕生奠定了最短路徑算法的基礎，主要包括：計算一個節點到全部任意節點之間最短路徑的Dijkstra算法[6]，計算任意對節點間最短路徑的Floyd算法[7]，以及智能A*算法[8]。

大多數路網的研究通常都集中在如何減少最短路徑查詢的計算時間上面。例如，基于覆蓋的算法[9]減少了查詢的預處理時間，比普通A*算法和Dijkstra算法的查詢速度快10倍；一種稱為動態層次結構的算法(AH)通過縮小理論與實踐之間差距的指標體系來優化路網上的最短路徑和距離查詢時間[10]。但是上述算法僅僅能夠優化查詢的計算時間，并不能改善最短路徑實際消耗的行程時間。

RoadRank算法是在城市道路網中計算每個路段的影響分數算法，并能根據總體分數進行排序，通過在每個時間點提供最新的交通數據，不斷隨時間增量更新影響分數。RoadRank算法可用作動態城市道路網絡的交通擁堵和影響估計[11]，給出了每個路段的影響分數。該算法考慮到了擁擠，但忽略了每個節點上的交通燈。

交通燈是城市交通網絡的重要組成部分[12]，隨著城市流量的增加，人們因為等待交通燈消耗的時間越來越長。目前，部分大城市的交通堵塞問題十分嚴峻，已成為社會待解決的一大難題，極大影響了群眾的正常出行。因此，交通燈對最短路徑的影響不可忽視。地圖應用程序提供的最短路線并不一定是想要的路線，在實際路網中用戶消耗大量時間等待交通燈和道路擁擠。傳統的A*算法通常忽略了交通燈的問題，其能夠獲得距離最短的路線，但行程時間不一定最短。

解決這些問題的關鍵在于修改地圖應用中傳統A*算法的啟發式函數，因此提出了一種基于新的啟發式函數的改進A*算法。

1 基本概念

1.1 標題路網

路網定義為N=(I,R)，包括一系列道路交點I={i1,i2,…,in}(作為節點)，通過一系列路段R={r1,r2,…,rn}連接上述節點。其中每個路段ri關聯了本身的特征值，包含不同交通狀況的衡量指標。

1.2 啟發式函數

啟發式算法是一種基于直觀或經驗的局部優化算法，也稱為智能算法、現代優化算法[13]，已得到了深入研究和廣泛應用，主要包括神經網絡算法[14]、遺傳算法[15]等。A*算法也是一種啟發式算法。算法的共性是基于客觀世界中的一些自然現象，通過與組合優化求解進行類比，找出共性設計算法。啟發式算法的難點是建立符合實際問題的一系列啟發式規則(即啟發式函數)，優點在于比盲目型的搜索算法高效。一個經過仔細設計的啟發式函數，通常能在較短時間內獲得一個搜索問題的最優解。

1.3 歐幾里德距離

歐幾里德距離(Euclidean distance)指在m維空間中兩個點之間的真實距離，或者向量的自然長度(即該點到原點的距離)。在二維和三維空間中的歐氏距離就是兩點間的實際距離[16]。在歐幾里德平面中，如果兩個點為p=(x1,y1)和q=(x2,y2)，則距離由式(1)給出：

(1)

1.4 曼哈頓距離

曼哈頓距離(Manhattan distance)由十九世紀的赫爾曼·閔可夫斯基所創[17]，用以標明兩個點在標準坐標系上的絕對軸距總和，是路網中啟發式方法通常使用的距離之一。在歐幾里德平面中，如果兩個點為p=(x1,y1)和q=(x2,y2)，則曼哈頓距離由式(2)給出：

d(p,q)=|x1-x2|+|y1-y2|

(2)

曼哈頓距離相比歐幾里德距離，對起點和目標點之間的實際行駛距離會產生更為精確的估計，因為在實際情況中很少存在起點到目標點之間的直接路徑，但有時曼哈頓距離也會高估實際距離。

2 A*算法

2.1 基本原理

A*算法是以Dijkstra為基礎的啟發式搜索方法，是廣泛已知的最佳搜索形式[18]。算法的關鍵創新點在于，在擴展下一個節點時引入路網信息，對當前節點到目標節點的距離進行評估。

基于評估函數f(n)選擇節點進行擴展。評估函數解釋為成本估算，所以評估最低的節點首先被擴展[19]。評估函數表示如下：

f(n)=g(n)+h(n)

(3)

其中，f(n)為從起始節點經由當前節點n到目標節點狀態的成本估計；g(n)為路徑從起始節點到當前節點n的實際成本；h(n)為啟發式函數，表示從當前節點n到目標節點的最佳路徑的估計成本。

對當前節點n的評估方法有多種，如距離、方向、其他指標以及各種指標的綜合應用，但是評估的基本原則是評估值與實際值越接近，評估函數的效果越好。

2.2 算法實現

A*算法的流程[20]如圖1所示。

(1)建立兩個列表存放節點數據(分別為開放列表和關閉列表)；

(2)將初始節點加入開放列表；

(3)尋找初始節點周圍所有可到達的節點，跳過關閉列表中的節點，加入到開放列表中；

(4)已訪問過的節點加入到關閉列表中；

(5)當開始搜索下一節點時，從開放列表中尋找f值最小的作為下一個擴展的節點(當前節點)；

(6)所有當前節點可到達的節點再次加入開放列表之后，重新比較f值，并且根據f值的大小在開放列表中生成升序排列隊列。在搜索過程中，使用廣度優先算法[21]依次選取隊列的首元素，計算可能子節點的g、h和f值，直到找到目標節點或者沒有找到目標節點開放列表已經為空時算法結束。

圖1 A*算法流程

A*算法實現的具體步驟為：

(1)初始節點加入open表;

(2)從open表中尋找f值最小的節點作為當前節點。當前節點加入到close表的同時將其在open表中刪除;

(3)針對當前節點的所有可達節點：(a)若該節點在close表，就跳過該節點，否則進行b；(b)若該節點不在open表中，則將其加入并且使其父指針指向該節點。若該節點在open表中，則計算當前g值，如果比原來g值小，則該節點滿足條件。修改其父指針指向新的節點，并計算新的f值和g值，對open表的f值重新進行排序;

(4)在整個搜索過程中，當目標節點已加入close表時，即找到最短路徑，此時停止搜索。或者當沒有找到目標節點而開放列表已經為空時，即找不到路徑，此時也停止搜索;

(5)保存搜索路徑的軌跡。通過父指針由目標節點回到初始節點。

3 改進A*算法

算法根據實際路網的條件可以被修改，為了簡化路網中的交通燈問題，對于交通燈的假設如下：假設1：每個十字路口都有交通燈。假設2：初始時，交通燈從紅燈恰好變成綠燈。假設3：每個交通燈同時具有相同的顏色。假設4：紅燈需要1分鐘，綠燈需要1分鐘。假設5：右轉不需要等待交通燈可直接通行。假設6：汽車的平均行駛速度為60英里/小時。假設7：如果交通燈是綠燈，則汽車可以直接穿過該十字路口。

為了實現合理規避交通燈且具有最短行程時間的路徑，主要基于傳統的A*算法思想，改進原有的距離啟發式函數。在改進A*算法中，將總行程時間用作估計成本。估計的行程時間是駕駛時間和等待時間的總和。根據假設6，總駕駛時間可由總駕駛距離除以駕駛速度得到。總等待時間是路網中每個節點上的等待時間的總和。最佳路線是從初始節點到目標節點需要最短時間的路徑。

改進A*與傳統A*算法之間的關鍵差異在于增加了等待時間的因素。傳統A*算法中，假設汽車可直接通過每個節點而不用等待，然而在實際路網情況中幾乎不可能。同時，等待時間與駕駛時間相比不是一個可忽略的時間，特別是在市中心以及道路交通擁堵時(同一個交通燈的等待次數變多)。

假設d(n)是從初始節點到節點n的總行程時間，可通過計算到達節點n前的行程時間總和得到，即從上一節點到節點n的行程時間以及從上一節點到節點n的等待時間。如果汽車進行右轉彎，則節點的等待時間為0。否則，將判斷該節點的交通燈是否為紅燈。根據假設3和4可知，如果行程時間的上限是一個奇整數，則交通燈是綠燈；否則，交通燈是紅燈。當交通燈為紅燈，必須等到轉向綠燈后繼續行程。因此，如果行程是從節點u到節點n，可以通過以下函數計算：

d(n)=

(4)

其中，c(u,v)為從節點u到節點v的駕駛時間，可由邊長度除以駕駛速度計算得到；w(u)為節點u處的等待時間，可通過開始時間和當前路徑從起始節點到節點u的行程時間計算得到。在實驗中，假設在初始節點處的交通燈從紅燈變成綠燈，不考慮初始時間的影響。

用x來表示節點u的父節點，定義兩個向量Vector(x,u)和Vector(u,v)，計算出兩個向量的旋轉角度。如果是右轉彎，轉角小于0；如果是左轉彎，轉角大于0。為了避免直線產生一個角度，定義右轉彎角度范圍為-135°～-45°。

對于啟發式函數，使用曼哈頓距離除以行駛速度作為駕駛時間的估計或者歐幾里德距離除以行駛速度作為駕駛時間的估計。

4 實驗結果

利用Minneapolis地圖數據作為基礎數據，地圖共有2 326個邊和946個節點，邊的平均駕駛時間為1.95分鐘。地圖原始數據使用map.txt存放，其中每一行表示一條邊，第一個整數代表道路是否是單行道，后4個數字分別代表一條邊的起點坐標和終點坐標。通過程序讀取此地圖并生成道路網絡。實驗中的Minneapolis地圖如圖2所示，其中淺黑線表示單行道和深黑線代表雙行道。

圖2 Minneapolis地圖

由于邊的平均駕駛時間為1.95分鐘，因此交通燈的等待時間是一個不可忽略的值。實驗對比分析了傳統的A*算法與改進的A*算法的實現效果，兩種算法均分別使用曼哈頓距離和歐氏距離作為啟發式函數。算法的對比性能指標是最短路徑搜索的運行時間，節點的擴展數量和路徑的行程時間。

實驗隨機選擇4個測試樣本。在第一個測試樣本中，初始點坐標為(1 121,7 568)，目標點坐標為(2 179,8 595)。在第二個測試樣本中，初始點坐標為(1 121,7 568)，目標點坐標為(1 455,7 920)。在第三個測試樣本中，初始點坐標為(2 197,8 966)，目標點坐標為(1 961,7 800)。在第四個測試樣本中，初始點坐標為(2 197,8 966)，目標點坐標為(2 085，8 543)。

通過使用曼哈頓距離和歐幾里德距離作為啟發式函數的傳統A*算法和改進A*算法，來搜索相同樣本的最短路徑。4種算法的性能實驗結果如表1～4所示。第三個測試樣本中利用4種算法搜索的最短路徑結果如圖3所示，其中粗灰色線代表最短路徑。

5 結果分析

對實驗結果的綜合分析發現：4種算法的運行時間均在大致相同的規模內(毫秒級)。運行時間的結果和節點擴展數量表明，改進A*算法與傳統A*算法能在類似的時間范圍內執行計算，并擴展相同數量的節點；傳統A*算法比改進A*算法運行時間更快，分析其原因是：考慮到交通燈等待時間之后，改進A*算法中有更復雜的g(n)和h(n)需要計算，略微(在毫秒級)影響了算法的運行時間;(3)兩種使用曼哈頓的算法與兩種使用歐幾里德的算法相比在距離上擴展了較少的節點，且運行時間較短，表明曼哈頓距離相比歐幾里德距離在運行時間方面具有更好的估計效果。

表1 節點(1 121,7 568)到節點(2 179,8 595)的實驗結果

表2 節點(1 121,7 568)到節點(1 455,7 920)的實驗結果

表3 節點(2 197,8 966)到節點(1 961,7 800)的實驗結果

表4 節點(2 197,8 966)到節點(2 085,8 543)的實驗結果

圖3 搜索結果

上述表明：傳統A*算法與改進A*算法均能夠實現最短路徑的搜索，且運行時間和擴展節點數量相差不大，在這兩方面性能相似。為了縮短用戶在路網的行程時間，文中著重關注兩類算法在性能-總行程時間上的差異(min級)。

結合分析第3個和第4個測試樣本，實驗發現：使用歐幾里德距離的啟發式函數的改進A*算法能搜索到最少行程時間的路徑，改進A*算法的總行程時間與傳統A*算法相比減少約5%，表明文中提出的方法在總行程時間方面更有效。分析其原因是：文中算法改進了等待交通燈的時間，其次是由于曼哈頓距離相對于歐幾里德距離會產生一部分過高估計，從而影響到算法的行程時間。

因此最好使用歐幾里德距離作為啟發式函數的改進A*算法，其始終能提供最佳行程時間路徑。從圖3中看出，不同方法搜索到的最短路徑是不同的，而最優路徑會有一些右轉彎，以避免交通燈的等待時間。

6 結束語

文中致力于改進和完善傳統的最短路徑搜索A*算法，克服路網中交通燈的等待問題，在啟發式函數中加入交通燈的等待時間，并融合到傳統的A*算法中進行最短路徑搜索。通過傳統算法與改進A*算法的對比實驗證明，文中提出的算法能實現最短路徑的搜索且具有較短的行程時間，并與傳統算法能夠在同一運行時間限制下實現。對基于A*算法的研究具有一定的理論價值，并且豐富了路網最短路徑搜索領域的內容。

參考文獻：

[1] SHEHZAD F,SHAH M A A.Evaluation of shortest paths in road network[J].Pakistan Journal of Commerce & Social Sciences,2009,3:67-79.

[2] FARO A,GIORDANO D.Algorithms to find shortest and alternative paths in free flow and congested traffic regimes[J].Transportation Research Part C Emerging Technologies,2016,73:1-29.

[3] ZHANG X,GUO X,JING G,et al.Research of improved shortest path algorithm in campus GIS[J].Open Cybernetics & Systemics Journal,2015,9(1):1060-1063.

[4] XU W,HE S,SONG R,et al.Finding the K shortest paths in a schedule-based transit network[J].Computers & Operations Research,2012,39(8):1812-1826.

[5] YANG H H,CHEN Y L.Finding K shortest looping paths in a traffic-light network[J].Computers & Operations Research,2005,32(3):571-581.

[6] WANG S X.The improved Dijkstra’s shortest path algorithm and its application[J].Procedia Engineering,2012,29:1186-1190.

[7] 趙禮峰,梁 娟.最短路問題的Floyd改進算法[J].計算機技術與發展,2014,24(8):31-34.

[8] SHAHZADA A,ASKAR K.Dynamic vehicle navigation:an A* algorithm based approach using traffic and road information[C]//International conference on computer applications and industrial electronics.[s.l.]:IEEE,2011:514-518.

[9] GUTMAN R J.Reach-based routing:a new approach to shortest path algorithms optimized for road networks[C]//Workshop on algorithm engineering & experiments & the first workshop on analytic algorithmics & combinatorics.[s.l.]:[s.n.],2004:100-111.

[10] ZHU A D,MA H,XIAO X,et al.Shortest path and distance queries on road networks:towards bridging theory and practice[C]//ACM SIGMOD international conference on management of data.New York,NY,USA:ACM,2013:857-868.

[11] ANWAR T,LIU C,VU H L,et al.RoadRank:traffic diffusion and influence estimation in dynamic urban road networks[C]//ACM international conference on information and knowledge management.New York,NY,USA:ACM,2015:1671-1674.

[12] 王先美.交通燈控制系統的設計[J].科技傳播,2010(23):114.

[13] 陳 萍.啟發式算法及其在車輛路徑問題中的應用[D].北京:北京交通大學,2009.

[14] 馮立穎.改進的BP神經網絡算法及其應用[J].計算機仿真,2010,27(12):172-175.

[15] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29(4):1201-1206.

[16] 徐士英.關于歐幾里得空間Ed中的二距離集[J].中國計量學院學報,2002,13(1):16-18.

[17] 李 彬.基于相對曼哈頓距離的Web聚類算法研究[J].電子商務,2013(11):57-58.

[18] 熊 偉,張仁平,劉奇韜,等.A*算法及其在地理信息系統中的應用[J].計算機系統應用,2007,16(4):14-17.

[19] 劉 浩,鮑遠律.A*算法在矢量地圖最優路徑搜索中的應用[J].計算機仿真,2008,25(4):253-257.

[20] 楊銀濤.基于A*算法的避障應用仿真[D].鄭州:鄭州大學,2014.

[21] 歐陽圣，胡望宇．幾種經典搜索算法研究與應用[J]．計算機系統應用,2011,20(5):243-247.