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



Abstract:The shortest path query is very important in the related applications of graph data. The problem studied in this work is the rule-based shortest path query, which is a special kind of shortest path problem. Given the starting vertex and the ending vertex, the rule-based shortest path query is that finding a shortest path from the starting vertex to the ending vertex, which passes through all vertices in the user-specified set, and the access order of some vertices meets certain partial order rules. It has proved that this problem is NP-hard problem. The existing work focuses on the rule-based shortest path problem on spatial datasets (the shortest distance between two vertices is expressed by Euclidean distance), which exhaustively lists all paths those satisfy the rule, and selects the path with the smallest length as the solution to the problem. However, in an actual road network, the distance between two vertices is equal to the length of the shortest path between two vertices, which is often greater than the Euclidean distance between two vertices. In addition, using an exhaustive approach always results in a lot of repetitive calculations. Based on this, this study designs a forward search algorithm and some optimization techniques to solve such problems. Finally, this study designs a large number of experiments on different real datasets to verify the effectiveness of the algorithms. The experimental results show that the algorithms described in this paper can quickly give the solution to the problem, and the efficiency of the algorithms greatly exceeds the existing algorithms.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5692