A *algorithm对于非常大的图，关于caching快捷方式的任何想法？
我正在OpenStreetMap地图上写一个快递/物stream模拟，并已经意识到，如下图所示的基本A *algorithm对于大型地图（如大伦敦）来说速度不够快。
绿色节点对应于放置在开放/优先级队列中的绿色节点，由于数目庞大（整个地图大概是1-2百万），需要5秒左右的时间才能find所画的路线。 不幸的是每条路线100毫秒是我的绝对限制。
目前，节点既存储在邻接列表中，也存储在空间100×100二维数组中。
我正在寻找的方法，我可以权衡预处理的时间，空间，如果需要路线的最佳性，更快的查询。 对于启发式成本的直线Haversine公式是根据轮廓仪最昂贵的函数 – 我尽可能地优化了我的基本A *。
例如，我想如果我从2D数组的每个象限中select一个任意节点X并在每个象限之间运行A *，则可以将path存储到磁盘以便后续模拟。 在查询时，我只能在象限中运行A *search，以便在预先计算的路线和X之间进行search。
有没有我上面描述的更精致的版本，或者我应该追求的另一种方法。 非常感谢！
为了logging，下面是一些基准结果，用于任意加权启发式成本，并计算10对随机挑选的节点之间的path：
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几乎将执行时间减半，同时保持相同的路线。
通过折衷优化，你应该能够做得更快。 请参阅wikipedia上的可接受性和最佳性 。
这个想法是使用一个epsilon值，这将导致一个解决scheme不会比最佳path的1 + epsilon差，但是这将导致algorithm考虑更less的节点。 请注意，这并不意味着返回的解决scheme将始终为最佳path的1 + epsilon倍。 这是最坏的情况。 我不知道你的问题在实践中会有怎样的performance，但我认为这是值得探讨的。
在维基百科上给你一些依赖这个想法的algorithm。 我相信这是改进algorithm的最佳select，它有可能在您的时间限制内运行，同时还能恢复正常的path。
由于你的algorithm在5秒内处理了数百万个节点，我假设你也使用二进制堆来实现，对吗？ 如果你手动实现它们，确保它们被实现为简单的数组，并且它们是二进制堆。
这个问题有专门的algorithm做了大量的预计算。 从记忆中，预先计算将信息添加到A *所使用的graphics中，以产生比直线距离更精确的启发式。 维基百科在http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks上给出了许多方法的名称，并说Hub标记是领导者。; 对此的快速search变成pubs/142356/HL-TR.html 。 使用A *的较旧的版本位于pubs/64505/goldberg-sp-wea07.html 。
你真的需要使用Haversine吗？ 为了覆盖伦敦，我原以为你可以假定一个平坦的地球，并使用毕达哥拉斯，或存储图表中每个链接的长度。
微软研究院就这个问题写了一篇非常棒的文章：
http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx
原文载于这里（PDF）：
~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf
基本上有几件事你可以尝试：
- 从源头和目的地开始。 这有助于最大限度地减less从源向外到达目的地时执行的浪费的工作量。
- 使用地标和高速公路。 本质上，在每个地图中find一些通常采用的path并执行一些预先计算，以确定如何有效地在这些点之间导航。 如果您可以find从您的信号源到地标的path，然后find其他地标，然后到达目的地，则可以快速find可行的路线并从中进行优化。
- 探索像“达到”algorithm的algorithm。 这有助于通过最小化需要考虑的顶点数量来查找有效的path，从而最大限度地减less遍历图时要执行的工作量。
GraphHopper做了两件事情来获得快速，非启发式和灵活的路由（注意：我是作者，你可以在这里尝试它）
- 一个不太明显的优化是避免OSM节点到内部节点的1：1映射。 相反，GraphHopper只使用连接点作为节点，大概节省1/8的遍历节点。
- 它具有对A *，Dijkstra或例如一对多Dijkstra有效的工具。 这使得整个德国可以在1s以下的路线。 A *（非启发式）双向版本使得这个更快。
所以应该有可能让你的伦敦更快的路线。
此外，默认模式是速度模式，它使得所有的东西都以更快的速度（例如，欧洲宽path为30ms），但是不太灵活，因为它需要预处理（ 收缩层次 ）。 如果你不喜欢这一点，只需要禁用它，并进一步微调包括街道的车，或者更好地为卡车创build一个新的configuration文件 – 例如排除服务街道和轨道，这应该给你30％的提升。 与任何双向algorithm一样，您可以轻松实现并行search。
我认为用“象限”解决你的想法是值得的。 更严格的说，我把它称为低分辨率的路线search。
您可以select足够接近的X个连接节点，并将它们视为单个低分辨率节点。 将你的整个图分成这样的组，并得到一个低分辨率的图。 这是一个准备阶段。
为了计算从源到目标的路由，首先识别它们所属的低分辨率节点，并find低分辨率路由。 然后通过在高分辨率图表上findpath来改善结果，但是只将algorithm限制在属于低分辨率路由的低分辨率节点的节点上（可选地，也可以考虑高达一定深度的邻居低分辨率节点）。
这也可以推广到多个分辨率，而不仅仅是高/低。
最后，你应该得到一个足够接近最佳的路线。 它是局部最优的，但在某种程度上可能会比全局最优，这取决于分辨率跳变（即当一组节点被定义为单个节点时的近似值）。
有几十个A *的变化可能适合这里的法案。 但是，你必须考虑你的用例。
- 你的内存（也是caching）受到限制吗？
- 你能并行search吗？
- 你的algorithm实现只能在一个位置使用（例如，大伦敦，而不是NYC或孟买或任何地方）？
我们没有办法知道你和你的雇主都知道的所有细节。 因此，您的第一站应该是CiteSeer或Google学术search：寻找与您一样使用相同的一组约束来处理寻路的论文。
然后下选三个或四个algorithm，做原型，testing它们如何扩大和微调它们。 您应该记住，您可以基于点之间的距离，剩余时间或任何其他因素，在相同的macros程序查找程序中组合各种algorithm。
如前所述，根据目标区域的小规模，Haversine可能是您在昂贵的trig评估上节省宝贵时间的第一步。 注意：我不推荐在lat，lon坐标中使用欧几里德距离 – 将您的地图重新映射到靠近中心的横向墨卡托，并使用笛卡尔坐标（以码或米为单位）！
预计算是第二个，更改编译器可能是一个明显的第三个想法（切换到C或C ++ – 详情请参阅https://benchmarksgame.alioth.debian.org/ ）。
额外的优化步骤可能包括摆脱dynamic内存分配，以及在节点之间使用有效的索引search（认为R树及其派生物/替代品）。
我曾在一家主要的导航公司工作，所以我可以放心地说，即使在embedded式设备上，100 ms也应该能让你从伦敦到雅典的路线。 大伦敦将成为我们的testing地图，因为它很方便（很容易适应内存 – 这实际上是不必要的）
首先，A *完全过时。 它的主要好处是“技术上”不需要预处理。 实际上，无论如何，您都需要预先处理OSM映射，这是毫无意义的好处。
给你一个巨大的速度提升的主要技术是弧形标志。 如果你把地图分成5×6的部分，你可以为每个部分分配一个32位整数的1位。 现在，您可以确定每条边从另一节到达节{X,Y}时是否有用。 很多时候，道路是双向的，这意味着只有两个方向中的一个是有用的。 所以这两个方向中的一个已经设置好了，另一个已经清除了。 这似乎并不是一个真正的好处，但这意味着在许多交叉点上，您将从2到1的select数量减less到1个，而这只需要一个位操作。
通常A *伴随着太多的内存消耗，而不是时间滞留。
但是我认为首先只用“大街”一部分的节点进行计算可能是有用的，通常你会在小巷子里select高速公路。
我想你可能已经使用它作为你的权重函数，但是如果你使用一些优先级队列来决定下一步testing哪个节点以便进一步旅行，你可以更快。
此外，您可以尝试将图减less到只包含低成本边的一部分的节点，然后find一个方法来开始/结束这些节点中最近的节点。 所以从开始到“大街”和“大街”有两条路就结束了。 现在，您可以使用简化graphics计算“大街道”一部分的两个节点之间的最佳path。
老问题，但是：
尝试使用不同的“二进制堆”堆。 “最好的渐近复杂堆”定义为斐波那契堆，它的维基页面有一个很好的概述：
https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times
请注意，二进制堆的代码更简单，它是通过数组实现的，并且数组的遍历是可预测的，所以现代CPU执行二进制堆操作的速度要快得多。
但是，给定的数据集足够大，其他堆将赢得二进制堆，因为它们的复杂性…
这个问题看起来像数据集足够大。
