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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：567745