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

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