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

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

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

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