孫玉昕,章 瑾

(武漢工程大學(xué)計算機(jī)與科學(xué)學(xué)院，湖北 武漢 430074)

0 引 言

路徑搜索的核心思想是利用計算機(jī)的處理能力，準(zhǔn)確高效地在網(wǎng)絡(luò)中任意兩個或多個節(jié)點之間尋找出最佳路徑.路徑搜索算法在計算機(jī)工程中有著廣泛的應(yīng)用價值，比如地理信息系統(tǒng)、位置服務(wù)、智能交通、智能機(jī)器人等領(lǐng)域[1].在工程實踐中，路徑搜索的時間效率和空間效率是判斷算法的優(yōu)劣重要指標(biāo)[2].啟發(fā)式搜索和盲目搜索相比，可省略大量無謂的搜索路徑，已能夠極大提高搜索效率，但當(dāng)面臨百萬節(jié)點的復(fù)雜網(wǎng)絡(luò)拓?fù)鋾r，啟發(fā)式搜索算法的搜索耗時將會呈指數(shù)級快速增長，無法滿足需求，因此考慮引入二叉堆進(jìn)行進(jìn)一步的算法優(yōu)化，使得搜索速度進(jìn)一步提升.

1 實驗部分

1.1 算法選擇

路徑搜索的核心算法就是最短路徑算法 ,它是計算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點.目前已知的最短路徑算法主要有 Floyd (弗洛伊德)算法、矩陣算法和Dijkstra(迪杰斯特拉)算法.其中Dijkstra算法是最為經(jīng)典的最短路徑算法，其主要特點是以起始點為中心逐層外推，直到推進(jìn)至終點.Dijkstra算法能確保求出最短路徑的最優(yōu)解，但由于它是逐層遍歷的方式導(dǎo)致其效率比較低，無法滿足工程實際的需求[3].

為了滿足效率和靈活性要求，基于人工智能的啟發(fā)式搜尋法(Heuristic Search Methods)的A*算法常被應(yīng)用路徑搜索[4].所謂啟發(fā)式是在Dijkstra算法基礎(chǔ)上，引入啟發(fā)函數(shù)(Heuristic Function)來估算當(dāng)前節(jié)點與目標(biāo)節(jié)點的距離，通過啟發(fā)函數(shù)的估算值不斷動態(tài)調(diào)整搜索方向.與Dijkstra算法的盲目搜索過程，A*算法的啟發(fā)式搜索方法充分利用網(wǎng)絡(luò)拓?fù)鋱D給出的信息來動態(tài)地調(diào)整搜索方向，因此搜索效率更高[5-6].

A*算法的核心計算公式表示為

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

其中f(n) 是途經(jīng)節(jié)點n從初始點到目標(biāo)節(jié)點的路徑距離的估價函數(shù)值，g(n) 是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際路徑距離，h(n)是從n到目標(biāo)節(jié)點的距離的啟發(fā)函數(shù).f(n)值越小則表示該結(jié)點的路徑越短[7-9].

A*算法流程圖如圖1所示.運(yùn)用A*算法進(jìn)行路徑搜索計算.A*算法的時間復(fù)雜度是O(n2)，n為網(wǎng)絡(luò)節(jié)點數(shù)量.因此，隨著網(wǎng)絡(luò)節(jié)點數(shù)和路徑長度的增加，A*算法的搜索耗時呈指數(shù)級的快速增長.在工程實際中，經(jīng)常需要對大規(guī)模的節(jié)點進(jìn)行搜索，當(dāng)面臨百萬節(jié)點的復(fù)雜網(wǎng)絡(luò)拓?fù)鋾r， A*算法的效率仍然無法滿足需求[5，7].

圖1 A*算法流程圖Fig.1 A* algorithm flowchart

1.2 優(yōu)化分析

針對上述大規(guī)模網(wǎng)絡(luò)的路徑搜索需求，重點研究了應(yīng)用A*算法進(jìn)行路徑搜索時的效率優(yōu)化問題.A*算法的數(shù)據(jù)結(jié)構(gòu)的核心是兩個表：Open表(Open表中存放已計算出估計值的結(jié)點)與Closed表(Closed表存放已訪問過的結(jié)點)，并且還沒有訪問過的A*結(jié)點.Open表是A*算法訪問最頻繁的表，因為需要從Open表中取出最小的估計值，作為本次訪問節(jié)點.

大量的操作是針對Openlist列表(Openlist表存放可能成為最短路徑的隊列)進(jìn)行的，重復(fù)不斷的OpenList進(jìn)行節(jié)點增加，刪除，查找，按f值排序等操作.可以說Open表的數(shù)據(jù)結(jié)構(gòu)設(shè)計很大程度上決定了算法的效率.最易于實現(xiàn)Open表數(shù)據(jù)結(jié)構(gòu)是鏈表結(jié)構(gòu)，采用鏈表或者哈希表的數(shù)據(jù)結(jié)構(gòu)來處理Openlist.這樣算法的過程比較清晰，設(shè)計難度也較低.但是當(dāng)需要處理大規(guī)模的網(wǎng)絡(luò)時，OpenList的列表長度會增長到有數(shù)千個節(jié)點組成.在重復(fù)對大規(guī)模的節(jié)點進(jìn)行排序，搜索，操作，計算量會非常大.其中最主要的是對Openlist的排序操作，如果使用常規(guī)的排序算法如冒泡法等，需要重復(fù)不斷的遍歷整個列表，算法復(fù)雜度是O(n2)[2].

A*算法并不需要Openlist完全有序，只需要找出f值最小的節(jié)點即可，而對其他節(jié)點的位置無要求.因此采用二叉堆可滿足算法對Openlist的操作需求.

首先二叉堆是完全二叉樹，并滿足堆的特性：父節(jié)點的鍵值總是小于其子節(jié)點的鍵值.最小鍵值的節(jié)點總在堆的頂端.因此在算法中查找f值最小的節(jié)點，堆頂端的節(jié)點就是需要的節(jié)點.用一維數(shù)組來表示二叉堆時，數(shù)組中第n(n>=1)節(jié)點，其子節(jié)點位于數(shù)組的2n和2n+1的位置，其父節(jié)點位于數(shù)組n/2的位置.如圖2所示(數(shù)組下標(biāo)從1開始).

圖2 二叉堆的數(shù)組表示Fig.2 Binary heap array representation

顯然數(shù)組第1個節(jié)點就是堆頂節(jié)點，就是f值最小節(jié)點.利用二叉堆的特性，可直接獲取Open表中f值最小的節(jié)點.從openlist列表中取出f值最小的節(jié)點，需要將其從堆移除.在移除堆頂節(jié)點后，將堆的最后一個節(jié)點移動到頂點，再將新堆頂與其兩個子節(jié)點比較，如父節(jié)點比子節(jié)點大，就交換二者，直到父節(jié)點比兩個子節(jié)點的f值都低.

當(dāng)向二叉堆增加節(jié)點時，可將新節(jié)點放在數(shù)組末尾.然后與其父節(jié)點比較，如果新節(jié)點的f值更低，就交換父子的位置.直到新節(jié)點不再比它的父節(jié)點低，或者這個節(jié)點已經(jīng)到達(dá)頂端.在搜索過程中，節(jié)點的f值可能會改變，這時要重新對Openlist進(jìn)行有序化處理：從發(fā)生改變的節(jié)點開始，將其與父節(jié)點比較，如果子節(jié)點的f值小于其父節(jié)點，就將他們交換.直到到達(dá)堆頂為止.

運(yùn)用二叉堆可直接獲取Openlist的f值最小的節(jié)點，計算量與Openlist大小無關(guān).向Openlist插入節(jié)點，刪除節(jié)點，排序操作的算法時間復(fù)雜度都是O(logn).n為Openlist的節(jié)點數(shù).從理論分析可知，二叉堆對于大規(guī)模的A*路徑搜索是效率比較優(yōu)化的算法.

2 結(jié)果與討論

應(yīng)用A*算法進(jìn)行最短路徑搜索，用于測試的路網(wǎng)模型是一個擁有100萬個節(jié)點(1000*1000)的超大型二維網(wǎng)格.為了網(wǎng)絡(luò)拓?fù)淠Ｐ透忧逦徒Y(jié)構(gòu)化，網(wǎng)絡(luò)中的每個節(jié)點(處于邊緣的節(jié)點除外)都擁有8個不同方向的相鄰節(jié)點，節(jié)點分為兩類：可通行與不可通行.A*算法需要在網(wǎng)格中指定的起始節(jié)點和目標(biāo)節(jié)點之間，快速搜索出一條由可通行的節(jié)點組成的而且是代價最小的通行路徑.在測試網(wǎng)絡(luò)中按照一定比例(30%)隨機(jī)地設(shè)置的不可通行節(jié)點，當(dāng)路徑搜索遇到不可通行的節(jié)點時，是不能直接通行的，必須要繞過.

路徑代價如圖3中，節(jié)點與方向正對的四個相鄰節(jié)點之間的路徑代價為10，與斜向方向的相鄰節(jié)點的四個子節(jié)點的路徑代價為14.這樣的路網(wǎng)結(jié)構(gòu)可以很好的模擬二維平面路網(wǎng)的拓?fù)浣Y(jié)構(gòu)和數(shù)學(xué)模型，同時盡量采用整形數(shù)值計算，降低運(yùn)算難度，提高計算效率.

圖3 網(wǎng)絡(luò)結(jié)構(gòu)模型Fig.3 Network structure model

A*算法中的關(guān)鍵估價函數(shù)值f(n)=g(n)+h(n)，其中g(shù)(n)表示為從節(jié)點n到起始節(jié)點s的已知最短路徑長度.H(n)標(biāo)準(zhǔn)從節(jié)點n到目標(biāo)節(jié)點o的路徑估計值.估價函數(shù)f(n) =g(n) +h(n)代表經(jīng)過該節(jié)點的路徑的估計值，在A*算法運(yùn)行中，f(n)值越小那么此節(jié)點的路徑越好.估價函數(shù)通過判斷父節(jié)點和子節(jié)點的相對位置來進(jìn)行累加計算，從起始節(jié)點開始逐步外推，直到到達(dá)目標(biāo)節(jié)點位置.

對二維網(wǎng)絡(luò)拓?fù)?，圖中節(jié)點由坐標(biāo)(X,Y)表示，那么節(jié)點A到目標(biāo)節(jié)點B的啟發(fā)函數(shù)可以用兩點間最短路徑的方法來設(shè)計，即

但考慮到計算機(jī)在處理開平方根運(yùn)算會增大計算量，采用另外一個近似的公式取代

H(n)=abs(Xn-Xo)+abs(Yn-Yo)

其中，Xn，Yn為節(jié)點n的橫向和縱向坐標(biāo)值;Xo，Yo為目標(biāo)節(jié)點o的橫向和縱向坐標(biāo)值.

abs()為絕對值函數(shù).圖4為路網(wǎng)搜索的過程實例，圖中每個像素點代表路網(wǎng)拓?fù)渲幸粋€節(jié)點，白色點為可通行節(jié)點，黑色點為不可通行節(jié)點.深灰色點為搜索過的節(jié)點(Close表)，白色點組成的線條即為所需的最短路徑結(jié)果.

圖4 網(wǎng)絡(luò)搜索過程Fig.4 Road network search process

通過常規(guī)的鏈表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的Openlist和采用二叉堆進(jìn)行優(yōu)化后的Openlist的算法進(jìn)行多次對比分析，結(jié)果如表1和圖5所示.

表1 引入二叉堆算法后實際耗時對比Table 1 Introduction of binary heap algorithms compare the actual time-consuming

圖5 引入二叉堆算法后實際耗時對比Fig.5 Introducing binary heap algorithm actually consuming comparison chart注：

3 結(jié) 語

從兩種算法的計算量和耗時對比可知，常規(guī)算法在進(jìn)行長路徑、大搜索空間的搜索時，計算時間迅速增加，而二叉堆算法則表現(xiàn)出良好的時間線性，沒有出現(xiàn)搜索時間爆炸式增長的情況.而針對數(shù)千個路徑節(jié)點，在需要搜索幾百萬的海量節(jié)點空間的情況下，應(yīng)用二叉堆數(shù)據(jù)結(jié)構(gòu)的A*算法具有良好的時間線性度，具備工程應(yīng)用價值.

致謝

論文在資料收集和實驗數(shù)據(jù)采集過程中，得到黃珂副教授的大力支持，在此謹(jǐn)向她表示衷心的感謝.

參考文獻(xiàn)：

[1] 陳偉亞，劉芳芳.地理信息系統(tǒng)在水污染控制規(guī)劃中的應(yīng)用[J].武漢工程大學(xué)學(xué)報，2013，35(1)：21-25.

CHEN Wei-ya, LIU Fang-fang. Applieation of geo-graphic information system teehnology in planing of water pollution control[J]. Jouranal of wuhan insti-tute of teehnology, 2013，35(1)：21-25.(in Chinese)

[2] 柳林，張繼賢，唐新明，等.LBS體系結(jié)構(gòu)及關(guān)鍵技術(shù)的研究[J].測繪科學(xué),2007,32(5)： 144-146.

LIU Lin, ZhANG Ji-xian, TANG Xin-ming, at al. LBS architecture and Research of key technologies[J]. Science of Surveying and Mapping,2007,32 (5):144-146 .(in Chinese)

[3] 顧運(yùn)筠.最短路徑搜索算法的幾種優(yōu)化改進(jìn)[J].計算機(jī)應(yīng)用與軟件，2008，25(4):246-247.

GU Yun-jun. Shortest path search algorithm several optimized and improved[J]. Computer Applications and Software,2008,25(4): 246 -247.(in Chinese)

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

LIU Hao, BAO Yuan-lv.The application of the A*algorithm searching the optimal vector path map[J]. Computer Simulation, 2008,25(4): 253-257.(in Chinese)

[5] 陳和平，張前哨.A*算法在游戲地圖尋徑中的應(yīng)用與實現(xiàn)[J].計算機(jī)應(yīng)用與軟件,2005，22(12):118-120.

CHEN He-ping, Zhang Qian-shao. Application and Implementation of the A*algorithm pathfinding in game maps[J]. Computer Applications and Software, 2005, 22(12):118-120.(in Chinese)

[6] 史輝，曹聞，朱述龍，等.A*算法的改進(jìn)及其在路徑規(guī)劃中的應(yīng)用[J].測繪與空間地理信息,2009，32(6): 208-211.

SHI Hui, CAO Wen, ZHU Shu-long, et al. A*algorithm and its application in path planning[J]. Geomatics & Spatial Information,2009,32 (6): 208-211.(in Chinese)

[7] 朱福喜,傅建明.人工智能原理[M]. 武漢：武漢大學(xué)出版社，2002.

ZHU Fu-xi, FU Jian-ming. Principle of artificial intelligence[M]. Wuhan: Wuhan University press, 2002.(in Chinese)

[8] 龔劬.圖論與網(wǎng)絡(luò)最優(yōu)化算法[M].重慶：重慶大學(xué)出版社，2009.

GONG Qu. Graph theory and network optimization algorithms[M]. Chongqing: Chongqing University Press,2009.(in Chinese)

[9] 魯統(tǒng)偉，林芹，李熹，等.記憶運(yùn)動方向的機(jī)器人避障算法[J].武漢工程大學(xué)學(xué)報，2013，35(4)：66-71.

LU Tong-wei, LIN Qin, LI Xi, et al. Obestacle avoidance algorithm of robot based on recording moue direction. Jouranal of Wuhan instute of technology，2013，35(4)：66-71.(in Chinese)