薩賢春，辛 赟，陳憲東，楊 超

(1.西安科技大學(xué)，陜西 西安710054;2.陜西省測(cè)繪地理信息局，陜西西安710054)

一、引 言

路徑分析是GIS中網(wǎng)絡(luò)分析的重要組成部分，其中最短路徑算法作為路徑分析的主要研究?jī)?nèi)容，已被應(yīng)用到諸如機(jī)器人運(yùn)動(dòng)設(shè)計(jì)(robot motion planning)、電網(wǎng)、高速公路建設(shè)、煤礦風(fēng)網(wǎng)解算及計(jì)算機(jī)網(wǎng)絡(luò)路由等各個(gè)方面［1］?，F(xiàn)有的最短路徑算法按照實(shí)現(xiàn)技術(shù)可分為標(biāo)號(hào)算法與代數(shù)算法兩大類。其中標(biāo)號(hào)算法使用比較廣泛，其代表的算法有最短優(yōu)先搜索算法Dijikstra、Floyd等，代數(shù)方法有矩陣乘法等［2］。目前所公認(rèn)的最好的求解最短路徑問題的方法是 1959年由 Dijkstra提出的標(biāo)號(hào)法，即Dijikstra算法。本文從蟻群思想出發(fā)，通過不同的數(shù)據(jù)結(jié)構(gòu)與標(biāo)記方式，設(shè)計(jì)并實(shí)現(xiàn)了一種最短路徑求解的新算法。假設(shè)從起點(diǎn)開始放出一群螞蟻，始終是爬行過程中花費(fèi)最少的一只在向前爬行，通過對(duì)每一次爬行過的節(jié)點(diǎn)和弧段進(jìn)行標(biāo)號(hào)的方法來確保該過程是最短優(yōu)先搜索策略，即搜索到的路徑為最短路徑。

二、算法描述

廣度優(yōu)先搜索屬于一種盲目搜索策略，是最簡(jiǎn)便的圖的搜索算法之一，也是很多重要的圖的算法原型。本文所采用的方法就是基于一種廣度優(yōu)先的最短優(yōu)先搜索思想。

1.算法思想

在一個(gè)賦權(quán)無向圖G(V，E，W)中，已知起始節(jié)點(diǎn)s與終止節(jié)點(diǎn)d，在起始節(jié)點(diǎn)處放置一群螞蟻(ants)，使得其中始終是爬行過程中花費(fèi)路徑值(mVal)最少的一只螞蟻在向前爬行(繁殖)，并對(duì)每只螞蟻爬行過的節(jié)點(diǎn)與弧段進(jìn)行標(biāo)記(isAnt)，若螞蟻在爬行的過程中遇到已經(jīng)標(biāo)記過的節(jié)點(diǎn)或弧段，則該螞蟻停止爬行并死亡(路徑死亡)。那么，所有螞蟻中最先爬到終止節(jié)點(diǎn)的，其爬過的路徑即為網(wǎng)絡(luò)G(V，E，W)中起始節(jié)點(diǎn)s到終止節(jié)點(diǎn)d的最短路徑。

2.數(shù)據(jù)結(jié)構(gòu)

網(wǎng)絡(luò)中存儲(chǔ)的主要要素為網(wǎng)絡(luò)節(jié)點(diǎn)、網(wǎng)絡(luò)弧段和空間拓?fù)潢P(guān)系。節(jié)點(diǎn)與弧段是基礎(chǔ)要素，是組成網(wǎng)絡(luò)的物理要素，而空間拓?fù)潢P(guān)系描述的是它們之間的關(guān)系。圖的拓?fù)潢P(guān)系存儲(chǔ)采用節(jié)點(diǎn)與邊數(shù)據(jù)結(jié)構(gòu)，在節(jié)點(diǎn)上附加記錄與之相連弧段的信息。與鄰矩陣的存儲(chǔ)方式相比，基于鄰近節(jié)點(diǎn)的拓?fù)潢P(guān)系存儲(chǔ)方法節(jié)省了內(nèi)存，可用于規(guī)模較大的網(wǎng)絡(luò)分析。本文網(wǎng)絡(luò)中具體節(jié)點(diǎn)結(jié)構(gòu)如下:

3.算法設(shè)計(jì)運(yùn)行過程

采用本文所述路徑搜索策略的最優(yōu)路徑算法流程如圖1所示。圖中路徑繁殖指的是:對(duì)原來的路徑向前擴(kuò)展一個(gè)未標(biāo)記過的弧段，路徑值增加該弧段的值。以s與d分別代表起點(diǎn)與終點(diǎn)，算法結(jié)束的條件為找到最短路徑或圖中的節(jié)點(diǎn)已經(jīng)被永久地標(biāo)記。

圖1 算法流程

以圖2為例，使用該算法求解從起點(diǎn)(29)到終點(diǎn)(6)的最短路徑。具體執(zhí)行步驟如下:

1)標(biāo)記起始節(jié)點(diǎn)29，初始化起始路徑為29—37、29—27、29—23、29—16，并標(biāo)記弧段 29—37、29—27、29—23、29—16。

2)因?yàn)楣?jié)點(diǎn)29已被標(biāo)記過，因此路徑29—37、29—27在擴(kuò)展時(shí)死亡。

3)對(duì)路徑列表中剩余的路徑進(jìn)行擴(kuò)展。在該網(wǎng)絡(luò)圖中首先繁殖路徑29—23。節(jié)點(diǎn)23未被標(biāo)記，因此標(biāo)記節(jié)點(diǎn) 23并擴(kuò)展，即 29—23—17、29—23—22、29—23—30、29—16;現(xiàn)在最短路徑為 29—16，對(duì)其進(jìn)行繁殖，即 29—16—14、29—16—17、29—16—9、29—23—22、29—23—17、29—23—30。其中29—23—22為最短繁殖，但由于23—22已經(jīng)被標(biāo)記過，因此該路徑死亡。同理由于16—14已被標(biāo)記，29—16—14 死亡。

擴(kuò)展當(dāng)前路徑列表中的29—16—9，擴(kuò)展后為29—16—9—7、29—16—9—10、29—16—9—2、29—16—17、29—23—17、29—23—30。依次類推，按照流程圖直到當(dāng)前的最短路徑的末尾節(jié)點(diǎn)為終止節(jié)點(diǎn)為止。最后的最短路徑結(jié)果為 29—16—9—10—11—12—13—6，與dijikstra路徑算法結(jié)果一致。

圖2

三、算法分析

1.算法證明

定義1:對(duì)于有向圖G(V，E，W)，Adj(vi)表示節(jié)點(diǎn)vi的出度弧段集合，即有向圖中以vi為起點(diǎn)的弧段集合。由文獻(xiàn)［3］可知，在一般GIS的網(wǎng)絡(luò)圖中，Adj(vi)的個(gè)數(shù)一般為2～5。

結(jié)論1:A為在執(zhí)行搜索的過程中產(chǎn)生的臨時(shí)路徑集合。存在 ai∈A，mVali為路徑集合 A{a1，a2，…，an}中最短路徑的路徑值。

結(jié)論2:對(duì)于路徑集合A，A中所有的路徑均為路徑的末尾節(jié)點(diǎn)至起始節(jié)點(diǎn)的最短路徑。

結(jié)論3:圖G(V，E，W)中從起始節(jié)點(diǎn)開始，每次進(jìn)行路徑繁殖的始終是路徑集合中值mVal最短且路徑的尾節(jié)點(diǎn)vi?P未被標(biāo)記過，因此最先到達(dá)終止節(jié)點(diǎn)的路徑即為最短路徑。

結(jié)論2的證明:在搜索過程中對(duì)于每一條路徑ai，其尾部節(jié)點(diǎn)到起始節(jié)點(diǎn)的距離di表示路徑ai的長度。由于在搜索過程中對(duì)擴(kuò)展過的節(jié)點(diǎn)與弧段進(jìn)行標(biāo)記，若在搜索過程中某一路徑擴(kuò)展時(shí)遇到的節(jié)點(diǎn)或弧段已被標(biāo)記過，則說明至該節(jié)點(diǎn)或該弧段有比當(dāng)前路徑更短的路徑，因此對(duì)該路徑擴(kuò)展一定不能得到最短路徑，該路徑死亡。根據(jù)結(jié)論2，一旦搜索至終止節(jié)點(diǎn)，則可以確定最短路徑，結(jié)論3得證。

算法證明過程如下:P={s}，T=V－P，P為標(biāo)記過的節(jié)點(diǎn)集合，T表示未標(biāo)記過的節(jié)點(diǎn)集合。根據(jù)起始點(diǎn)s初始化起始路徑集合A;標(biāo)記起始節(jié)點(diǎn)s，P={s}，T=V－P。

1)開始進(jìn)入循環(huán):對(duì)于路徑集合A{a1，a2，…，an}，若沒有從起點(diǎn)s至終點(diǎn)d路徑，則根據(jù)結(jié)論1有

2)對(duì) A{a1，a2，…，an}中每一條路徑值 mValk，取長度最短的路徑ai為其路徑值mVal;其他路徑值大于min Val。判斷該最短路徑的末尾節(jié)點(diǎn)vik是否為終止節(jié)點(diǎn)d，若是，則找到最短路徑，搜索停止，否則進(jìn)行步驟3)。

3)若路徑ai末端的節(jié)點(diǎn)vk∈P，則說明至該節(jié)點(diǎn)有比路徑ai更短的路徑，該路徑為非最短路徑，路徑死亡。若vk∈T，則標(biāo)記vk，使vk∈P。

4)根據(jù)結(jié)論3，對(duì)路徑ai進(jìn)行繁殖，設(shè)Adj(vk)中未被標(biāo)記過的弧段有m個(gè)，則原來的ai被繁殖為m條新路徑，繁殖后的新路徑的路徑值mVal增加加入路徑弧段的值wkj，使用繁殖后的路徑和未進(jìn)行繁殖的路徑更新路徑集合A，進(jìn)入下一次循環(huán)，直到找到最短路徑或A的個(gè)數(shù)為0為止。

2.算法效率分析

設(shè)k為n次路徑集合中路徑個(gè)數(shù)的平均值，k的大小與網(wǎng)絡(luò)規(guī)模的大小有關(guān)。從根據(jù)起點(diǎn)初始化的路徑集合開始，每次對(duì)候選路徑集合求最短路徑采用的是冒泡排序的方式，它的時(shí)間復(fù)雜度為k2;每次對(duì)集合中的最短路徑至少向前擴(kuò)展一個(gè)節(jié)點(diǎn)，擴(kuò)展至所有節(jié)點(diǎn)n的時(shí)間復(fù)雜度為nk;每次對(duì)最短路徑擴(kuò)展的時(shí)候，路徑末尾出度節(jié)點(diǎn)的個(gè)數(shù)k1約為2～5，那么對(duì)所有節(jié)點(diǎn)進(jìn)行擴(kuò)展的時(shí)間復(fù)雜度為nk1。因此，總的復(fù)雜度為O(nk2+nk+nk1)。

四、結(jié)束語

本文算法從蟻群思想出發(fā)，以最短優(yōu)先搜索為基礎(chǔ)，在路徑搜索過程中采用對(duì)節(jié)點(diǎn)與弧段標(biāo)號(hào)的方法確保每次進(jìn)行繁殖的路徑為所有路徑中最短的，從而保證搜索過程中從起點(diǎn)開始的路徑中首先到達(dá)終點(diǎn)的為最短路徑。筆者在主頻為2.20 GHz、內(nèi)存為2 GB、操作系統(tǒng)為Windows7的計(jì)算機(jī)上，使用C#對(duì)其運(yùn)行效率進(jìn)行了測(cè)試，結(jié)果見表1。

表1

與傳統(tǒng)的方法相比，該算法結(jié)構(gòu)簡(jiǎn)單，便于理解，執(zhí)行效率也不遜色，有一定的實(shí)用性。同時(shí)，本算法也支持并行計(jì)算。

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.2版.北京:清華大學(xué)出版社，1997.

［2］陸鋒.最短路徑算法:分類體系與研究進(jìn)展［J］.測(cè)繪學(xué)報(bào)，2001，30(3):269-275.

［3］夏松，韓用順.GIS中最短路徑算法的改進(jìn)實(shí)現(xiàn)［J］.測(cè)繪通報(bào)，2004(9):40-42.

［4］王明中，謝劍英，陳應(yīng)麟.一種新的Kth最短路徑搜索算法［J］.計(jì)算機(jī)工程與應(yīng)用，2004(30):49-89.

［5］司連法，王文靜.快速Dijkstra最短路徑優(yōu)化算法的實(shí)現(xiàn)［J］.測(cè)繪通報(bào)，2005(8):15-18.

［6］陳潔，陸鋒.交通網(wǎng)絡(luò)最短路徑標(biāo)號(hào)算法的實(shí)現(xiàn)與效率分析［J］.中國圖象圖形學(xué)報(bào)，2005，10(9):1134-1138.

［7］王臣杰，毛海城，楊得志.圖的節(jié)點(diǎn)-弧段聯(lián)合結(jié)構(gòu)表示法及其在GIS最優(yōu)路徑選取中的應(yīng)用［J］.測(cè)繪學(xué)報(bào)，2000，29(1):47-51.

［8］YUE Y.An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm［J］.Journal of Wuhan Technical University of Surveying and Mapping，1999，24(3):209-212.

［9］高松，陸鋒，段瀅瀅.一種基于雙向搜索的K則最優(yōu)路徑算法［J］.武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2008，33(4):418-421.

［10］徐業(yè)昌，李樹祥，朱建民.基于地理信息系統(tǒng)的最短路徑搜索算法［J］.中國圖象圖形學(xué)報(bào)，1998，3(1):39-42.