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

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

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

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

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

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

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