王 亞，任 燕，夏林元

1.遵義師范學(xué)院信息工程學(xué)院，貴州遵義563000

2.中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院，廣東廣州510275

交通運(yùn)輸網(wǎng)絡(luò)是對提供物資輸送且具有點(diǎn)線連通的網(wǎng)狀地物的模型簡化.節(jié)點(diǎn)實(shí)體、弧段實(shí)體及網(wǎng)絡(luò)拓?fù)潢P(guān)系構(gòu)成交通運(yùn)輸網(wǎng)絡(luò)的基本模型要素.交通運(yùn)輸網(wǎng)絡(luò)分析最常見的應(yīng)用場景是交通運(yùn)輸網(wǎng)絡(luò)的最短（或最優(yōu)）路徑分析.

在交通運(yùn)輸網(wǎng)絡(luò)的最短路徑算法研究中，基于道路交通網(wǎng)絡(luò)的研究是最廣泛的，文獻(xiàn)[1-2]對道路交通網(wǎng)絡(luò)的最短路徑算法按目標(biāo)向?qū)Ш蛯哟位瘍煞N類型進(jìn)行了討論.目標(biāo)導(dǎo)向方法主要是通過引導(dǎo)路徑的搜索方向來減少算法的搜索空間，該方法并不改變數(shù)據(jù)本身的性狀.層次化方法則通過道路網(wǎng)的等級屬性以及交叉口（可視為交通運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)）的連通性將一個(gè)網(wǎng)絡(luò)分割成為相互連通的多層次網(wǎng)絡(luò)，高層次的網(wǎng)絡(luò)弧段量依次變少，最低層次的網(wǎng)絡(luò)包含全部的弧段和節(jié)點(diǎn)實(shí)體，因此算法可以在不同的層次網(wǎng)絡(luò)間切換搜索路徑，從而降低搜索空間.上述文獻(xiàn)雖然給出了算法間的性能比較，但算法的實(shí)現(xiàn)效率跟實(shí)際所采用的數(shù)據(jù)結(jié)構(gòu)和內(nèi)容密切相關(guān)，而這些文獻(xiàn)并沒有進(jìn)行深入的研究.文獻(xiàn)[3]在有向帶權(quán)聯(lián)通圖的數(shù)據(jù)基礎(chǔ)上對Dijkstra 算法進(jìn)行了改進(jìn)，針對不聯(lián)通兩點(diǎn)可能形成死循環(huán)的問題設(shè)計(jì)了相應(yīng)的退出機(jī)制，并提出了如何求取最短路徑上節(jié)點(diǎn)的相鄰點(diǎn)的方法.該方法采用通用數(shù)據(jù)庫的方式來記錄圖結(jié)構(gòu)，類似于鄰接矩陣的實(shí)現(xiàn)方式.顯然，采用冗余的鄰接矩陣方式來實(shí)現(xiàn)Dijkstra 算法的運(yùn)算效率較低.文獻(xiàn)[4]對A?算法的估計(jì)函數(shù)進(jìn)行改進(jìn)，增加了一個(gè)從當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的歐氏距離估算過程.在具體實(shí)現(xiàn)過程中，該改進(jìn)算法采用了鄰接表進(jìn)行存儲(chǔ)并利用優(yōu)先級隊(duì)列來實(shí)現(xiàn).然而，采用歐氏距離作為A?算法的距離估算函數(shù)，其計(jì)算效率會(huì)明顯降低.文獻(xiàn)[5]指出，采用鄰接矩陣的方法存儲(chǔ)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)的空間復(fù)雜度為O(N2)（N為交通運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目）.以Dijkstra 算法為例，當(dāng)采用k叉堆、二項(xiàng)堆或Fibonacci 堆來實(shí)現(xiàn)時(shí)，其算法復(fù)雜度為O(MlgN)或O(M+NlnN)（M為交通運(yùn)輸網(wǎng)絡(luò)的弧段數(shù)目）.當(dāng)采用桶結(jié)構(gòu)基數(shù)堆實(shí)現(xiàn)時(shí)，在弧段權(quán)重為整數(shù)的條件下，算法復(fù)雜度為O(M+NlnC/ln lnC)（C為常數(shù)），而基數(shù)堆和Fibonacci 堆相結(jié)合的算法復(fù)雜度僅為O(M+NlnC).文獻(xiàn)[6-8]提出了一種基于模糊神經(jīng)網(wǎng)絡(luò)的最短路徑算法，利用神經(jīng)元間的并行性特征減少計(jì)算的迭代次數(shù)，從而取得優(yōu)于Dijkstra 算法和A?算法的計(jì)算效率，但文獻(xiàn)未提及A?算法作為比較基準(zhǔn)時(shí)應(yīng)該采用哪種估算函數(shù)來實(shí)現(xiàn)其計(jì)算過程.文獻(xiàn)[9-11]提出了動(dòng)態(tài)交通網(wǎng)絡(luò)的數(shù)學(xué)模型，并設(shè)計(jì)了考慮交叉口延時(shí)的動(dòng)態(tài)最短路徑算法，在Hadoop 的MapReduce 算法框架下實(shí)現(xiàn)了最短路徑并行計(jì)算算法.文獻(xiàn)[12-13]討論了基于不同交通工具的多約束條件的最短路徑算法，并對Dijkstra 算法進(jìn)行了相應(yīng)的改進(jìn).

綜合考慮主要的最短路徑算法，文獻(xiàn)[4,14-16]提及的Dijkstra 算法是目前應(yīng)用最廣泛的最短路徑算法，也是求單源、無負(fù)權(quán)最短路徑的較好選擇，其計(jì)算的時(shí)間復(fù)雜度為O(N2+M).在算法設(shè)計(jì)過程中，Dijkstra 算法計(jì)算了從源點(diǎn)到搜索空間內(nèi)所有其他節(jié)點(diǎn)的最短路徑，而在具體的算法實(shí)現(xiàn)中只需要考慮從源點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條最短路徑，因此該算法具有很大的改進(jìn)可能.Floyd 算法[17]在求多源、無負(fù)權(quán)邊的最短路徑時(shí)，用節(jié)點(diǎn)矩陣來表示圖，其時(shí)效性較差，時(shí)間復(fù)雜度O(N3).當(dāng)采用Bellman-Ford 算法[18]求取單源最短路徑時(shí)，可以對具有負(fù)權(quán)回路的圖進(jìn)行計(jì)算，時(shí)效性較好，時(shí)間復(fù)雜度為O(NM).A?算法[19-21]是解決圖中兩頂點(diǎn)之間最短路徑的一種最有效的啟發(fā)式直接搜索方法，該算法實(shí)際上可看作是在Dijkstra 算法基礎(chǔ)上引入了一個(gè)當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離估算值.因?yàn)楣浪阒稻哂幸龑?dǎo)作用，算法并不需要搜索所有的鄰接節(jié)點(diǎn)，而是直接沿估算值的方向逼近目標(biāo)節(jié)點(diǎn)，所以搜索速度明顯加快.

基于上述分析，本文引入二叉堆索引結(jié)構(gòu)對Dijkstra 算法和A?算法進(jìn)行了改進(jìn)，提高了交通運(yùn)輸網(wǎng)絡(luò)存儲(chǔ)結(jié)構(gòu)的讀取效率，并通過數(shù)據(jù)類型的低精度損耗簡化和運(yùn)算類型的簡化提高了算法的計(jì)算效率，尤其對A?算法的估計(jì)函數(shù)進(jìn)行了計(jì)算方式的優(yōu)化，有效降低了搜索空間，從而提高了兩種算法的整體計(jì)算效率.

1 交通運(yùn)輸網(wǎng)絡(luò)的二叉堆數(shù)據(jù)結(jié)構(gòu)表示和算法改進(jìn)

1.1 交通運(yùn)輸網(wǎng)絡(luò)的最短路徑算法分析

本文首先結(jié)合圖論的概念對交通運(yùn)輸網(wǎng)絡(luò)進(jìn)行分析.在圖論中，圖被定義為

式中，V為頂點(diǎn)的非空有窮集合V=(v1,v2,···,vn)，E為邊的集合E=(e1,e2,···,en).根據(jù)邊是否有序可將圖分為有向圖和無向圖.在地理信息系統(tǒng)（geographic information system,GIS）網(wǎng)絡(luò)中，資源的輸送是具有方向性的，即使在道路交通網(wǎng)絡(luò)中，雙向通行的道路也可以簡化為方向相逆的兩條有向道路.因此，交通運(yùn)輸網(wǎng)絡(luò)可以視為有向圖，圖中的頂點(diǎn)即為交通運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)實(shí)體，圖中的邊即為交通運(yùn)輸網(wǎng)絡(luò)的弧段實(shí)體.交通運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)實(shí)體和弧段實(shí)體的網(wǎng)絡(luò)拓?fù)潢P(guān)系可以用有向圖中頂點(diǎn)的出度以及從頂點(diǎn)出發(fā)的邊的集合表示.交通運(yùn)輸網(wǎng)絡(luò)的約束包括兩種：某條邊的禁行和相互連接的多條邊的禁行.以實(shí)際情況為例，某條道路由于施工禁止通行就屬于第1 種約束，路口禁止掉頭就屬于第2 種約束.這兩種約束在圖論里并沒有相關(guān)概念可以描述，本文將第1 種約束用邊的禁行子集表示，將第2 種約束用連續(xù)邊的禁行子集表示.在具體應(yīng)用中，連續(xù)邊可以采用鏈表結(jié)構(gòu)實(shí)現(xiàn).

根據(jù)以上分析可將交通運(yùn)輸網(wǎng)絡(luò)（以下簡稱網(wǎng)絡(luò)）定義為

式中，V為網(wǎng)絡(luò)G中節(jié)點(diǎn)實(shí)體的集合，E為網(wǎng)絡(luò)中弧段實(shí)體的集合，R1為G上的禁行弧段的集合，R2為G上的禁行連續(xù)弧段的集合.

1.1.1 Dijkstra 算法

根據(jù)以上定義，同時(shí)考慮到最終的計(jì)算結(jié)果是以連續(xù)弧段組成的路線來表示的，于是可以將交通運(yùn)輸網(wǎng)絡(luò)中兩節(jié)點(diǎn)實(shí)體之間的最短路徑計(jì)算簡化為兩弧段實(shí)體之間的最短路徑：給定起始弧段s ∈E和目標(biāo)弧段t ∈E，計(jì)算s弧段到t弧段的最短路徑p.

在交通運(yùn)輸網(wǎng)絡(luò)中，Dijkstra 算法的運(yùn)算邏輯如下：

令起始弧段的集合s={ei}，將初始化弧段設(shè)為e1，剩余網(wǎng)絡(luò)弧段集合s?={e2,e3,···,en}，則有第1 條弧段到第1 條弧段（即其本身）的初始化最短路徑為0，起始弧段到終點(diǎn)弧段的初始化最短路徑為無窮大，即

式中，L為上一弧段到起始弧段的路徑長度函數(shù)，T為當(dāng)前弧段到起始弧段的路徑長度函數(shù).

實(shí)現(xiàn)Dijkstra 算法的具體步驟如下：

步驟1對ej ∈s?，ej R1，求min{T(ej),L(ei)+lij}=T(ej).

步驟2求時(shí)對應(yīng)的T(er)，令L(er)=T(er).

步驟3若er=et，則已找到e1到et的最短距離L(er)，否則令i=k，從s?中刪除ej后轉(zhuǎn)步驟1，這樣經(jīng)過有限次迭代就可求出s到t的最短路徑.

經(jīng)分析可知Dijkstra 算法的基本思想是：從起始節(jié)點(diǎn)開始循環(huán)計(jì)算源節(jié)點(diǎn)到未標(biāo)記節(jié)點(diǎn)的最短路徑，直到找出所有未標(biāo)記節(jié)點(diǎn)到起始節(jié)點(diǎn)的最短路徑為止，其搜索范圍可近似為以起始節(jié)點(diǎn)為圓心的一個(gè)圓形區(qū)域，如圖1所示.

圖1 Dijkstra 算法的搜索空間Figure 1 Searching space of Dijkstra algorithm

1.1.2 A?算法

交通運(yùn)輸網(wǎng)絡(luò)中A?算法邏輯和具體步驟與Dijkstra 算法相似，在此不再贅述.A?算法可以視為Dijkstra 算法的一種特例，其特殊之處在于A?算法在計(jì)算最短路徑時(shí)增加了當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離（或權(quán)重）估算函數(shù)Dj→t.因此，在搜索過程中，A?算法會(huì)沿著距離估算最小的方向逼近目標(biāo)節(jié)點(diǎn)，其搜索范圍可近似為以源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)連線為中軸的橢圓形區(qū)域，如圖2所示.

圖2 A?算法的搜索空間Figure 2 Searching space of A?algorithm

1.2 交通運(yùn)輸網(wǎng)絡(luò)的二叉堆索引結(jié)構(gòu)

Dijkstra 算法的關(guān)鍵步驟在于循環(huán)地從未標(biāo)記節(jié)點(diǎn)中選取權(quán)重最小的弧段.因此，如何組織節(jié)點(diǎn)及其相關(guān)弧段的數(shù)據(jù)結(jié)構(gòu)，使得每次都能最快找到未標(biāo)記節(jié)點(diǎn)中權(quán)重最小的弧段成了實(shí)現(xiàn)算法的關(guān)鍵問題.Dijkstra 算法的搜索范圍可以看成以源節(jié)點(diǎn)為母節(jié)點(diǎn)向四周延伸的樹狀結(jié)構(gòu).此外，每次計(jì)算最短路徑的源節(jié)點(diǎn)各不相同，因而該樹狀結(jié)構(gòu)的母節(jié)點(diǎn)均不同，且母節(jié)點(diǎn)之下的子節(jié)點(diǎn)及其結(jié)構(gòu)也都不同，這意味著每次計(jì)算都要重新組織一次數(shù)據(jù)的索引結(jié)構(gòu).同理，A?算法雖然增加了估算函數(shù)，其基本搜索過程仍然是從源節(jié)點(diǎn)指向目標(biāo)節(jié)點(diǎn)的樹狀延伸過程.因此，無論是Dijkstra 算法還是A?算法，都可以考慮將其網(wǎng)絡(luò)數(shù)據(jù)的索引組織成樹狀結(jié)構(gòu).在道路交通網(wǎng)絡(luò)的應(yīng)用中，其網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)的是稀疏有向圖的特點(diǎn).每個(gè)節(jié)點(diǎn)的出度一般不超過5，大部分為2 或者3，因此采用二叉樹的索引結(jié)構(gòu)的表示方式能夠保證樹的平衡性.目前，在最短路徑搜索的研究中，最常見的幾種網(wǎng)絡(luò)數(shù)據(jù)組織結(jié)構(gòu)主要有鄰接矩陣、鄰接表、鏈表等.表1比較了幾種數(shù)據(jù)結(jié)構(gòu)的操作效率.從表1可以發(fā)現(xiàn)，二叉樹結(jié)構(gòu)在查找、插入和遍歷的效率方面優(yōu)于其他數(shù)據(jù)結(jié)構(gòu).

表1 交通運(yùn)輸網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)操作效率比較Table 1 Comparison for efficiency of transportation network data structure

根據(jù)上述分析，本文設(shè)計(jì)了如圖3所示的交通運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu).一個(gè)交通運(yùn)輸網(wǎng)絡(luò)由一個(gè)弧段數(shù)組和一個(gè)節(jié)點(diǎn)數(shù)組構(gòu)成，每個(gè)弧段類的主要屬性包括弧段ID、頭節(jié)點(diǎn)ID、尾節(jié)點(diǎn)ID、弧段權(quán)重、弧段在弧段數(shù)組里的位置.每個(gè)節(jié)點(diǎn)類的主要屬性包括節(jié)點(diǎn)ID、節(jié)點(diǎn)出度、以節(jié)點(diǎn)為出發(fā)點(diǎn)的第1 條弧段在弧段數(shù)組里的位置.弧段數(shù)組采用C++ 標(biāo)準(zhǔn)模板庫STL 的Vector 類實(shí)現(xiàn)，數(shù)組內(nèi)對所有弧段實(shí)行雙重初始排序，首先是以弧段的頭節(jié)點(diǎn)ID 進(jìn)行排序，其次是將相同頭節(jié)點(diǎn)的弧段依次排序.節(jié)點(diǎn)數(shù)組采用STL 的Map 類實(shí)現(xiàn)，Map 類的鍵（Key）為節(jié)點(diǎn)ID，值（Value）為節(jié)點(diǎn)對象.Map 內(nèi)部的節(jié)點(diǎn)對象無需排序，直接通過鍵訪問對應(yīng)的節(jié)點(diǎn)對象.一個(gè)交通運(yùn)輸網(wǎng)絡(luò)的連通性由弧段類的頭節(jié)點(diǎn)ID、尾節(jié)點(diǎn)ID 與節(jié)點(diǎn)類的節(jié)點(diǎn)ID的關(guān)聯(lián)實(shí)現(xiàn)，即頭節(jié)點(diǎn)ID 和尾節(jié)點(diǎn)ID 為弧段類的外鍵，節(jié)點(diǎn)ID 為節(jié)點(diǎn)類的鍵（Key）.

由于Dijkstra 算法和A?算法的搜索路徑類似于樹狀結(jié)構(gòu)，且常見交通運(yùn)輸網(wǎng)絡(luò)基本上呈現(xiàn)稀疏圖的特征，生成的二叉樹基本上是一棵完全二叉樹，可以保證操作不會(huì)形成O(N)的最壞結(jié)果.另外，在算法實(shí)現(xiàn)過程中頻繁使用最小數(shù)據(jù)的取出、已查詢數(shù)據(jù)的刪除、重排序等操作，因此采用二叉堆索引來實(shí)現(xiàn)交通運(yùn)輸網(wǎng)絡(luò)的索引是最佳方式.二叉堆的基本元素為弧段，弧段對象的權(quán)重為二叉堆的排序因子.

在圖3所示的交通運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)中，二叉堆采用C++ 標(biāo)準(zhǔn)模板庫STL 的Vector 類實(shí)現(xiàn).該二叉堆為小根堆，這意味著位于堆根節(jié)點(diǎn)的弧段對象的權(quán)重值最小，且堆中每一個(gè)位于父節(jié)點(diǎn)位置的弧段對象的權(quán)重值都小于位于子節(jié)點(diǎn)位置的弧段對象的權(quán)重值.根據(jù)算法需要，該二叉堆的基本操作包括：弧段對象的插入、上移、下移、彈出等.基本操作的時(shí)間復(fù)雜度在O(1)到O(lnN)之間.弧段對象的插入包括以下步驟：

步驟1將弧段對象壓入二叉堆；

步驟2將堆尾的弧段上移至正確的位置.

在上移的過程中，將插入的弧段對象從下到上依次與堆內(nèi)的各父節(jié)點(diǎn)位置的弧段進(jìn)行比較.若插入的弧段對象的權(quán)重小于當(dāng)前父節(jié)點(diǎn)位置的弧段的權(quán)重，則兩者交換位置；反之，退出上移過程.弧段對象的彈出過程分為以下步驟：

步驟1將二叉堆頭部的弧段對象取出；

步驟2將尾部的弧段對象放至堆頭并彈出堆尾；

步驟3將堆頭的弧段對象下移至正確位置.

下移的過程跟上移的過程相反.

圖3 二叉堆交通運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)Figure 3 Binary heap data structure of transportation network

1.3 基于二叉堆的Dijkstra 改進(jìn)算法

在1.2 節(jié)提及的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上，本文首先對Dijkstra 算法進(jìn)行改進(jìn)，包括以下2 個(gè)優(yōu)化策略：

策略1采用二叉堆的索引結(jié)構(gòu)提高弧段查詢效率.

策略2按Double-Float-int 的順序簡化數(shù)據(jù)類型，從而降低計(jì)算耗時(shí).

在二叉堆索引結(jié)構(gòu)下對Dijkstra 算法的改進(jìn)即優(yōu)化策略1 的實(shí)現(xiàn)如圖4所示.算法圍繞弧段構(gòu)建二叉小根堆，依次彈出二叉堆內(nèi)的弧段，再通過彈出的當(dāng)前弧段，取出當(dāng)前弧段所指向節(jié)點(diǎn)的所有出向弧段，依次計(jì)算每個(gè)出向弧段的新的總權(quán)重值.若新的總權(quán)重值小于出向弧段的原總權(quán)重值，則更新該出向弧段的總權(quán)重值，并將該出向弧段插入到二叉堆；若新的總權(quán)重值大于等于出向弧段的原總權(quán)重值，則繼續(xù)處理下一個(gè)出向弧段.當(dāng)前弧段的出向弧段處理完成后，算法返回并彈出二叉堆里的下一個(gè)弧段，再重復(fù)上述過程，直至遇到目標(biāo)節(jié)點(diǎn)或二叉堆為空.算法的最終步驟是沿目標(biāo)節(jié)點(diǎn)反向回溯得到從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑.在算法處理二叉堆彈出的每個(gè)弧段過程中，必須避開禁行弧段和禁行轉(zhuǎn)向，禁行弧段和禁行轉(zhuǎn)向即為交通運(yùn)輸網(wǎng)絡(luò)G中定義的R1和R2約束條件.禁行弧段為不可通行的弧段，如現(xiàn)實(shí)交通運(yùn)輸網(wǎng)絡(luò)中不可通行的路段.禁行轉(zhuǎn)向由多個(gè)弧段組成，如現(xiàn)實(shí)交通運(yùn)輸網(wǎng)絡(luò)中禁止左轉(zhuǎn)、禁止掉頭等交通策略.

在Dijkstra 算法中，優(yōu)化策略2 的實(shí)現(xiàn)對應(yīng)圖4中“計(jì)算出向弧段i的總權(quán)重值”，采用可容忍誤差將弧段數(shù)組中所有弧段的權(quán)重值從Double 或Float 數(shù)據(jù)類型轉(zhuǎn)換為int 值，可以提高計(jì)算速度.

1.4 基于二叉堆的A?改進(jìn)算法

A?算法包括以下優(yōu)化策略：

策略1采用二叉堆的索引結(jié)構(gòu)提高弧段查詢效率.

圖4 基于二叉堆的Dijkstra 算法Figure 4 Dijkstra algorithm based on binary heap

策略2按Double-Float-int的順序簡化數(shù)據(jù)類型，從而降低計(jì)算耗時(shí).

策略3按開平方根-乘除-加減的順序簡化運(yùn)算類型，從而降低計(jì)算耗時(shí).

策略4減少搜索空間.

在A?算法的改進(jìn)過程中，優(yōu)化策略1 的實(shí)現(xiàn)與Dijkstra 算法的過程相同，即圖4所示的算法過程.采用二叉堆的索引結(jié)構(gòu)可以比采用其他數(shù)據(jù)結(jié)構(gòu)更高效地獲取當(dāng)前弧段的下一個(gè)連接弧段.優(yōu)化策略2 和3 的實(shí)現(xiàn)步驟對應(yīng)圖4的“計(jì)算出向弧段i的新的總權(quán)重值”.在A?算法中，出向弧段i的新的總權(quán)重值的計(jì)算不同于Dijkstra 算法中的計(jì)算方式.在Dijkstra 算法中，出向弧段i的新的總權(quán)重值等于當(dāng)前弧段的總權(quán)重值與出向弧段自身的權(quán)重值之和；在A?算法中，出向弧段i的新的總權(quán)重值等于當(dāng)前弧段的總權(quán)重值、出向弧段自身的權(quán)重值、當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離估算Dj→t之和，其中Dj→t的公式為

式中，(xt,yt)為目標(biāo)節(jié)點(diǎn)坐標(biāo)，(xj,yj)為當(dāng)前節(jié)點(diǎn)坐標(biāo)，Dj→t為目標(biāo)節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)之間的歐氏距離.

在實(shí)際計(jì)算中，由于歐氏距離運(yùn)用了2 次平方和1 次開平方根計(jì)算，計(jì)算耗時(shí)較大，此外Dj→t只是一個(gè)估算值，只需大致接近當(dāng)前節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)t的實(shí)際計(jì)算值即可.因此，本文采用的距離估算公式為

至此可以實(shí)現(xiàn)優(yōu)化策略3.另外在基本數(shù)據(jù)中，采用可容忍誤差將節(jié)點(diǎn)數(shù)組的坐標(biāo)值及弧段數(shù)組中所有弧段的權(quán)重值從Double 或Float 數(shù)據(jù)類型有損轉(zhuǎn)換為int 值，從而實(shí)現(xiàn)了優(yōu)化策略2.同時(shí)，由于距離估算Dj→t的存在，在算法實(shí)現(xiàn)搜索運(yùn)算的過程中會(huì)沿著當(dāng)前節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)t的方向快速前進(jìn)，有效地減少了搜索空間，從而實(shí)現(xiàn)了策略4.

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

根據(jù)以上思路，本文采用Visual C++分別實(shí)現(xiàn)了Dijkstra 算法和A?算法的改進(jìn).算法的實(shí)現(xiàn)環(huán)境如下：實(shí)驗(yàn)數(shù)據(jù)為全國道路交通骨干網(wǎng)以及上海市道路交通網(wǎng)共59 507 個(gè)節(jié)點(diǎn)、163 099 個(gè)弧段，運(yùn)行硬件環(huán)境為CPU 2.3 GHz 主頻、4G 內(nèi)存、120 GB 硬盤.

分析數(shù)據(jù)內(nèi)容可知，每個(gè)節(jié)點(diǎn)實(shí)體的平均出度為163 099÷59 507≈2.74，數(shù)據(jù)呈現(xiàn)稀疏圖的特征，形成的二叉樹基本相當(dāng)于一棵完全二叉樹.由于出度略大于2，二叉樹的深度lnN比較合適，采用二叉堆來實(shí)現(xiàn)數(shù)據(jù)索引可以最大化其搜索效率.實(shí)驗(yàn)采用了4 組大范圍的最短路徑搜索例子，與組內(nèi)起終點(diǎn)位置相同.每組的第1 個(gè)實(shí)驗(yàn)采用傳統(tǒng)的FIFO 隊(duì)列實(shí)現(xiàn)Dijkstra算法，并將其作為比較基準(zhǔn)；其他3 個(gè)實(shí)驗(yàn)都采用二叉堆索引實(shí)現(xiàn)算法.A?算法采用了兩種距離估計(jì)函數(shù)，D1代表采用的距離估計(jì)函數(shù)為式(3)；D2代表算法所采用的距離估計(jì)函數(shù)為式(4).

2.2 實(shí)驗(yàn)結(jié)果與分析

從數(shù)據(jù)結(jié)果觀察，同樣是Dijkstra 算法，采用二叉堆的數(shù)據(jù)索引結(jié)構(gòu)與采用傳統(tǒng)FIFO 隊(duì)列的數(shù)據(jù)結(jié)構(gòu)相比，算法的耗時(shí)有明顯減少，這證明了優(yōu)化策略1 是有效的.在A?算法的應(yīng)用中，采用D1函數(shù)與D2函數(shù)相比，搜索空間有顯著減少，耗時(shí)明顯降低.由此可得到兩個(gè)結(jié)論：1）在A?算法中，選擇合適的距離估計(jì)函數(shù)可以顯著減少算法的搜索空間，明顯降低算法耗時(shí)，這證明優(yōu)化策略4 是有效的；2）D1函數(shù)采用了開平方根的復(fù)雜計(jì)算，從而增加了算法的耗時(shí)，且其增加的時(shí)間超過了因搜索空間減少而減少的計(jì)算時(shí)間，這也從側(cè)面證明了簡化數(shù)據(jù)類型和操作類型的優(yōu)化策略2 和3 是有效的.

表2 Dijkstra 算法和A?算法改進(jìn)的實(shí)驗(yàn)結(jié)果Table 2 Results of improvement for Dijkstra and A?algorithms

圖5為部分計(jì)算結(jié)果地圖顯示.

圖5 部分實(shí)驗(yàn)結(jié)果地圖顯示Figure 5 Map display of experimental results

3 結(jié) 語

本文針對交通運(yùn)輸網(wǎng)絡(luò)設(shè)計(jì)了二叉堆索引結(jié)構(gòu)，并在此基礎(chǔ)上實(shí)現(xiàn)了計(jì)算最短路徑的Dijkstra 算法和A?算法，在算法的實(shí)現(xiàn)過程中采用了多種優(yōu)化策略.首先，通過二叉堆索引的應(yīng)用提高了交通運(yùn)輸網(wǎng)絡(luò)存儲(chǔ)結(jié)構(gòu)中點(diǎn)線及其網(wǎng)絡(luò)拓?fù)潢P(guān)系的查詢效率.其次，將點(diǎn)線坐標(biāo)進(jìn)行了低精度損耗的數(shù)據(jù)類型簡化，提高了算法計(jì)算效率.此外，對A?算法中當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離估計(jì)函數(shù)進(jìn)行了計(jì)算方式的優(yōu)化，有效降低了搜索空間，從而提高了兩種算法的整體計(jì)算效率.最后，通過編程實(shí)現(xiàn)了二叉堆索引結(jié)構(gòu)和算法的優(yōu)化策略，并隨機(jī)抽取了多組實(shí)驗(yàn).實(shí)現(xiàn)結(jié)果顯示，對Dijkstra 算法改進(jìn)后的計(jì)算速度提高了7 倍以上，對A?算法改進(jìn)后的計(jì)算速度提高了200 倍以上，從而證明了本文的改進(jìn)和優(yōu)化策略確實(shí)達(dá)到了預(yù)期效果.