大規(guī)模圖上的最短路徑問題研究.pdf

1、最短路徑問題是圖論和算法設(shè)計中的經(jīng)典問題。也是現(xiàn)實世界的許多應(yīng)用中的基本問題，如路徑規(guī)劃、物流規(guī)劃、GPS導(dǎo)航、生物醫(yī)學(xué)、社交網(wǎng)絡(luò)、基于位置的服務(wù)(LBS)等等。盡可能快地計算最短路徑是這些應(yīng)用的迫切需求。隨著GPS、電子地圖和LBS的發(fā)展，位置信息爆炸式增長，圖的規(guī)模也越來越大。傳統(tǒng)算法已經(jīng)無法滿足實時性的需求，特別是在基于路網(wǎng)的應(yīng)用中。與此同時，這些應(yīng)用需求也在不斷推動最短路徑算法的持續(xù)發(fā)展。
　　盡管對最短路徑算法的研究已經(jīng)

2、取得了突飛猛進(jìn)的發(fā)展，但是面對數(shù)據(jù)規(guī)模的迅速增長和實時性要求的日益普遍，目前的算法仍然面臨巨大的挑戰(zhàn)。應(yīng)對挑戰(zhàn)的方法一般有三:①研究更高效的串行算法:預(yù)處理技術(shù)是解決這個問題的有效方法。②研究近似算法:在大多數(shù)現(xiàn)實場景中沒有必要計算精確距離。使用近似距離可以有效的降低計算的復(fù)雜度。③研究并行算法:為了充分利用現(xiàn)代多核體系結(jié)構(gòu)的特性，開發(fā)并行算法是必然選擇。
　　圍繞提高最短路徑算法的性能這一目標(biāo)，本文沿兩條線索展開研究工作:以最短

3、路徑問題的分類為線索，本文研究了單源最短路徑、點到點的最短路徑和全源最短路徑問題;以未來的研究趨勢為線索，本文提出了新的串行、近似和并行算法。具體來說，本文的主要研究成果、貢獻(xiàn)和創(chuàng)新點可以概括為以下幾點:
　　(1)提出求解點到點的最短路徑的高效下界算法。在許多應(yīng)用中，實時計算一個源點到一個目的點的最短路徑是一個非常重要的問題。學(xué)術(shù)界已經(jīng)提出若干下界算法求解點到點的最短路徑問題，如A*算法，ALT算法等。這些算法使用的距離估值比較

4、松散，仍然有很大的提升潛力。本文提出了一種新的兩階段目標(biāo)制導(dǎo)下界算法ACT算法。它組合使用了A*搜索，中心點和三角不等式，并且不依賴于特定領(lǐng)域的先驗知識。新算法充分利用了預(yù)處理數(shù)據(jù)，可以獲得非常好的距離下界。在真實路網(wǎng)上的實驗結(jié)果表明，新算法的性能明顯優(yōu)于以往的算法。在某些實例下，ACT算法所擴(kuò)展的頂點數(shù)量僅僅比最短路徑上的頂點數(shù)量多25％左右。
　　(2)提出在路網(wǎng)上檢索露近鄰的基于預(yù)處理的近似算法。路網(wǎng)上的k近鄰檢索已經(jīng)引起越

5、來越多的學(xué)者的關(guān)注。本文提出了一種簡單高效的預(yù)處理算法檢索近似k近鄰。算法選取頂點集合V的一個子集R作為代表頂點，計算R中所有頂點對之間的最短路徑距離。因為|R|(《)|V|，算法只需要較少量的內(nèi)存空間，kNN檢索系統(tǒng)可以部署在普通的桌面級計算機(jī)上。而且，算法中使用的是誤差可控的近似距離。實驗表明，誤差上限較小時，近似算法的檢索結(jié)果比較精確。
　　(3)優(yōu)化OpenCL異構(gòu)計算平臺上的并行單源最短路徑算法。由于數(shù)據(jù)相關(guān)性較強(qiáng)，很難

6、直觀地并行化傳統(tǒng)的最短路徑算法。異構(gòu)計算為解決這一難題帶來了機(jī)遇和挑戰(zhàn)。本文討論了OpenCL的內(nèi)存一致性，研究了已有的并行算法，并提出了一個改進(jìn)型算法。通過調(diào)整數(shù)據(jù)結(jié)構(gòu)和使用原子操作，改進(jìn)后的算法大大減少了內(nèi)核調(diào)用的次數(shù)。實驗結(jié)果表明，改進(jìn)版本的性能比原始版本提高了一倍多。
　　(4)優(yōu)化大規(guī)模稀疏圖上的全源最短路徑算法。在大規(guī)模稀疏圖上計算全源最短路徑的主流方法仍然是重復(fù)調(diào)用Dijkstra算法。本文研究了標(biāo)號初值與標(biāo)號修正算