交通運輸網(wǎng)絡(luò)的二叉堆索引及路徑算法優(yōu)化

王 亞，任 燕，夏林元

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

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

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

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

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

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

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

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

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

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

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

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

1.1.1 Dijkstra 算法

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

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

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

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

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

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

步驟2求時對應(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é)點開始循環(huán)計算源節(jié)點到未標(biāo)記節(jié)點的最短路徑，直到找出所有未標(biāo)記節(jié)點到起始節(jié)點的最短路徑為止，其搜索范圍可近似為以起始節(jié)點為圓心的一個圓形區(qū)域，如圖1所示.

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

1.1.2 A?算法

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

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

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

Dijkstra 算法的關(guān)鍵步驟在于循環(huán)地從未標(biāo)記節(jié)點中選取權(quán)重最小的弧段.因此，如何組織節(jié)點及其相關(guān)弧段的數(shù)據(jù)結(jié)構(gòu)，使得每次都能最快找到未標(biāo)記節(jié)點中權(quán)重最小的弧段成了實現(xiàn)算法的關(guān)鍵問題.Dijkstra 算法的搜索范圍可以看成以源節(jié)點為母節(jié)點向四周延伸的樹狀結(jié)構(gòu).此外，每次計算最短路徑的源節(jié)點各不相同，因而該樹狀結(jié)構(gòu)的母節(jié)點均不同，且母節(jié)點之下的子節(jié)點及其結(jié)構(gòu)也都不同，這意味著每次計算都要重新組織一次數(shù)據(jù)的索引結(jié)構(gòu).同理，A?算法雖然增加了估算函數(shù)，其基本搜索過程仍然是從源節(jié)點指向目標(biāo)節(jié)點的樹狀延伸過程.因此，無論是Dijkstra 算法還是A?算法，都可以考慮將其網(wǎng)絡(luò)數(shù)據(jù)的索引組織成樹狀結(jié)構(gòu).在道路交通網(wǎng)絡(luò)的應(yīng)用中，其網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)的是稀疏有向圖的特點.每個節(jié)點的出度一般不超過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 交通運輸網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)操作效率比較Table 1 Comparison for efficiency of transportation network data structure

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

策略4減少搜索空間.

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

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

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

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

2 實驗與分析

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

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

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

2.2 實驗結(jié)果與分析

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

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

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

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

3 結(jié) 語

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