基于改進A*算法的最優(yōu)路徑搜索

朱云虹，袁 一

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

0 引 言

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

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

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

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

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

解決這些問題的關(guān)鍵在于修改地圖應(yīng)用中傳統(tǒng)A*算法的啟發(fā)式函數(shù)，因此提出了一種基于新的啟發(fā)式函數(shù)的改進A*算法。

1 基本概念

1.1 標題路網(wǎng)

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

1.2 啟發(fā)式函數(shù)

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

1.3 歐幾里德距離

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

(1)

1.4 曼哈頓距離

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

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

(2)

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

2 A*算法

2.1 基本原理

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

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

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

(3)

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

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

2.2 算法實現(xiàn)

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

(1)建立兩個列表存放節(jié)點數(shù)據(jù)(分別為開放列表和關(guān)閉列表)；

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

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

(4)已訪問過的節(jié)點加入到關(guān)閉列表中；

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

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

圖1 A*算法流程

A*算法實現(xiàn)的具體步驟為：

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

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

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

(4)在整個搜索過程中，當目標節(jié)點已加入close表時，即找到最短路徑，此時停止搜索?；蛘弋敍]有找到目標節(jié)點而開放列表已經(jīng)為空時，即找不到路徑，此時也停止搜索;

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

3 改進A*算法

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

為了實現(xiàn)合理規(guī)避交通燈且具有最短行程時間的路徑，主要基于傳統(tǒng)的A*算法思想，改進原有的距離啟發(fā)式函數(shù)。在改進A*算法中，將總行程時間用作估計成本。估計的行程時間是駕駛時間和等待時間的總和。根據(jù)假設(shè)6，總駕駛時間可由總駕駛距離除以駕駛速度得到?？偟却龝r間是路網(wǎng)中每個節(jié)點上的等待時間的總和。最佳路線是從初始節(jié)點到目標節(jié)點需要最短時間的路徑。

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

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

d(n)=

(4)

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

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

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

4 實驗結(jié)果

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

圖2 Minneapolis地圖

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

實驗隨機選擇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)。

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

5 結(jié)果分析

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

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

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

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

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

圖3 搜索結(jié)果

上述表明：傳統(tǒng)A*算法與改進A*算法均能夠?qū)崿F(xiàn)最短路徑的搜索，且運行時間和擴展節(jié)點數(shù)量相差不大，在這兩方面性能相似。為了縮短用戶在路網(wǎng)的行程時間，文中著重關(guān)注兩類算法在性能-總行程時間上的差異(min級)。

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

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

6 結(jié)束語

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

參考文獻：

[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].計算機技術(shù)與發(fā)展,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] 王先美.交通燈控制系統(tǒng)的設(shè)計[J].科技傳播,2010(23):114.

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

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

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

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

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

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

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

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

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