王 亞，任 燕，夏林元

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

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

交通運輸網絡是對提供物資輸送且具有點線連通的網狀地物的模型簡化.節(jié)點實體、弧段實體及網絡拓撲關系構成交通運輸網絡的基本模型要素.交通運輸網絡分析最常見的應用場景是交通運輸網絡的最短（或最優(yōu)）路徑分析.

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

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

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

1 交通運輸網絡的二叉堆數據結構表示和算法改進

1.1 交通運輸網絡的最短路徑算法分析

本文首先結合圖論的概念對交通運輸網絡進行分析.在圖論中，圖被定義為

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

根據以上分析可將交通運輸網絡（以下簡稱網絡）定義為

式中，V為網絡G中節(jié)點實體的集合，E為網絡中弧段實體的集合，R1為G上的禁行弧段的集合，R2為G上的禁行連續(xù)弧段的集合.

1.1.1 Dijkstra 算法

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

在交通運輸網絡中，Dijkstra 算法的運算邏輯如下：

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

式中，L為上一弧段到起始弧段的路徑長度函數，T為當前弧段到起始弧段的路徑長度函數.

實現Dijkstra 算法的具體步驟如下：

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

步驟2求時對應的T(er)，令L(er)=T(er).

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

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

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

1.1.2 A?算法

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

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

1.2 交通運輸網絡的二叉堆索引結構

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

表1 交通運輸網絡的數據結構操作效率比較Table 1 Comparison for efficiency of transportation network data structure

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

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

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

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

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

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

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

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

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

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

圖3 二叉堆交通運輸網絡數據結構Figure 3 Binary heap data structure of transportation network

1.3 基于二叉堆的Dijkstra 改進算法

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

策略1采用二叉堆的索引結構提高弧段查詢效率.

策略2按Double-Float-int 的順序簡化數據類型，從而降低計算耗時.

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

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

1.4 基于二叉堆的A?改進算法

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

策略1采用二叉堆的索引結構提高弧段查詢效率.

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

策略2按Double-Float-int的順序簡化數據類型，從而降低計算耗時.

策略3按開平方根-乘除-加減的順序簡化運算類型，從而降低計算耗時.

策略4減少搜索空間.

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

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

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

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

2 實驗與分析

2.1 實驗環(huán)境及數據

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

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

2.2 實驗結果與分析

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

表2 Dijkstra 算法和A?算法改進的實驗結果Table 2 Results of improvement for Dijkstra and A?algorithms

圖5為部分計算結果地圖顯示.

圖5 部分實驗結果地圖顯示Figure 5 Map display of experimental results

3 結 語

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