什么算法在地图上计算从点A到点B的方向？
地图提供商（如Google或Yahoo! Maps）如何提供方向建议？
我的意思是，他们可能以某种形式存在真实世界的数据，当然包括距离，但也可能包括驾驶速度，人行道，列车时刻表等等。但假设数据是一种更简单的格式，比如一个非常大的有向图边缘权重反映距离。 我希望能够快速计算从一个任意点到另一个点的方向。 有时候这些点会在一起（在一个城市内）接近，而有时它们会相距甚远（跨国）。
像Dijkstra算法这样的图形算法将不起作用，因为图形非常庞大。 幸运的是，像A *这样的启发式算法可能会起作用。 但是，我们的数据是非常有条理的，也许某种分层方法可能有用？ （例如，存储相距很远的某些“关键”点之间的预先计算的方向以及一些局部方向，然后两个远处点的方向将涉及到关键点的局部方向，另一个关键点的全局方向，然后是局部再次指示。）
在实践中实际使用哪些算法？
PS。 这个问题的动机是发现在线测绘方向的怪癖。 与三角形不平等相反，有时谷歌地图认为XZ需要更长的时间，并且比使用XYZ中的中间点更远。 但是，也许他们的步行方向也可以优化另一个参数？
PPS。 这是另一种违反三角形不平等的表现（对我来说）他们使用某种分层方法：XZ与XYZ。 前者似乎使用着名的塞瓦斯托波尔大道，虽然它略微偏离了道路。
编辑 ：这些例子都没有工作了，但都在原来的帖子时。
作为一个在地图绘制公司工作了18个月的人，其中包括在路由算法方面的工作......是的，Dijkstra's确实有效，并做了一些修改：
通过这些修改，您甚至可以在非常合理的时间范围内完成跨国路由。
这个问题在过去几年一直是一个活跃的研究领域。 主要思想是对图形进行一次 预处理 ，以加速所有后续查询 。 有了这些附加信息，可以非常快地计算行程。 尽管如此， Dijkstra的算法是所有优化的基础。
Arachnid描述了基于分层信息的双向搜索和边缘修剪的用法。 这些加速技术工作得很好，但最新的算法通过一切手段胜过这些技术。 使用当前的算法，可以在大陆路网上以比毫秒少得多的时间来计算最短路径。 未经修改的Dijkstra算法的快速实现需要大约10秒 。
文章工程快速路线规划算法给出了该领域研究进展的概述。 有关更多信息，请参阅该文件的参考资料。
已知最快的算法不使用关于数据中道路的分层状态的信息，即，如果是公路或当地道路。 相反，他们在预处理步骤中计算自己的层次结构，以便加快路线规划。 这个预计算然后可以用来修剪搜索：远离开始和目的地慢速道路在Dijkstra算法期间不需要考虑。 好处是非常好的性能和结果的正确性保证。
第一种优化的路线规划算法仅处理静态道路网络，这意味着图中的边缘具有固定的成本值。 实际情况并非如此，因为我们想要考虑交通堵塞或依赖车辆限制等动态信息。 最新的算法也可以处理这些问题，但仍然存在需要解决的问题和正在进行的研究。
如果您需要最短路径距离来计算TSP的解决方案，那么您可能对包含源和目标之间所有距离的矩阵感兴趣。 为此，您可以考虑使用公路层次结构计算多对多最短路径。 请注意，过去两年新方法改善了这一点。
只要解决三角形不平等违规问题，希望他们优化的额外因素是常识。 你不一定需要最短或最快的路线，因为它可能导致混乱和破坏。 如果你想让自己的路线更喜欢卡车友好的主要路线，并且可以应付让每个坐着驾驶员的司机下车，那么你很快就会丢弃三角形的不平等[1]。
如果Y是X和Z之间狭窄的住宅街道，如果用户明确要求XYZ，则可能只想通过Y使用快捷方式。 如果他们要求XZ，他们应该坚持主要道路，即使它稍远一点，需要更长的时间。 这与Braess的悖论相似 - 如果每个人都试图采用最短，最快的路线，则由此产生的拥堵意味着它不再是任何人的最快路线。 从这里我们偏离图论到博弈论。
[1]事实上，当你允许单向道路并失去对称性要求时，任何希望产生的距离都将成为数学意义上的距离函数。 失去三角形不平等也只是在伤口上擦盐。
链接地址: http://www.djcxy.com/p/29209.html上一篇: What algorithms compute directions from point A to point B on a map?