软件学报

作者：李忠飞,杨雅君,王鑫

单位：李忠飞，天津大学 智能与计算学部, 天津 300354;数字出版技术国家重点实验室, 北京 100871;天津市认知计算与应用重点实验室, 天津 30035411,杨雅君，天津大学 智能与计算学部, 天津 300354;数字出版技术国家重点实验室, 北京 100871;天津市认知计算与应用重点实验室, 天津 30035402,王鑫，天津大学 智能与计算学部, 天津 300354;天津市认知计算与应用重点实验室, 天津 30035403

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

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

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

来源：2019年第3期

《软件学报》期刊编辑部

查看软件学报杂志2019年第3期