非常大的图形A*算法，对于缓存快捷方式有什么想法？

Question

非常大的图形A*算法，对于缓存快捷方式有什么想法？

algorithmopenstreetmapgraph-algorithmshortest-patha-star

72

我正在使用OpenStreetMap地图编写一款快递/物流模拟器，发现像下面这样的基本A*算法对于大型地图（如伦敦市区）并不够快。

绿色节点对应于被放入开放集/优先队列中的节点，由于数量巨大（整个地图大约有100-200万个节点），要找到如图所示的路径需要约5秒钟左右。但很遗憾，每条路线的最长计算时间只能是100毫秒左右。

目前，节点既存储在邻接列表中，也存储在一个空间100x100二维数组中。

我正在寻找可以在预处理时间、空间和必要时权衡路径优化程度的方法，以加快查询速度。根据分析器，启发式代价的直线Haversine公式是最昂贵的函数 - 我已经尽可能地优化了我的基本A*算法。

例如，我想如果我从2D数组的每个象限中选择一个任意节点X，并在每个节点对之间运行A*搜索，则可以将路线存储到磁盘上供后续模拟使用。在查询时，我只需要在象限内运行A*搜索，以便在预计算的路径与X之间获取路径。

是否有更精确的版本或者我应该追求不同的方法。非常感谢！

以下是对于任意加权启发式代价和计算10对随机选定节点之间的路径的基准测试结果：

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

令人惊讶的是，将系数增加到1.1几乎将执行时间减半，同时保持相同的路线。

- drspa44

我认为你应该尝试在这里询问：http://cs.stackexchange.com - Wojciech Kulik

一种修改算法的方法是允许对每个路段进行加权（例如，8车道高速公路每单位距离的成本为1，而未铺设的土路则成本为50，以及介于两者之间的所有事物...）。虽然这样做需要对地图提供商提供的所有路段进行分类，如果它们没有适当的数据与之相关联的话，那么这将是一个巨大的任务... - twalberg

2

没有时间写完整的答案，但现代技术涉及找到小分离器。不要满足于近似结果--这很麻烦，需要调试。 - David Eisenstat

2

尝试使用“Arc-Flags”对图进行预处理；这很简单，也应该能够让你获得不错的加速效果。 - user541686

你可以使用地标来实现A*算法。这个想法是，你选择一个地标并预先计算出从该地标到图中所有节点的距离。然后，当你有一个搜索查询时，你可以使用这些数据生成一个最小乐观启发式（参见：可接受和一致）。你还应该研究“reach”。 - Harrichael

显示剩余9条评论

9个回答

9

有专门针对此问题的算法，会进行大量预计算。据我记忆，预计算会为图表添加信息，A*算法利用该信息生成比直线距离更准确的启发式。维基百科给出了一些方法的名称，可在http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks找到，并表示Hub Labelling是领先者。在此快速搜索可得到http://research.microsoft.com/pubs/142356/HL-TR.pdf。还有一个较旧的版本使用了A*算法，位于http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf。

您是否真的需要使用Haversine？如果只是覆盖伦敦市区，您可以假设地球是平面的，使用勾股定理，或在图表中存储每个链接的长度。

- mcdowella

谢谢，我会阅读这些的。不幸的是，即使是非常短的距离，毕达哥拉斯定理也可能会有很大误差。出于意料之外的原因，更换它通常会导致次优路径。 - drspa44

http://gis.stackexchange.com/questions/58653/what-is-the-approximate-error-of-the-pythagorean-theorem-vs-haversine-formula-i - drspa44

2

@drspa44 - 你需要重新投影地图（考虑使用局部中心横轴墨卡托投影）！ - Deer Hunter

这里有一个简单的平面投影：https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/util/DistancePlaneProjection.java#L45 请参考注释中的链接。 - Karussell

7

微软研究部门撰写了一篇非常优秀的关于这个主题的文章：

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

原始论文托管在此处（PDF）：

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

基本上有几种方法可以尝试：

从源和目的地开始。这有助于最小化从源向外遍历到目的地时执行的浪费工作量。
使用地标和高速公路。实质上，找到每个地图中常走的路径的一些位置，并执行一些预计算以确定如何在这些点之间有效地导航。如果您可以找到从源到地标，然后到其他地标，然后到目的地的路径，那么您可以快速找到可行的路线并进行优化。
探索像“reach”算法这样的算法。这有助于通过最小化需要考虑的顶点数量来遍历图形，以便找到有效的路径。

- mattbasta

谢谢。我确实读了那篇文章，今天我试图想出一些实现地标方法的方式。对我来说问题在于不知道如何根据我拥有的数据选择地标。高速公路对我来说也不容易识别。我尝试了到达度的实验，但我发现性能提升微不足道。看着微软的图片，双向Djikstra和A*似乎并没有比我目前拥有的快多少，虽然我还没有实现任何一个。 - drspa44

第二步被称为收缩分层。 - MSalters

@MSalters，使用地标时情况就不同了 -> ALT - Karussell

6

GraphHopper可以做两件事情来实现快速、非启发式和灵活的路径规划（注意：我是作者，你可以在这里在线试用）

一个不太明显的优化是避免将OSM节点与内部节点进行1:1映射。相反，GraphHopper仅使用路口作为节点，并节省了大约1/8的遍历节点。
它具有高效的A*、Dijkstra或例如一对多的Dijkstra实现。这使得在德国整个地区内规划路径在不到1秒的时间内就能完成。A*的双向版本（无启发式）使其更快。

因此，应该可以为您提供伦敦大区的快速路线。

此外，默认模式是速度模式，这使得所有东西都快了一个数量级（例如欧洲广域路线需要30毫秒），但灵活性较差，因为它需要预处理（ Contraction Hierarchies）。如果您不喜欢这个模式，只需禁用它，并进一步微调包括的街道供汽车使用，或者可以更好地创建一个新的卡车配置文件 - 例如排除服务街和轨道，这应该能够再提高30％。而且，与任何双向算法一样，您可以很容易实现并行搜索。

- Karussell

4

我认为使用“象限”来完善你的想法是值得的。更严谨地说，我称之为低分辨率路径搜索。

你可以选择足够近的X个相连节点，并将它们视为一个单一的低分辨率节点。将整个图形划分为这样的群组，就可以得到一个低分辨率图形。这是预处理阶段。

为了计算从源到目标的路径，首先确定它们所属的低分辨率节点，并找到低分辨率路径。然后通过在高分辨率图中找到路线来改进结果，但只限制算法仅针对属于低分辨率路径的低分辨率节点（可选地，您还可以考虑邻居低分辨率节点直到某个深度）。

这也可以推广到多个分辨率，而不仅仅是高/低。

最终，您应该得到一条足够接近最优的路径。它是局部最优的，但在某种程度上可能比全局最优差一些，这取决于分辨率跳跃（即当将一组节点定义为单个节点时所做的近似）。

- valdo

3

这里有数十种可能适用的A*变体。但您需要考虑您的使用情况。

您是否受到内存（以及缓存）的限制？
您能否并行搜索？
您的算法实现将仅在一个位置使用（例如仅限于大伦敦，而不是纽约、孟买或其他地方）吗？

我们无法知道您和雇主所知道的所有细节。因此，您的第一站应该是CiteSeer或Google Scholar：寻找处理与您相同一般约束条件的路径查找论文。

然后缩小范围到三到四个算法，进行原型设计，测试它们的扩展性并进行微调。您应该记住，可以根据点之间的距离、剩余时间或任何其他因素，在同一大型路径查找程序中组合各种算法。

正如已经提到的，基于您的目标区域规模较小，放弃 Haversine 是您节省宝贵时间和昂贵三角函数计算的第一步。注意：我不建议在 lat、lon 坐标系中使用欧几里得距离 - 将地图重新投影到以横轴为中心的墨卡托投影，并在码或米的笛卡尔坐标系中使用！

预处理是第二个步骤，更换编译器可能是一个明显的第三个想法（转向 C 或 C++ - 参见 https://benchmarksgame.alioth.debian.org/ 获取详细信息）。

额外的优化步骤可能包括消除动态内存分配，并使用高效的索引来搜索节点（考虑 R 树及其衍生/替代品）。

- Deer Hunter

3

我曾在一家主要的导航公司工作，所以我可以自信地说，在嵌入式设备上，用100毫秒就可以得到从伦敦到雅典的路线。对于我们来说，更大的伦敦将是一个测试地图，因为它很小（很容易适应内存 - 其实这并非必要）。

首先，A*算法已经过时了。它的主要优点是“技术上”不需要预处理。实际上，您需要对OSM地图进行预处理，因此这是一个无意义的好处。

提供巨大速度提升的主要技术是弧标志。如果将地图分成5x6个区域，您可以为每个区域在32位整数中分配1个位置。现在，您可以确定每个边缘是否在从另一个区域前往区域时有用。相当多的道路是双向的，这意味着只有两个方向中的一个是有用的。因此，其中一个方向设置了该位，而另一个方向则清除了该位。这可能看起来并不是真正的好处，但它意味着在许多交叉口，您将把需要考虑的选择数量从2减少到仅需1个，并且这只需要进行一次位操作。

- MSalters

对于伦敦来说，一个主要的优势是你可以在桥上设置这些位。A*算法可能会因为不必要地穿过河流并卡在另一岸而遭受相当大的困扰。 - MSalters

0

通常情况下，A*算法的内存消耗比时间开销更大。

然而，我认为首先只计算“大街”上的节点可能会很有用。通常情况下，你会选择高速公路而不是小巷。

我猜你可能已经在权重函数中使用了这个方法，但如果你使用一些优先队列来决定下一个要测试的节点以进行进一步旅行，你可以更快地完成。

此外，您可以尝试将图形缩小到仅包含成本较低的节点，然后找到从起点/终点到最接近这些节点的路径。因此，您从起点到“大街”和从“大街”到终点有两条路径。现在，您可以在缩小的图形中计算两个“大街”节点之间的最佳路径。

- xuma202

-1

虽然这是一个老问题，但还是值得探讨：

尝试使用不同于“二叉堆”的堆。最优渐进复杂度的堆明显是斐波那契堆，其维基页面提供了很好的概述：

https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times

请注意，二叉堆的代码更简单，它是基于数组实现的，对数组的遍历是可预测的，因此现代CPU可以更快地执行二叉堆操作。

然而，如果数据集足够大，其他堆将胜过二叉堆，因为它们更复杂...

这个问题似乎是数据集足够大。

- user1928750

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

您可以通过权衡最优性来使其更快。请参见维基百科上的可接受性和最优性。

这个想法是使用一个epsilon值，这将导致解决方案不会比最优路径差1 + epsilon倍，但是这将导致算法考虑较少的节点。请注意，这并不意味着返回的解决方案总是1 + epsilon倍于最优路径。这只是最坏情况。我不知道它在实践中对您的问题会表现如何，但我认为这值得探索。

您可以在维基百科上找到许多依赖此想法的算法。我认为这是改进算法并在时限内返回良好路径的最佳选择。

由于您的算法在5秒钟内处理数百万个节点，我假设您也使用二进制堆进行实现，对吗？如果您手动实现它们，请确保它们被实现为简单的数组，并且它们是二进制堆。