logo标签列表

什么算法可以计算在地图上从点A到点B的方向？

algorithmpath-finding
567

地图提供商（比如谷歌或雅虎地图）是如何建议路线的呢？

它们可能有某种形式的真实世界数据，肯定包括距离，但也可能包括行驶速度、人行道存在情况、火车时间表等等。但假设数据以更简单的格式存在，例如一个非常大的有向图，边缘权重反映距离。我想能够快速计算从任意一点到另一点的方向。有时这些点会很近（在同一个城市内），而有时它们会很远（横跨全国）。

像Dijkstra算法这样的图形算法不适用于庞大的图形。幸运的是，启发式算法，如A *算法，可能有效。然而，我们的数据非常结构化，也许一种分层方法可能会起作用？（例如，在某些遥远的“关键”点之间存储预先计算的方向，以及一些本地方向。然后，两个远离的点的方向将涉及到关键点的本地方向，到另一个关键点的全局方向，以及再次的本地方向。）

实际上使用了哪些算法？

附注：此问题的动机是在在线地图方向中发现的异常。与三角不等式相反，有时候Google Maps认为使用一个中间点作为 X-Y-Z 比使用 X-Z 更长更远。但也许他们的步行路线也优化了另一个参数呢？

附注：这里又有一个违反三角不等式的例子，它表明（对我来说）他们使用某种分层方法：X-Z与X-Y-Z。前者似乎使用了显眼的Sebastopol大道，即使它略微偏离了路线。

编辑：这些例子都似乎不再起作用，但在原始帖子发布时，两者都有效。

3
顺便提一句，A*算法是对Dijkstra算法的一种推广，如果有额外信息可以提供到目标点的下限距离，它可以减少需要探索的子图大小。 - Mitch Wheat
关于A*算法：是的，确实如此。幸运的是，在我们的情况下，“额外信息”可以通过使用直线距离等方式得到。当我上面说“Dijkstra”时，我指的是基本的Dijkstra算法。 - A. Rex
步行路线？不知道其他地方怎么样，但在这里（英国汉普郡），谷歌没有行人数据 - 它会将我沿着行人区周围的道路路由。它唯一有用的是更改路线所需时间的估计 :) - jTresidder
我并不特别在意这些指南是用于驾车还是步行。我只想知道它们是如何工作的！我添加步行链接的原因是因为我正在计算一种步行环绕巴黎并看到所有66个华莱士喷泉的方法。（这些地图的端点应该是华莱士喷泉。） - A. Rex
@John：我知道。我确实在尝试解决旅行商问题的一个实例。作为子程序，我向谷歌请求步行路线，并出于好玩检查了三角不等式。 - A. Rex
显示剩余3条评论
18个回答
548

作为一位曾在地图公司工作18个月的人，其中包括开发路由算法... 是的，Dijkstra算法可以使用，但需要进行一些修改：

  • 不是从源点到目标点只进行一次Dijkstra，而是从两端同时开始，每次向中间扩展，直到两端相遇。这样可以减少大约一半的工作量（2*pi*(r/2)^2 vs pi*r^2）。
  • 为了避免在源点和目标点之间探索每个城市的背街小巷，可以有多层地图数据：一个“高速公路”层，只包含高速公路；一个“次要道路”层，只包含次要道路，依此类推。然后，您只需探索更详细的层的较小部分，必要时进行扩展。很明显，这种描述省略了很多细节，但您可以理解其基本思想。

通过这些修改，甚至可以在非常合理的时间内完成跨国路径规划。

29
在现实世界中从事这项工作的人，太棒了！你有没有想过在Google文章中提到的那样可以预先计算多少内容？ - A. Rex
10
我们没有进行任何这样的预处理，但这确实看起来像是一个有趣的优化方法。 - Nick Johnson
29
“它只保证产生一个解决方案，但不一定是最有效的”这种说法是不正确的。只要所使用的启发式是可接受的，A算法就会生成最小成本路径。可接受的意思是代价永远不会被高估，但可能会被低估（但不良的估计将减慢算法）。使用预处理数据很可能有助于制作更好的可接受启发式，并因此使A算法工作更快。 - a1kmm
6
经过进一步的考虑，你是完全正确的。 你可以通过将目标节点和目的地之间的“大圆距离”添加到正在评估的边缘的成本中来增强现有算法。 我其实不确定我们的算法是否这样做了，但这是一个非常明智的优化。 - Nick Johnson
12
在最坏情况下（即所有路径都等效的一种启发式算法），A*算法恰好等于Djikstra算法。 - Tordek
显示剩余7条评论
114

这些年来，这个问题一直是研究的热点。主要思想是对图进行预处理，以加快所有后续查询的速度。有了这些额外的信息，可以非常快速地计算路径。但是，Dijkstra算法仍然是所有优化的基础。

Arachnid 描述了基于层次信息的双向搜索和边缘剪枝的使用。这些加速技术效果很好，但最近的算法在各个方面都优于这些技术。使用当前的算法，在大陆道路网络上可以在相当短的时间内计算出最短路径，不到1毫秒。一个未经修改的Dijkstra算法的快速实现需要约10秒。

文章《工程快速路径规划算法》概述了这一领域中研究的进展。有关详细信息，请参见该论文的参考文献。

目前已知最快的算法不使用有关数据中路段的层级状态的信息，即无论它是高速公路还是本地道路，它们都会在预处理步骤中计算出自己的层次结构，以优化路线规划。然后可以使用这个预处理信息来剪枝搜索：在起点和终点远离的地方，不需要考虑缓慢的道路，而只需要使用Dijkstra算法。好处是性能非常好，结果具有正确性保证。

最早优化的路径规划算法仅处理静态道路网络，即图中的边具有固定的成本值。但实际上并非如此，因为我们希望考虑动态信息，例如交通阻塞或车辆依赖限制。最新的算法也可以处理这些问题，但仍需解决一些问题，研究正在进行中。

如果您需要计算TSP的解决方案所需的最短路径距离，则可能会对包含源和目的地之间所有距离的矩阵感兴趣。为此，您可以考虑使用使用高速公路层次结构计算多对多最短路径。请注意，近两年来，这一方法已经得到改进。
1
确实很有启发性。你提到的新方法是什么？ - Tomas Pajonk
1
特别是缩减层次结构。您可以在此处了解更多信息：http://algo2.iti.kit.edu/routeplanning.php。还有一段关于它的Google技术讲座：http://www.youtube.com/watch?v=-0ErpE8tQbw。 - SebastianK
19

仅解决三角不等式违规问题，希望他们优化的额外因素是常识。你并不一定想要最短或最快的路线，因为这可能会导致混乱 和 破坏。如果你希望你的路线图更倾向于那些适合卡车行驶、可以处理每个卫星导航跟随司机的主要路线，你很快就会放弃三角不等式[1]。

如果 Y 是 X 和 Z 之间的狭窄住宅区街道，只有当用户明确请求 X-Y-Z 时，您才可能希望使用通过 Y 的捷径。如果他们请求 X-Z，则应坚持使用主要道路，即使它稍微远一些，需要花费更长时间。这类似于布雷斯悖论-如果每个人都试图走最短、最快的路线，结果拥堵意味着这对任何人来说都不是最快的路线。从这里我们就偏离了图论进入到博弈论。

[1] 实际上，当您允许单向道路并且失去对称性要求时，任何希望所产生的距离符合数学意义上的距离函数的希望都消失了。同时失去三角不等式只是雪上加霜。

16
10
目前在静态道路网络查询时间方面最先进的技术是由Abraham等人提出的Hub标记算法http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20。最近，微软公司发布了一份详尽而出色的技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf，对该领域进行了概述。
简短的版本是：
虽然Hub标记算法提供了静态道路网络最快的查询速度，但需要大量的内存运行（18 GiB）。
Transit node routing稍慢一些，但只需要约2 GiB的内存，且预处理时间更快。
收缩层次结构在快速预处理时间、低空间要求（0.4 GiB）和快速查询时间之间提供了不错的平衡。
没有一种算法是完全占优的……
Peter Sanders的这个Google技术讲座可能会引起兴趣。

https://www.youtube.com/watch?v=-0ErpE8tQbw

此外，这是Andrew Goldberg的演讲。

https://www.youtube.com/watch?v=WPrkc78XLhw

可以从KIT的Peter Sanders研究小组网站上获取收缩分层的开源实现。http://algo2.iti.kit.edu/english/routeplanning.php

此外，Microsoft撰写了一篇易于访问的博客文章，介绍了他们使用CRP算法的情况...http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

9

我以前没有在Google、Microsoft或Yahoo Maps工作过，所以我不能告诉你它们是如何工作的。

不过，我曾经为一家能源公司设计了一个定制的供应链优化系统，其中包括一个调度和路径规划应用程序，用于管理他们的卡车车队。然而，我们的路径规划标准比建筑位置、交通缓慢或车道关闭等更加具有业务特定性。

我们采用了一种名为ACO（蚁群算法优化）的技术来进行卡车的调度和路径规划。这种技术是一种人工智能技术，应用于解决旅行商问题的路径规划问题。使用ACO的关键是基于已知的路径信息构建一个误差计算，使得图形求解模型知道何时退出（即误差足够小时）。

您可以在谷歌上搜索ACO或TSP以了解更多相关技术。但我没有使用任何开源的人工智能工具，因此无法推荐一款（尽管我听说SWARM非常全面）。

4
路由与旅行商问题不同。在旅行商问题中，您已知所有距离并优化停留顺序，这不是一种点对点算法。 - Karussell
8

我有点惊讶地发现这里没有提到弗洛伊德-沃舍尔算法。这个算法与Dijkstra算法非常相似。它还有一个非常好的特点，即它允许您计算尽可能多的中间顶点。因此，它可以快速找到使用高速公路或快速道路的路线。

8

由于图形巨大，像Dijkstra算法这样的图形算法将无法使用。

这个论点并不一定成立，因为Dijkstra通常不会查看完整的图形，而只是一个非常小的子集（图形互连性越好，这个子集就越小）。

对于表现良好的图形，Dijkstra实际上可能表现得相当好。另一方面，通过仔细的参数化，A*总是能够表现得同样好或更好。您已经尝试过它在您的数据上的表现了吗？

话虽如此，我也很想听听其他人的经验。当然，像Google Map搜索之类的著名例子特别有趣。我可以想象一个定向最近邻启发式算法。

2
假设你想要找到从点A到点B的路线，其最佳距离为d。Dijkstra算法至少会检查所有距离A不超过d的点。如果A是旧金山，B是波士顿，这意味着它会检查美国的大部分地区。不是吗？ - A. Rex
2
是的，就是这样。我想说的是可以使用A*代替它，并且它总是能找到最优解（尽管使用启发式算法）！ - Konrad Rudolph
当然可以。在我写完原帖后，我想到了我使用的“启发式”一词。这里有点不准确，因为它确实找到了最优解。 - A. Rex
2
好的，问题在于A*使用启发式（相对于成为启发式）来确定下一步。这个决定确实可能是次优的。但它只影响运行时间，而不影响结果，因为它只决定了它比Dijstra猜测得更好多少。 - Konrad Rudolph
6
我已经做过很多次了，尝试了几种不同的方法。根据地图的大小（地理上），您可能需要考虑使用haversine函数作为启发式算法。
我最好的解决方案是使用A*算法，将直线距离作为启发式函数。但是，您需要为地图上的每个点（交叉点或顶点）提供某种坐标。您还可以尝试不同的启发式函数权重，即
f(n) = k*h(n) + g(n)

其中k是大于0的某个常数。

4

在游戏中，为了加快A*算法的速度，通常采用两张地图：一张是粗略的宏观导航地图，另一张是细致的微观导航地图，用于导航到宏观方向的边界。这样，你只需要计算两条小路径，搜索空间就会比单独搜索到目的地的路径小得多。如果你需要频繁进行此类操作，你可以预先计算大量数据，这样一部分搜索过程就变成了对预先计算数据的搜索，而不是搜索路径。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接