本文關(guān)鍵詞：圖劃分對Arc-flags算法的影響

  更多相關(guān)文章： Arc-flags算法 算法分析 圖劃分 最短路徑 預(yù)處理

【摘要】：最短路徑計算作為導(dǎo)航的常用算法在移動互聯(lián)網(wǎng)中扮演了重要角色,由于路網(wǎng)規(guī)模的增大和終端的不停移動,傳統(tǒng)的串行最短路徑算法已經(jīng)無法滿足實時性要求,因此預(yù)處理技術(shù)得到了廣泛使用。Arc-flags是一個經(jīng)典的基于預(yù)處理技術(shù)的最短路徑算法,可以提供高效的在線最短路徑查詢服務(wù)�，F(xiàn)有Arc-flags算法的研究主要集中在提升預(yù)處理時空效率和比較不同路網(wǎng)劃分方式的優(yōu)劣上,尚未見圖劃分對Arc-flags算法影響的深入研究。本文在真實路網(wǎng)上測試了不同的圖劃分?jǐn)?shù)量和邊界點數(shù)量等因素對Arc-flags算法的影響,主要包括預(yù)處理時間和空間的消耗、在線查詢時間和搜索范圍等方面,并根據(jù)實驗結(jié)果和分析提出了合理的圖劃分建議(如選用好的圖劃分方法減少邊界點數(shù)量等),為改進和使用Arc-flags算法提供指導(dǎo)。
【作者單位】： 中國科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)學(xué)院;國家高性能計算中心(合肥);中國科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)信息中心;
【關(guān)鍵詞】： Arc-flags算法 算法分析 圖劃分 最短路徑 預(yù)處理
【基金】：國家自然科學(xué)基金青年科學(xué)基金項目(61303047)
【分類號】：P208
【正文快照】： 串行最短路徑算法已經(jīng)無法滿足實時性要求,因此預(yù)處理技術(shù)得到了廣泛使用。Arc-flags是一個經(jīng)典的基于預(yù)處理技術(shù)的最短路徑算法,可以提供高效的在線最短路徑查詢服務(wù)。現(xiàn)有Arc-flags算法的研究主要集中在提升預(yù)處理時空效率和比較不同路網(wǎng)劃分方式的優(yōu)劣上,尚未見圖劃分對Arc

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 黃智星,夏富春;生物基因最短路徑模型分析[J];內(nèi)蒙古科技與經(jīng)濟;2005年07期

2 白青海;;一種求解交通圖最短路徑的方案[J];內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版);2007年02期

3 高超;;游客最短路徑導(dǎo)游方案的設(shè)計[J];商業(yè)文化(下半月);2011年01期

4 吳鵬;;賦權(quán)圖上最短路徑的一種簡便算法[J];貴州師范大學(xué)學(xué)報(自然科學(xué)版);2012年05期

5 張玉成,孫俊逸;應(yīng)用最優(yōu)化選擇原則求最短路徑及長度[J];湖北大學(xué)學(xué)報(自然科學(xué)版);1993年01期

6 班世炳;增刪邊對最短路徑影響的研究[J];廣西民族學(xué)院學(xué)報(自然科學(xué)版);1998年02期

7 潘開靈,呂緒華;罰轉(zhuǎn)向網(wǎng)絡(luò)最短路徑研究[J];武漢冶金科技大學(xué)學(xué)報(自然科學(xué)版);1999年01期

8 李?,山秀明,任勇;具有冪率度分布的因特網(wǎng)平均最短路徑長度估計[J];物理學(xué)報;2004年11期

9 張帆,李軍,王鈞,景寧;多目標(biāo)最短路徑進化求解方法[J];系統(tǒng)工程;2005年09期

10 杜牧青;程琳;;考慮交叉口轉(zhuǎn)向延誤的最短路徑拍賣算法[J];西南交通大學(xué)學(xué)報;2010年02期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 溫粉蓮;唐常杰;喬少杰;許剛;劉威;左R，

本文編號：567745