哪些算法可以计算地图上从A点到B点的方向？

Question

地图提供商（例如Google或Yahoo! Maps）如何建议方向？我的意思是，他们可能具有某种形式的现实世界数据，当然包括距离，还可能包括行车速度，人行道的存在，火车时刻表等。但是，假设数据的格式更简单，则表示一个很大的有向图边缘权重反映距离。我希望能够快速计算从一个任意点到另一点的方向。有时，这些点会彼此靠近（在一个城市内），而有时它们会相距较远（越野）。像Dijkstra的算法这样的图算法将无法工作，因为图非常大。幸运的是，像A *这样的启发式算法可能会起作用。但是，我们的数据非常结构化，也许某种分层方法可能有效？（例如，存储相距很远的某些“关键”点之间的预先计算的方向以及一些本地方向。然后，两个遥远点的方向将涉及到关键点的本地方向，到另一个关键点的全局方向，然后是本地再次指示。）实际上实际使用哪些算法？PS。这个问题是由在网上制图方向上找到古怪之处引起的。与三角形不等式相反，有时Google Maps认为XZ比使用XYZ中的中间点花费更长的时间并且更远。但是也许他们的步行方向也针对另一个参数进行了优化？PPS。这是对三角形不等式的另一种违反，对我而言，这暗示了他们使用某种分层方法：XZ与XYZ。前者似乎使用了著名的塞巴斯托波尔大道，尽管有点偏离。编辑：这些示例似乎都不工作了，但在原始帖子发布时都可以。

Answer 1

以在地图公司工作了18个月的人的身份发言，其中包括研究路由算法...是的，Dijkstra确实可以工作，但有一些修改：

• 您无需从源头到目标都进行一次Dijkstra的操作，而应从两端开始，并扩展双方直到中间相遇。这消除了大约一半的工作（2 * pi *（r / 2）^ 2 vs pi * r ^ 2）。

• 为了避免探索源与目的地之间每个城市的后巷，您可以使用几层地图数据：仅包含高速公路的“高速公路”层，仅包含次要街道的“次级”层，依此类推。然后，您仅浏览更详细层的较小部分，并根据需要进行扩展。显然，此描述省略了很多细节，但是您可以理解。

沿着这些路线进行修改，您甚至可以在非常合理的时间范围内进行越野路线选择。

Answer 2

近年来，这个问题一直是研究的活跃领域。主要思想是对图形进行一次预处理，以加快所有后续查询的速度。利用这些附加信息，可以非常快速地计算行程。尽管如此，Dijkstra的算法仍是所有优化的基础。

Arachnid描述了基于分层信息的双向搜索和边缘修剪的用法。这些加速技术效果很好，但是最新的算法在所有方面都优于这些技术。使用当前的算法，在大陆公路网络上，最短路径的计算时间可少于一毫秒。Dijkstra的未修改算法的快速实现大约需要10秒。

《工程快速路线规划算法》一书概述了该领域的研究进展。有关更多信息，请参见该文件的参考。

已知最快的算法不会在数据中使用有关道路分层状态的信息，即公路是公路还是本地道路。取而代之的是，它们在预处理步骤中计算自己的层次结构，并对其进行优化以加快路线规划。然后可以使用这种预计算来简化搜索：在Dijkstra算法中，无需考虑远离起点和目的地的慢行道路。好处是非常好的性能和结果的正确性保证。

第一个优化的路线规划算法仅处理静态道路网络，这意味着图中的边具有固定的成本值。实际上，这不是真的，因为我们要考虑动态信息，例如交通拥堵或与车辆相关的限制条件。最新的算法也可以解决此类问题，但仍有许多问题需要解决，并且研究正在进行中。

如果您需要最短的路径距离来为TSP计算解决方案，那么您可能会对包含源与目标之间的所有距离的矩阵感兴趣。为此，您可以考虑使用高速公路层次结构计算多对多最短路径。请注意，在过去的两年中，这已经通过更新的方法得到了改善。