公开(公告)号：US20070156330A1

公开(公告)日：2007-07-05

申请号：US11321349

申请日：2005-12-29

申请人： Andrew Goldberg ,  Haim Kaplan ,  Renato Werneck

发明人： Andrew Goldberg ,  Haim Kaplan ,  Renato Werneck

IPC分类号： G01C21/34

CPC分类号： G01C21/3446

摘要： A graph is selected for preprocessing. Partial shortest path trees are constructed for the vertices of the graph and shortcuts are added to the graph to reduce the reach of certain vertices. The partial trees can be used to divide the arcs into two groups, a high reach group and a low reach group wherein a reach threshold is used to divide the groups. This threshold may be a function of the number of iterations of the preprocessing algorithm performed thus far. Upper bounds on reach of the low reach arcs are computed, and these arcs are deleted from the graph. The preprocessing algorithm is applied iteratively to the remaining arcs in the graph, with the reach threshold changing based on the current iteration. At the end of the preprocessing phase all arc reaches are below the current threshold and are deleted. The graph obtained from the input graph by adding the shortcuts, together with the reach values, may then be used during a query phase to compute shortest paths between two vertices.

摘要翻译： 选择图形进行预处理。 为图形的顶点构建部分最短路径树，并将快捷方式添加到图中以减少某些顶点的覆盖范围。 部分树可以用于将弧分成两组，即高达组和低达组，其中使用达到阈值来划分组。 该阈值可以是到目前为止执行的预处理算法的迭代次数的函数。 计算低达弧弧的上限，并从图中删除这些弧。 预处理算法迭代地应用于图中的剩余弧，其中达到阈值基于当前迭代而改变。 在预处理阶段结束时，所有电弧达到低于当前阈值并被删除。 然后可以在查询阶段使用从输入图形中添加快捷方式以及到达值获得的图形来计算两个顶点之间的最短路径。

公开(公告)号：US20060047421A1

公开(公告)日：2006-03-02

申请号：US11115558

申请日：2005-04-27

申请人： Andrew Goldberg ,  Renato Werneck

发明人： Andrew Goldberg ,  Renato Werneck

IPC分类号： G01C21/34

CPC分类号： G01C21/34 ,  G01C21/3446 ,  H04L45/12 ,  H04L45/122

摘要： Methods and systems are provided for computing shortest paths among a set of locations. A set of landmarks is dynamically selected by starting with two original landmarks and then improving the landmark selection based on distance to other landmarks. The landmarks are then used with A* search to find the shortest path from source to destination. Additional improvements are provided to reduce the amount of storage required. Landmarks may be generated or selected from a subset of landmarks during pre-processing using one or more selection heuristics, such as using tree-based heuristics and using a local search.

摘要翻译： 提供了用于计算一组位置之间的最短路径的方法和系统。 通过从两个原始地标开始动态选择一组地标，然后根据与其他地标的距离改进地标选择。 然后用A *搜索使用地标，以找到从源到目的地的最短路径。 提供额外的改进以减少所需的存储量。 在使用一个或多个选择启发式的预处理期间，例如使用基于树的启发式法和使用本地搜索，可以从地标的子集中生成或选择地标。