大型图形的A *算法，对缓存快捷方式有何想法? [英] A* Algorithm for very large graphs, any thoughts on caching shortcuts?
问题描述
我正在OpenStreetMap地图上编写快递/后勤仿真，并且已经意识到，如下图所示的基本A *算法对于大型地图(例如大伦敦)来说不够快.
I'm writing a courier/logistics simulation on OpenStreetMap maps and have realised that the basic A* algorithm as pictured below is not going to be fast enough for large maps (like Greater London).
绿色节点对应于放置在开放集合/优先级队列中的节点，由于数量巨大(整个地图大约为1-2百万)，因此需要5秒钟左右的时间才能找到所描绘的路线.不幸的是，每条路线100ms大约是我的绝对极限.
The green nodes correspond to ones that were put in the open set/priority queue and due to the huge number (the whole map is something like 1-2 million), it takes 5 seconds or so to find the route pictured. Unfortunately 100ms per route is about my absolute limit.
当前，节点既存储在邻接列表中，又存储在空间100x100 2D数组中.
Currently, the nodes are stored in both an adjacency list and also a spatial 100x100 2D array.
我正在寻找可以权衡预处理时间，空间以及必要时优化路线以加快查询速度的方法.根据探查器，用于启发式成本的直线Haversine公式是最昂贵的函数-我已尽我所能优化了基本A *.
I'm looking for methods where I can trade off preprocessing time, space and if needed optimality of the route, for faster queries. The straight-line Haversine formula for the heuristic cost is the most expensive function according to the profiler - I have optimised my basic A* as much as I can.
例如，我在考虑是否要从2D数组的每个象限中选择一个任意节点X并在每个象限之间运行A *，我可以将路由存储到磁盘以进行后续仿真.查询时，我只能在象限中运行A *搜索，以在预先计算的路径和X之间进行搜索.
For example, I was thinking if I chose an arbitrary node X from each quadrant of the 2D array and run A* between each, I can store the routes to disk for subsequent simulations. When querying, I can run A* search only in the quadrants, to get between the precomputed route and the X.
是否有我上面描述的更完善的版本，或者可能是我应该采用的其他方法.非常感谢！
Is there a more refined version of what I've described above or perhaps a different method I should pursue. Many thanks!
为便于记录，以下是一些基准结果，可任意加权启发式成本并计算10对随机选取的节点之间的路径:
For the record, here are some benchmark results for arbitrarily weighting the heuristic cost and computing the path between 10 pairs of randomly picked nodes:
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几乎使执行时间减少了一半，同时又保持了相同的路径.
Surprisingly increasing the coefficient to 1.1 almost halved the execution time whilst keeping the same route.
推荐答案
您应该可以通过权衡最优性来使其更快.参见Wikipedia上的可接纳性和最优性.
You should be able to make it much faster by trading off optimality. See Admissibility and optimality on wikipedia.
这个想法是使用一个epsilon值，该值将导致求解的结果不小于最佳路径的1 + epsilon倍，但是这将导致该算法考虑的节点更少.请注意，这并不意味着返回的解决方案将始终是最佳路径的1 + epsilon倍.这只是最坏的情况.我不知道它在实际中如何解决您的问题，但我认为值得探讨.
The idea is to use an epsilon value which will lead to a solution no worse than 1 + epsilon times the optimal path, but which will cause fewer nodes to be considered by the algorithm. Note that this does not mean that the returned solution will always be 1 + epsilon times the optimal path. This is just the worst case. I don't know exactly how it would behave in practice for your problem, but I think it is worth exploring.
为您提供了许多算法，这些算法都依赖于Wikipedia上的这一思想.我相信这是改进算法的最佳选择，它有可能在您的时限内运行，同时仍然返回良好的路径.
You are given a number of algorithms that rely on this idea on wikipedia. I believe this is your best bet to improve the algorithm and that it has the potential to run in your time limit while still returning good paths.
由于您的算法确实在5秒内处理了数百万个节点，因此我假设您还使用二进制堆进行实现，对吗?如果您手动实现它们，请确保将它们实现为简单数组，并且它们是二进制堆.
Since your algorithm does deal with millions of nodes in 5 seconds, I assume you also use binary heaps for the implementation, correct? If you implemented them manually, make sure they are implemented as simple arrays and that they are binary heaps.
这篇关于大型图形的A *算法，对缓存快捷方式有何想法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
