動態(tài)路網(wǎng)上最短路徑算法研究.pdf

1、在道路網(wǎng)上精確計算點對點最短路徑是圖論算法的眾多實際應(yīng)用之一。經(jīng)典的Dijkstra算法及其變種雙向Dijkstra搜索算法在大規(guī)模道路網(wǎng)上過于緩慢，早已力不從心。有幸的是在過去十年間，這個經(jīng)典問題受到大量關(guān)注，尤其在大規(guī)模道路網(wǎng)上取得了極其重要的突破，目前很多算法的運行效率比Dijkstra算法快了好幾個數(shù)量級。目標向?qū)Х椒ê蛯哟位椒ㄊ莾深愖罹叽硇缘姆椒?，它們各自?jīng)歷過一段快速發(fā)展時期。此外，將兩類方法巧妙地結(jié)合起來能夠在各方面都

2、取得最佳效果。盡管實驗表明這些算法性能良好，卻缺乏理論分析的支撐。這是因為，道路網(wǎng)雖有一些性質(zhì)，卻無法嚴格地對它下定義。這些性質(zhì)包括稀疏性、近乎可平面性以及層次化特性。
　　然而，現(xiàn)有的算法大都只適應(yīng)處理靜態(tài)網(wǎng)絡(luò)，它們需要較長的時間進行預(yù)處理，以產(chǎn)生足夠的輔助數(shù)據(jù)來加速最短路徑查詢。因此，這些加速技術(shù)難以應(yīng)付邊權(quán)重經(jīng)常變化的動態(tài)路網(wǎng)，諸如交通堵塞或者檢修路況等，即使權(quán)重變化的邊集只占整個路網(wǎng)的一小部分。鑒于現(xiàn)有的最快算法Trans