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

李忠飞杨雅君王鑫

天津大学;

摘要：

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集(两点之间的最短距离用欧氏距离表示)上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.…展开v

关键词：图数据、最短路径、规则、最优子排列、分层收缩

所属期刊栏目：30

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2019-04-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共22页

页码：515-536