一种受限最长频繁路径的查询方法

摘要

本发明公开一种受限最长频繁路径的查询方法，其步骤为：1)设计线性概略化足迹索引，并通过足迹索引构造出足迹图，计算足迹图中每条边的权重，最终将边的权重归一化；2)在上述足迹图中，采用逆Dijkstra单源最短路径算法找出任意顶点到终点的最频繁路径；3)在上述足迹图和最频繁路径的基础上，采用路径的频繁边数量作为上下界剪枝条件搜索整个所述足迹图，最终找出满足条件的受限最长频繁路径。本发明可以保证受限最长频繁路径的合理性和高效性。该发明的最终结果可以提供给相关领域的用户使用，例如导航系统、城市路径规划等领域，可以保证是最频繁路径的合理替代路径。

主权项

一种受限最长频繁路径的查询方法，其特征在于，包括以下步骤：步骤1、设计线性概略化足迹索引，并通过足迹索引构造出足迹图，计算足迹图中每条边的权重，最终将边的权重归一化；步骤2、在所述足迹图中，采用逆Dijkstra单源最短路径算法找出任意顶点到终点的最频繁路径；步骤3、在所述足迹图和最频繁路径的基础上，采用路径的频繁边数量作为上下界剪枝条件搜索整个所述足迹图，最终找出满足条件的受限最长频繁路径。