基于规则的最短路径查询算法

李忠飞; 杨雅君; 王鑫

首页> 中文期刊> 《软件学报》 >基于规则的最短路径查询算法

基于规则的最短路径查询算法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集(两点之间的最短距离用欧氏距离表示)上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.

著录项

来源
《软件学报》 |2019年第3期|515-536|共22页
作者
李忠飞; 杨雅君; 王鑫;
展开▼
作者单位

天津大学智能与计算学部;

天津300354;

数字出版技术国家重点实验室;

北京 100871;

天津市认知计算与应用重点实验室;

天津300354;

天津大学智能与计算学部;

天津300354;

数字出版技术国家重点实验室;

北京 100871;

天津市认知计算与应用重点实验室;

天津300354;

天津大学智能与计算学部;

天津300354;

天津市认知计算与应用重点实验室;

天津300354;

展开▼
原文格式 PDF
正文语种 chi
中图分类程序设计、软件工程;
关键词
图数据; 最短路径; 规则; 最优子排列; 分层收缩;

相似文献

中文文献
外文文献
专利

1. 基于缓存的时变道路网最短路径查询算法 [J] . 黄阳 ,周旭 ,杨志邦 . 计算机研究与发展 . 2022,第2期
2. 基于多功能网的最短路径查询算法 [J] . 袁敏 ,孙更新 ,宾晟 . 青岛大学学报（自然科学版） . 2021,第002期
3. 一种基于悬挂顶点关联索引的最短路径查询算法 [J] . 陈伟 ,楼志斌 ,杨清章 . 燕山大学学报 . 2018,第003期
4. 基于顶点关联索引的最短路径查询算法研究 [J] . 余靖 ,杨清章 . 高技术通讯 . 2017,第011期
5. 路网中基于地理位置和区域封闭性的最短路径的查询算法 [J] . 顾明皓 ,徐明 . 计算机科学 . 2016,第006期
6. 蚂蚁算法在公交查询最短路径求法中的应用 [C] . 张帅 ,彭玉青 ,赵镇 . CERNET第十届学术年会 . 2003
7. 大规模图上的基于规则约束的最短路径算法研究 [A] . 李忠飞 . 2018

基于规则的最短路径查询算法

摘要

著录项

相似文献

相关主题

期刊订阅