交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new

ID:34423183

大?。?89.25 KB

頁數(shù):5頁

時間:2019-03-06

交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new_第1頁
交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new_第2頁
交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new_第3頁
交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new_第4頁
交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new_第5頁
資源描述:

《交通限制條件下的最短路徑算法分析與優(yōu)化 路徑算法分析new》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第22卷第1期測繪學(xué)院學(xué)報Vol.22No.12005年3月JournalofInstituteofSurveyingandMappingMar.2005文章編號!1009-427X(2005)01-0062-03交通限制條件下的最短路徑算法分析與優(yōu)化許志海!張昭云"信息工程大學(xué)測繪學(xué)院!河南鄭州450052#摘要!通過對交通網(wǎng)絡(luò)本身的特點及要求的分析與研究9介紹了一些適合道路網(wǎng)的經(jīng)典最短路算法和數(shù)據(jù)存貯模式9探討了在交通網(wǎng)絡(luò)路線優(yōu)化過程中需要特別處理的幾個問題9如路口延誤禁行狀態(tài)等9并在理論上給出了相應(yīng)的解決方案O最后給出了一個路徑搜索

2、的實例O關(guān)鍵詞!交通網(wǎng)絡(luò);最短路徑;Distra算法;啟發(fā)式搜索;交通信息中圖分類號!P2S2文獻標(biāo)識碼!A地理網(wǎng)絡(luò)分析是空間分析的一個重要方面常與兩點之間的直線距離和方向存在定的關(guān)是依據(jù)地理網(wǎng)絡(luò)拓撲關(guān)系并通過考察地理網(wǎng)絡(luò)系其幾何和拓撲特性有助于問題的求解元素的空間屬性數(shù)據(jù)對網(wǎng)絡(luò)的性能特征進行多!."最短路徑算法分析方面的分析計算在基于交通網(wǎng)絡(luò)的地理網(wǎng)絡(luò)分最短路徑問題可分為多種類型在基于交通析中主要包括路徑分析服務(wù)中心范圍的確定網(wǎng)絡(luò)的路徑分析中單源最短路徑問題更具有普可達性分析等其核心是對最短路徑的求解遍意義其算法有很多種其中采用及啟發(fā)策略

3、的Distra算法是目前已知的理論上最完善的算法!基于交通網(wǎng)絡(luò)的最短路徑算法分析和優(yōu)化它以極強的抗差性而得到廣泛的普及和應(yīng)用!.!交通網(wǎng)絡(luò)的定義及特點!.".!道路網(wǎng)的存貯交通網(wǎng)絡(luò)一般根據(jù)圖論的基本理論抽象為賦對于交通網(wǎng)絡(luò)的表示通常使用的方法是以1權(quán)圖可以形式化定義為圖論為基礎(chǔ)根據(jù)平面圖特性的存儲方式常用的ROadWOrk=VR有鄰接矩陣鄰接表鄰接多重表和十字鏈表等鄰接矩陣由于其空間復(fù)雜度高一般為O12N=aa6NOdeset+R=NR1。m和關(guān)聯(lián)節(jié)點查詢速度慢一般為O1而NR=taNyLaN>aN6V不適于稀疏圖的存貯鄰接多重表和十字

4、鏈表由其中V是道路的節(jié)點集NR表示道路網(wǎng)中兩個于結(jié)構(gòu)和操作比較復(fù)雜在實踐中的應(yīng)用也僅限于節(jié)點的拓撲關(guān)系集合有序?qū)aNy表示節(jié)點某些專有領(lǐng)域?qū)τ诮煌ňW(wǎng)絡(luò)的存貯和管理鄰接a和N之間的一條邊謂詞LaN表示節(jié)點a到表使用最為廣泛其空間復(fù)雜度為Om+1對于N的通路邊權(quán)可以用邊的幾何長度或者長度和路徑分析中的關(guān)鍵操作關(guān)聯(lián)節(jié)點的查詢也其他因素的加權(quán)和表示設(shè)1=N為一個具體可認為是Om1另外在路徑分析算法的實現(xiàn)網(wǎng)絡(luò)的節(jié)點數(shù)目m=V為網(wǎng)絡(luò)中邊的數(shù)目中對于類似于交通網(wǎng)絡(luò)的大型稀疏圖圖的構(gòu)建交通網(wǎng)絡(luò)可以看成是帶權(quán)有向不完全稀疏與撤銷耗費的時間是相當(dāng)可觀

5、的對于用鄰接矩圖它具有以下的特點由于存在轉(zhuǎn)向限制和道路陣表示的圖它的構(gòu)建與撤銷分別至少需要122行駛方向限制所以它是有向圖存在立體交叉道步即使采取最大相關(guān)點或最大相關(guān)邊法雖然路它是非平面圖對于道路網(wǎng)上的一對節(jié)點P在一定程度上降低了鄰接矩陣在存貯上的空間復(fù)G總存在P到G的路徑反之亦然因此是強連雜度但要搜索節(jié)點的最大相關(guān)點或最大相關(guān)邊通的道路網(wǎng)對應(yīng)的有向圖是不完全的不規(guī)范的數(shù)目也要耗費大量的時間而且還是具有大量的節(jié)點度數(shù)不一通常小于5且mO1。1+的無效數(shù)據(jù)因此在交通網(wǎng)絡(luò)這樣的大型稀疏圖12因此是稀疏圖交通網(wǎng)絡(luò)在空間上存在著局應(yīng)用鄰接表來存貯數(shù)

6、據(jù)已經(jīng)成為業(yè)界的共識其部相關(guān)性即任意兩節(jié)點AB之間的最短路徑通表示根據(jù)應(yīng)用角度不同可以分為順序鄰接表收稿日期!2004-09-21;修回日期!2004-12-1S作者簡介!許志海(1970-)9男9河南睢縣人9博士生9主要從事GIS3S集成研究O第1期許志海等交通限制條件下的最短路徑算法分析與優(yōu)化63FSForWardStar和逆向鄰接表BS在一個典型的道路網(wǎng)中假設(shè)起點s與終點d最短3BackWardStar等路徑長度為z則算法檢查的頂點大致落在由點a!."."最短路徑常用算法分析的位置所定義的橢圓內(nèi)其中z=Dista1cesa對于Dik

7、stra算法的改進主要集中于網(wǎng)絡(luò)存+Dista1ceda對于搜索的節(jié)省量的準(zhǔn)確分析貯的空間復(fù)雜度和算法實現(xiàn)的時間復(fù)雜度以及為比較困難對于典型的利用A。方法在類似于道了滿足某些具體應(yīng)用進行一些特殊限制等方面路網(wǎng)這樣的稀疏圖可得到與112成正比的期望2基于堆結(jié)構(gòu)和桶結(jié)構(gòu)優(yōu)先級隊列的LS算法是研運行時間35"7究得最深入應(yīng)用也最廣泛文獻4在基于真!.".$分層路徑搜索實交通網(wǎng)絡(luò)的基礎(chǔ)上對17種常用算法中的15種路網(wǎng)圖的規(guī)模是影響最優(yōu)路徑搜索時間的主進行了驗證根據(jù)結(jié)果給出了基于鄰接表的一種要因素如果用合理的方法減少搜索所涉及的頂圖存貯結(jié)構(gòu)并推薦了其

8、中的3種算法T@@點和弧的數(shù)量將會使路徑規(guī)劃獲得有效的加速DKA以及DKD其中T@@算法的基礎(chǔ)是圖增長采用基于多層地圖的分級搜索技術(shù)可以實現(xiàn)對路6理論較適合于計算單源點到其他所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭