利用堆排序優(yōu)化路徑搜索效率的分析

孫玉昕,章 瑾

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

0 引 言

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

1 實(shí)驗(yàn)部分

1.1 算法選擇

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

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

A*算法的核心計(jì)算公式表示為

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

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

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

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

1.2 優(yōu)化分析

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

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

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

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

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

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

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

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

2 結(jié)果與討論

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語(yǔ)

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

致謝

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

參考文獻(xiàn)：

[1] 陳偉亞，劉芳芳.地理信息系統(tǒng)在水污染控制規(guī)劃中的應(yīng)用[J].武漢工程大學(xué)學(xué)報(bào)，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].測(cè)繪科學(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ì)算機(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ì)算機(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)用與實(shí)現(xiàn)[J].計(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].測(cè)繪與空間地理信息,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)動(dòng)方向的機(jī)器人避障算法[J].武漢工程大學(xué)學(xué)報(bào)，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)