图划分对Arc-flags算法的影响

发布时间：2017-07-20 11:15

  本文关键词：图划分对Arc-flags算法的影响

  更多相关文章： Arc-flags算法 算法分析 图划分 最短路径 预处理

【摘要】：最短路径计算作为导航的常用算法在移动互联网中扮演了重要角色,由于路网规模的增大和终端的不停移动,传统的串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用。Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务。现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc-flags算法影响的深入研究。本文在真实路网上测试了不同的图划分数量和边界点数量等因素对Arc-flags算法的影响,主要包括预处理时间和空间的消耗、在线查询时间和搜索范围等方面,并根据实验结果和分析提出了合理的图划分建议(如选用好的图划分方法减少边界点数量等),为改进和使用Arc-flags算法提供指导。
【作者单位】： 中国科学技术大学计算机科学与技术学院;国家高性能计算中心(合肥);中国科学技术大学网络信息中心;
【关键词】： Arc-flags算法 算法分析 图划分 最短路径 预处理
【基金】：国家自然科学基金青年科学基金项目(61303047)
【分类号】：P208
【正文快照】： 串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用。Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务。现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc

【相似文献】

中国期刊全文数据库 前10条

1 黄智星,夏富春;生物基因最短路径模型分析[J];内蒙古科技与经济;2005年07期

2 白青海;;一种求解交通图最短路径的方案[J];内蒙古民族大学学报(自然科学版);2007年02期

3 高超;;游客最短路径导游方案的设计[J];商业文化(下半月);2011年01期

4 吴鹏;;赋权图上最短路径的一种简便算法[J];贵州师范大学学报(自然科学版);2012年05期

5 张玉成,孙俊逸;应用最优化选择原则求最短路径及长度[J];湖北大学学报(自然科学版);1993年01期

6 班世炳;增删边对最短路径影响的研究[J];广西民族学院学报(自然科学版);1998年02期

7 潘开灵,吕绪华;罚转向网络最短路径研究[J];武汉冶金科技大学学报(自然科学版);1999年01期

8 李?,山秀明,任勇;具有幂率度分布的因特网平均最短路径长度估计[J];物理学报;2004年11期

9 张帆,李军,王钧,景宁;多目标最短路径进化求解方法[J];系统工程;2005年09期

10 杜牧青;程琳;;考虑交叉口转向延误的最短路径拍卖算法[J];西南交通大学学报;2010年02期

中国重要会议论文全文数据库 前10条

1 温粉莲;唐常杰;乔少杰;许刚;刘威;左R，

本文编号：567745