圖劃分在路網(wǎng)最短路徑查詢中應(yīng)用的研究.pdf

1、隨著移動互聯(lián)網(wǎng)的興起，人們對路徑導(dǎo)航的需求越來越高，對基于位置服務(wù)的需求更多樣化。由于終端的不停移動，基于位置的實時導(dǎo)航對算法性能有著更嚴格的要求。交通工具的發(fā)達，使得人們的活動范圍越來越大，導(dǎo)航中需要處理的路網(wǎng)數(shù)據(jù)規(guī)模也越來越大，導(dǎo)致計算時間更長，和需求相矛盾。
　　圖劃分是一種圖數(shù)據(jù)處理技術(shù)，廣泛應(yīng)用于并行計算和大規(guī)模集成電路設(shè)計等領(lǐng)域。路網(wǎng)的最短路徑計算問題是在圖數(shù)據(jù)上進行查詢計算，兩者有著天然的相關(guān)性。本文重點研究圖劃分在

2、路網(wǎng)最短路徑查詢中的應(yīng)用，提出了基于代表元的路網(wǎng)最短路徑查詢算法，在滿足服務(wù)多樣性需求的同時獲得較好的在線查詢速度。
　　本文的主要工作有:
　　研究圖劃分對Arc-flags算法的影響
　　Arc-flags是將圖劃分技術(shù)應(yīng)用到最短路徑查詢中的經(jīng)典算法，該算法采用預(yù)處理技術(shù)提升在線查詢速度。前人的工作主要集中在優(yōu)化預(yù)處理性能和對比不同的圖分割方式方面，圖劃分對Arc-flags算法的影響沒有做過深入分析。本文在真實路

3、網(wǎng)上深入分析了圖劃分對Arc-flags算法的影響，主要包含預(yù)處理時間、空間消耗和在線查詢效率等方面，對不同情況下Arc-flags算法的應(yīng)用提出相應(yīng)的圖劃分建議。
　　定義有向圖中的代表元，提出新的代表元選擇算法和基于代表元的最短路徑查詢算法。
　　代表元是一種非標準圖劃分方式，被應(yīng)用在近似最短距離查詢中。以往基于代表元的近似最短距離查詢算法僅關(guān)注無向圖中的計算，而由于單行道的存在，真實路網(wǎng)通常被表示成有向圖。本文定義了有