本文關鍵詞：圖劃分對Arc-flags算法的影響

  更多相關文章： Arc-flags算法 算法分析 圖劃分 最短路徑 預處理

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號：567745