论文摘要
最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.
论文目录
文章来源
类型: 期刊论文
作者: 李忠飞,杨雅君,王鑫
关键词: 图数据,最短路径,规则,最优子排列,分层收缩
来源: 软件学报 2019年03期
年度: 2019
分类: 信息科技,基础科学
专业: 数学,计算机软件及计算机应用
单位: 天津大学智能与计算学部,数字出版技术国家重点实验室,天津市认知计算与应用重点实验室
基金: 国家自然科学基金(61402323,61572353,U1736103),数字出版技术国家重点实验室开放课题,天津市自然科学基金(17JCYBJC15400)~~
分类号: TP311.13;O157.5
DOI: 10.13328/j.cnki.jos.005692
页码: 515-536
总页数: 22
文件大小: 1540K
下载量: 328
相关论文文献
- [1].营销的最短路径[J]. 销售与管理 2019(10)
- [2].动态网络中一种高效的最短路径树维护算法[J]. 计算机工程 2017(01)
- [3].稳定的最短路径树及其构造算法[J]. 计算机工程与科学 2016(03)
- [4].道路突发中断情况下实时最短路径快速求解算法[J]. 计算机应用 2016(S1)
- [5].“最短路径”问题的探究与思考[J]. 考试与评价 2017(01)
- [6].勾股定理、方程如影随形[J]. 中学生数理化(八年级数学)(配合人教社教材) 2017(03)
- [7].确定最短路径不能想当然[J]. 中学生数理化(八年级数学)(配合人教社教材) 2017(03)
- [8].谢谢你,姑,妈[J]. 意林(少年版) 2013(14)
- [9].面向室内实时路径规划的最短路径缓存算法[J]. 电子技术与软件工程 2019(22)
- [10].基于遗传算法的送外卖最短路径研究[J]. 科技传播 2016(06)
- [11].初中数学中“平面展开最短路径”教学反思[J]. 中学生数理化(教与学) 2014(12)
- [12].最短路径[J]. 同学少年 2012(06)
- [13].基于复杂网络的城市公交网络的度和最短路径相关性的分析[J]. 科技通报 2013(02)
- [14].面向大规模道路网的最短路径近似算法[J]. 测绘学报 2019(01)
- [15].基于最短路径的求解与创新[J]. 科技创新导报 2012(29)
- [16].一种高效的最短路径树动态更新算法[J]. 计算机科学 2011(07)
- [17].适合复杂网络分析的最短路径近似算法[J]. 软件学报 2011(10)
- [18].具有多条最短路径的最短路问题[J]. 哈尔滨工业大学学报 2010(09)
- [19].基于扇形搜索的最短路径射线追踪方法探讨[J]. 红水河 2019(05)
- [20].道路交通网络最短路径关键转向研究[J]. 公路 2018(09)
- [21].一种个性化城市多目标最短路径随机优化算法[J]. 中国科技论文 2016(07)
- [22].化学GPS能快速找出两点间最短路径 速度快过电子GPS[J]. 黑龙江科技信息 2014(30)
- [23].这篇文章的解答值得商榷[J]. 中学生数学 2011(04)
- [24].城市交通时间最短路径计算模型及应用仿真[J]. 计算机仿真 2014(01)
- [25].交互网络上任意节点对的最短路径集解法[J]. 海军工程大学学报 2011(04)
- [26].一种灾害救援最短路径动态算法[J]. 沈阳建筑大学学报(自然科学版) 2011(05)
- [27].军事通讯网络的最短路径研究分析[J]. 数码世界 2019(07)
- [28].独立多约束最短路径选择[J]. 江西理工大学学报 2011(03)
- [29].基于人工免疫的N最短路径检索算法[J]. 山东大学学报(理学版) 2017(09)
- [30].对K则最短路径若干算法的探讨[J]. 内蒙古煤炭经济 2016(Z3)