A*非常大的图的算法,对缓存快捷方式的任何想法？

Question

我正在OpenStreetMap地图上写一个快递/物流模拟,并且已经意识到如下图所示的基本A*算法对于大型地图(如大伦敦)来说不够快.

绿色节点对应于放置在开放集/优先级队列中的绿色节点,并且由于数量巨大(整个地图大约为1-2百万),需要5秒左右才能找到所示的路线.不幸的是,每条路线100毫秒是我的绝对限制.

目前,节点存储在邻接列表和空间100×100 2D阵列中.

我正在寻找可以在预处理时间,空间和路线最佳性能之间进行权衡的方法,以便更快地进行查询.根据剖析器,启发式成本的直线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几乎将执行时间减半,同时保持相同的路线.

Answer 1

你应该能够通过权衡最优性来加快速度.请参阅维基百科上的可接受性和最优性.

我们的想法是使用一个epsilon值,该值将导致解决方案不比1 + epsilon最佳路径的时间差,但这将导致算法考虑更少的节点.请注意,这并不意味着返回的解决方案始终是1 + epsilon最佳路径的倍数.这只是最糟糕的情况.我不确切地知道它在实践中会如何表现你的问题,但我认为值得探索.

在维基百科上,您将获得许多依赖于此想法的算法.我相信这是改进算法的最佳选择,并且它有可能在您的时间限制内运行,同时仍然可以返回良好的路径.

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

Answer 2

这个问题有专门的算法可以进行大量的预计算.从内存中,预计算将信息添加到A*用于产生比直线距离更准确的启发式的图形.维基百科在http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks上给出了许多方法的名称,并表示Hub Labeling是领导者.快速搜索http://research.microsoft.com/pubs/142356/HL-TR.pdf.使用A*的较旧版本位于http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf.

你真的需要使用Haversine吗？为了覆盖伦敦,我原本以为你可以假设一个平坦的地球并使用毕达哥拉斯,或者存储图中每个链接的长度.

Answer 3

微软研究院就这个主题撰写了一篇非常好的文章:

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

基本上你可以尝试一些事情:

1. 从源和目的地开始.这有助于最大限度地减少从源向外移动到目的地时所执行的浪费工作量.
2. 使用地标和高速公路.基本上,在每个地图中找到一些通常采用路径的位置,并执行一些预先计算以确定如何在这些点之间有效导航.如果您可以找到从源到地标的路径,然后到其他地标,然后到目的地,您可以快速找到可行路线并从那里进行优化.
3. 探索像"覆盖"算法这样的算法.这有助于最大限度地减少在遍历图形时通过最小化为查找有效路径而需要考虑的顶点数量而执行的工作量.

Answer 4

GraphHopper做了两件事,以获得快速,无启发和灵活的路由(注意:我是作者,你可以在这里尝试它)

1. 不太明显的优化是避免OSM节点到内部节点的1:1映射.相反,GraphHopper仅使用联结作为节点,并节省大约1/8的遍历节点.
2. 它为A*,Dijkstra或一对多Dijkstra提供了高效的工具.在整个德国,这使得1岁以下的路线成为可能.A*的(非启发式)双向版本使这更快.

因此,应该可以为您提供更快的伦敦路线.

此外,默认模式是速度模式,它使所有内容的速度更快(例如,对于欧洲宽路线为30ms),但灵活性较低,因为它需要预处理(收缩层次结构).如果您不喜欢这样,只需禁用它,并进一步微调包含的汽车街道,或者更好地为卡车创建新的配置文件 - 例如,排除服务街道和轨道,这将使您进一步提高30%.与任何双向算法一样,您可以轻松实现并行搜索.