1、迪克斯特林算法的改進及在路線規(guī)劃中的應(yīng)用摘要：為了提高路網(wǎng)路線規(guī)劃的效率，許多專家學(xué)者對此進行了一些研究。Dijk stra算法是一個研究熱點。在兩點之間尋找一個最佳路徑時迪克斯特拉算法也有 自己的缺點，但它仍具有無可替代的優(yōu)勢。通過對經(jīng)典Dijk stra算法優(yōu)勢和劣 勢的分析，我們可以發(fā)現(xiàn)，主要缺點可以概括為兩點：存儲結(jié)構(gòu)和搜索區(qū)域。因 此，本文改進了這兩點，即數(shù)據(jù)存儲結(jié)構(gòu)和限制算法搜索區(qū)域的改進。通過分析 實驗結(jié)果獲得其有效性。關(guān)鍵詞：迪克斯特拉算法；道路網(wǎng)絡(luò)；路線規(guī)劃；存儲結(jié)構(gòu)；受限搜索區(qū)域I引言基于拓撲結(jié)構(gòu)的道路網(wǎng)絡(luò)，路線規(guī)劃是為車輛運行期間到達目的地而進行的 一種搜索最佳路徑的過程

2、以及車輛導(dǎo)航系統(tǒng)中最短路徑問題的一種具體應(yīng)用。迪 克斯特拉算法是在圖中搜索最短路徑最經(jīng)典最成熟的算法，然而，該算法具有較 高的時間復(fù)雜度以及要占有較大的存儲空間。為了克服迪克斯特拉算法的這些缺 點，專家學(xué)者也相應(yīng)做了大量的研究，他們的研究成果有各自的特點和優(yōu)點，但 相關(guān)算法的理論基礎(chǔ)是迪克斯特拉算法，結(jié)合實際交通網(wǎng)絡(luò)的分布特性，此論文 改進了經(jīng)典的迪克斯特拉算法以減少時間復(fù)雜度和存儲空間，和減少算法的搜索 規(guī)模，以此提高算法的運行效率。II存儲結(jié)構(gòu)A 存儲結(jié)構(gòu)的改進運用圖片說明存儲結(jié)構(gòu)的改進原則，如圖片1所示，采用鄰接矩陣存儲迪克 斯特拉算法的數(shù)據(jù)，圖片2顯示各節(jié)點之間拓撲關(guān)系的鄰接矩陣的結(jié)構(gòu)

3、，采用一 個10X10的矩陣來存儲點與點之間的拓撲關(guān)系，行與列同等數(shù)目。矩陣xi,xj 的值對應(yīng)于節(jié)點i和j之間的權(quán)值，當(dāng)源節(jié)點和末節(jié)點是同一個節(jié)點時，權(quán)值為 0，兩節(jié)點之間無直接路徑時權(quán)值為8。此矩陣含有大量的0和8,這也增加了 無效路徑的數(shù)目并占有了存儲的大量空間。因此從時間和空間的角度來看是不科02880288888388204888832884038888888830528838888504888888824038888888830481338888408882838888058888881850圖片2,鄰接矩陣關(guān)于上面提到存儲模式，通過減少不必要的0和8來壓縮數(shù)據(jù)存儲空間，用 鄰接表

4、來存儲數(shù)據(jù)。用表數(shù)組MGraph來表示存儲矩陣G，鄰接矩陣的每一行用單一的連接列表 來表示，鏈接表中只存儲非8元素。每個節(jié)點有兩個元素，一個是列值，另一個 是權(quán)值。圖3表示圖1的存儲方式：每個點到源點的最短距離存儲在一維數(shù)組D中。前一個節(jié)點存儲在一維數(shù)組P中。參與比較的節(jié)點存儲在一個輔助的雙向鏈表中。算法步驟如下：步驟1，和節(jié)點v0直接相連的節(jié)點的D(vi)將被初始化為其權(quán)值，其余的為 計算機所允許的最大值。步驟2,和v0直接相連的節(jié)點被添加到路徑列表中。步驟3,找出具有最小權(quán)值的節(jié)點w，并在路線中刪除w，如果剩余節(jié)點是0， 就結(jié)束。步驟4,修改最短路徑，圖G中和節(jié)點w直接相連的其他節(jié)點之間比

5、較Dvi 和D (w) +s(w,vi)，如果Dvi的值比D ( w) +s(w,vi)的值小或者Dvi的值為8, 把vi加入到路徑中。P(vi)的前一個節(jié)點設(shè)置為w,最短路徑被修改為P(vi)= D (w) +s(w,vi)。然后重復(fù)步驟2。B復(fù)雜度分析空間復(fù)雜度的分析因為采用列表數(shù)組MGraph，其空間復(fù)雜度是O(T)，T是圖的邊的數(shù)目。在 最糟糕的情況下，如果T=n2,那么空間復(fù)雜度就為O(n2)。時間復(fù)雜度的分析存儲結(jié)構(gòu)改進后，實施算法四步驟的時間復(fù)雜度如下：步驟1的時間復(fù)雜度為O(n)；步驟2的時間復(fù)雜度為O(n)；對于步驟3,第一循環(huán)的數(shù)目就是和v直接相連的節(jié)點數(shù)目，即n1。和首

6、次發(fā)現(xiàn)的且和v的距離為8的節(jié)點直接相連的節(jié)點數(shù)目加上n-1即可得到第二 循環(huán)的數(shù)目。直到節(jié)點數(shù)目為0即可得出分析結(jié)論，然后結(jié)束。1 最糟糕的情況是， 節(jié)點v和每個節(jié)點都有聯(lián)系，其循環(huán)數(shù)目相應(yīng)的就是(n-1) , (n-2)，1，相 應(yīng)的時間復(fù)雜度就是(n-1) + (n-2) +1,即0(皿)。步驟4的時間復(fù)雜度是0(T),在最糟糕的情況下，如果T=n2，那么空間復(fù)雜 度就為0(n2)。因此，存儲結(jié)構(gòu)改進后的算法的時間復(fù)雜度是max0(n),0(T),0(n2),即0(n2)，時間復(fù)雜度是古典的迪克斯特拉算法相同。但是都市路線網(wǎng)絡(luò)的節(jié)點比較多，而且路線網(wǎng)絡(luò)所對應(yīng)的有向圖是不完整 的，節(jié)點的度小

7、于5個，所以Tn2，在這種情況下，改進后的存儲結(jié)構(gòu)非常實 用而且有效，消除了存儲冗余的冗余計算。III搜索區(qū)域A受限的搜索區(qū)域因為經(jīng)典的迪克斯特拉算法是一種全面的搜索過程，所以是肯定有冗余的， 根據(jù)迪克斯特拉算法的特點以及實際道路網(wǎng)絡(luò)的空間分布特征，算法必然會限制 搜索區(qū)域，因為兩點之間直線距離是最短的，當(dāng)我們規(guī)劃實際道路網(wǎng)絡(luò)的時候， 起始節(jié)點與終止節(jié)點之間通常是無法直達的，即兩點之間最終實際的最短路徑通 常是兩側(cè)的連接線，一般都在其附近。如果兩點之間僅僅只有一條邊，此邊本身 就是最短路徑，然而，有時兩點附近可能存在距離較短的其他路徑，也就是說， 為了進入右行車道，車輛會行駛在此路線。C圓形區(qū)

8、域P黑色粗線環(huán)繞的區(qū)域S起始節(jié)點 D一終止節(jié)點RS到D的歐氏距離 R1小矩形 R2大矩形T1閾值(從L1，L2到D)T2閾值(兩個閾值之間的距離)圖片4 經(jīng)典的dijkstra算法的比較示意圖及受限搜索區(qū)域算法圖片4顯示，為了尋找從起始節(jié)點S到終止節(jié)點D的最短路徑，一個dijkstra算 法理論搜索區(qū)域是一個圓形區(qū)域。，圓心是$，半徑是R。受限搜索區(qū)域算法的 理論搜索區(qū)域是邊界R1，對角線是S到D的那條線(當(dāng)S到D的那條線是水平 或垂直的時候，就有一個直線片段)。同時，考慮到有其他路徑，R1的每一邊都 可以延伸到T2邊界之外，以此形成一個大的矩形r2, l1和L2形成受限的搜索區(qū) 域以切割矩形

9、R2，L1和L2是平行于直線片段SD的兩條直線，距離是T1，如圖 4所示，搜索區(qū)域P是由封閉的粗線組成。B搜索區(qū)域分析經(jīng)典的dijkstra算法的搜索區(qū)域是A1=nR2；受限搜索區(qū)域算法的搜索區(qū)域是A/2T1 R+占T2因為搜索節(jié)點和搜索區(qū)域是匹配的，相應(yīng)的它們的時間復(fù)雜度是O(A2)和1O(A22)。通常T1，T2相應(yīng)的是較小的常數(shù)，因此，時間復(fù)雜度的比例大約可以表 示為 O(A 2)/O(A 2) 2A2 /A2QR4/R2=R2。通過比較，2我們可以發(fā)2現(xiàn)受限搜索區(qū)域算法的搜索區(qū)域比古典dijkstra算 法的搜索區(qū)域要小。隨著道路網(wǎng)絡(luò)規(guī)模的增大以及鄰近節(jié)點距離的加大，時間復(fù) 雜度的差異

10、將更加明顯，因此，必定限制搜索區(qū)域的算法經(jīng)改進后，將減少算法 搜索的規(guī)模，減小其復(fù)雜度，提高系統(tǒng)的效率。W應(yīng)用實例和結(jié)果分析為了比較兩種算法的優(yōu)勢和劣勢，VC+實現(xiàn)了帶有3600節(jié)點的隨機公路網(wǎng) 絡(luò)(CPU:2.0； main memory:512M； OS:WINXP)古典dijkstra算法搜索區(qū)域的示意圖改進后的算法搜索區(qū)域的示意圖此論文只給出了一個搜索結(jié)果，從起始節(jié)點1974到目標(biāo)節(jié)點2689。古典 dijkstra算法的搜索結(jié)果在圖片5中給出，待搜索節(jié)點的數(shù)目是627；改進后的 搜索結(jié)果在圖片6中給出，待搜索的節(jié)點數(shù)目是243。黑色線條是相關(guān)算法的最短路徑，通過比較，我們可以發(fā)現(xiàn)最短

11、路徑是相同 的，但是古典dijkstra算法的搜索區(qū)域非常接近于一個圓形區(qū)域，而改進后的 算法的搜索區(qū)域更接近于一個矩形。下表中給出了 8組實驗數(shù)據(jù)，t1表示古典dijkstra算法的搜索時間；t2 表示改進后的算法的搜索時間；n1表示古典dijkstra算法搜索的節(jié)點數(shù)目；n2 表示改進后的算法搜索的節(jié)點的數(shù)目。起始節(jié)點目標(biāo)節(jié)點Dijkstra算法改進后的算法t2/t1(%)n2/n1(%)t1(s)n1t2(s)n2197426892.3656270.1562436.6038.60336751.4334860.0921836.4037.7068919802.8959740.2143527.

12、1036.10163235204.19813950.2935177.0037.10193832112.8779550.2123397.4035.50122233333.98515410.2775787.0037.5076928134.06114800.3375628.3038.10113729283.84612280.2794847.7039.40兩種算法的搜索結(jié)果從上表中的數(shù)據(jù)我們可以看出，被改進后的算法搜索的節(jié)點的數(shù)目大約是 古典dijkstra算法節(jié)點數(shù)目的1/3。改進后的算法的搜索時間大約是古典 dijkstra算法的1/10。因此，我們可以得出一個結(jié)論，實時路徑規(guī)劃明顯增強 了。不幸

13、的是，改進后的算法本身限制了搜索區(qū)域，可能算法有時候不能搜索真 正的最短路徑，只是一個相對較短的路徑，這是一個有缺陷的最短路徑算法，優(yōu) 化時降低了其精確度。但是在很多情況下，最短路徑是在矩形內(nèi)的，整體來說， 優(yōu)化算法的優(yōu)勢是顯而易見的，改進后的算法到達了優(yōu)化的目的。V結(jié)論此論文基于城市交通網(wǎng)絡(luò)空間分布特征并且結(jié)合古典dijkstra算法本身的 特點，降低了算法的搜索規(guī)模，提高了運行效率，結(jié)果顯示，算法的改進是合理 的有效的。參考文獻：趙譯林車輛定位與導(dǎo)航系統(tǒng)北京電子工業(yè)出版社1999陸峰最短路徑算法：分類和進展研究2001福蒙陰李繼鄧志宏限制搜索區(qū)域的分層路由規(guī)劃算法計算機輔 助設(shè)計與圖形學(xué)雜志2005蘇海