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

• 作者: 李忠飞 杨雅君 王鑫
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 图数据 最短路径 规则 最优子排列 分层收缩
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 智能数据管理与分析技术专刊
• 页码范围: 515-536
• 页数: 22页
• 分类号: TP311
• 字数: 18956字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005692

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王鑫	天津大学智能与计算学部	56	364	10.0	16.0
5	杨雅君	天津大学智能与计算学部	3	8	2.0	2.0
14	李忠飞	天津大学智能与计算学部	1	3	1.0	1.0