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

作     者：李忠飞 杨雅君 王鑫 LI Zhong-Fei;YANG Ya-Jun;WANG Xin

作者机构：天津大学智能与计算学部天津300354 数字出版技术国家重点实验室北京100871 天津市认知计算与应用重点实验室天津300354 

基　　金：国家自然科学基金(61402323 61572353 U1736103) 数字出版技术国家重点实验室开放课题 天津市自然科学基金(17JCYBJC15400)~~ 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2019年第30卷第3期

页      码：515-536页

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

主 题 词：图数据 最短路径 规则 最优子排列 分层收缩 

学科分类：08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.13328/j.cnki.jos.005692

馆 藏 号：203607129...