大規(guī)模路網(wǎng)上點(diǎn)到點(diǎn)的最短路徑計算的Anytime算法研究.pdf

1、圖上最短路徑問題是一個經(jīng)典問題，在諸多領(lǐng)域有著廣泛的應(yīng)用，路網(wǎng)上交通導(dǎo)航就是其中尤為重要的一項(xiàng)應(yīng)用。隨著信息化的高速發(fā)展，路網(wǎng)趨于精細(xì)，數(shù)據(jù)量較大;比如紐約市路網(wǎng)地圖就包含了26萬個節(jié)點(diǎn)，73萬條邊。面對大規(guī)模的路網(wǎng)數(shù)據(jù)，傳統(tǒng)的最短路徑算法在求解時耗時較長，不能滿足應(yīng)用中的實(shí)時需求。
　　Anytime算法是一類能夠隨時被中斷運(yùn)行，且中斷時能返回所求問題的解的算法，并且允許運(yùn)行的時間越長，算法返回的解的質(zhì)量就越好。對于求解點(diǎn)到點(diǎn)最

2、短路徑問題而言，一個Anytime算法能夠在任意時刻終止并返回一條路徑，且返回的路徑隨著允許運(yùn)行的時間的增加而減短，直至最終返回最短路徑。由于這類算法能夠盡快的返回一個相對較短的路徑，并在時間允許的情況下返回最短路徑，從而能夠在路徑長度和求解時間之間取得平衡。
　　本文主要工作有:
　　1，對圖預(yù)處理算法的實(shí)驗(yàn)分析與比較文中描述了幾種對圖進(jìn)行預(yù)處理的算法，通過實(shí)驗(yàn)從預(yù)處理時間、邊覆蓋比例、加速比等角度分析了各個圖預(yù)處理算法在

3、不同路網(wǎng)地圖上的表現(xiàn)，指出了各個算法的特點(diǎn)。本文在已有工作的基礎(chǔ)上提出了一種基于路網(wǎng)信息的Scatter預(yù)處理算法。
　　2，對已有點(diǎn)到點(diǎn)最短路徑問題的Anytime算法的實(shí)驗(yàn)分析與比較文中介紹了三個用于求解點(diǎn)到點(diǎn)最短路徑問題的Anytime算法，并對各個算法進(jìn)行了對比分析，指出它們相同點(diǎn)和不同點(diǎn)，通過實(shí)驗(yàn)比較了各個算法在求解時間和求解質(zhì)量上的不同。分析指出，由于使用了上一輪的計算信息，相對于WA*算法，這些算法找到的路徑不夠短或