Map 提供商（例如Google或Yahoo! Maps）如何提供方向？
我的意思是，他们可能有某种形式的真实数据，当然包括距离，但也可能包括行驶速度，人行道的存在，火车时刻表等 . 但是假设数据格式较简单，比如一个非常大的有向图边缘权重反映距离 . 我希望能够快速计算从任意点到另一个点的方向 . 有时这些点将在一起（在一个城市内），而有时它们将相隔很远（越野） .
像Dijkstra算法这样的图算法是行不通的，因为图是巨大的 . 幸运的是，像A *这样的启发式算法可能会起作用 . 但是，我们的数据非常有条理，也许某种分层方法可能有用吗？ （例如，存储远离某些“关键”点之间的预先计算方向，以及一些局部方向 . 然后，两个远点的方向将涉及到关键点的本地方向，到另一个关键点的全局方向，然后是本地方向方向再次 . ）
在实践中实际使用了哪些算法？
PS . 这个问题的动机是在在线 Map 方向找到怪癖 . 与三角形不等式相反，有时谷歌 Map 认为X-Z需要更长时间，并且比使用X-Y-Z中的中间点更远 . 但也许他们的步行路线也会针对另一个参数进行优化？
PPS . 这是对三角不等式的另一个违反，它暗示（对我而言）他们使用某种分层方法：X-Z与X-Y-Z . 前者似乎使用着名的Boulevard de Sebastopol，尽管它稍微偏离了方向 .
Edit ：这两个例子似乎都不再起作用，但两者都是在原始帖子时发生的 .
18 回答
Map 从不考虑整个 Map . 我的猜测是： - 1.根据你的位置，他们在那个地方装载一个地方和地标 . 2.当您搜索目的地时，那就是当他们加载 Map 的其他部分并从两个地方制作图表然后应用最短路径算法 .
此外，还有一项重要的技术动态编程我怀疑它用于计算最短路径 . 你也可以参考它 .
只是解决三角不等式违规问题，希望他们必须想要最短或最快的额外因素，因为它可能导致chaos and destruction . 如果你希望你的方向更喜欢卡车友好的主要路线，并且能够应对每个坐骑导航跟随司机发送它们，你很快就会丢弃三角形不等式[1] .
如果Y是X和Z之间的狭窄住宅街道，如果用户明确要求X-Y-Z，您可能只想通过Y使用快捷方式 . 如果他们要求X-Z，他们应该坚持主要道路，即使它类似于Braess's paradox - 如果每个人都试图采取最短，最快的路线，由此产生的拥堵意味着它不再是任何人的最快路线 . 从这里我们偏离了图论到博弈论 .
[1]事实上，当你允许单向道路并失去对称性要求时，任何希望所产生的距离将成为数学意义上的距离函数 . 失去三角不等也只是在伤口擦盐 .
我已经在路由工作了几年，最近我的客户需求引发了一系列的活动，我发现A *很快就够了;实际上没有必要寻找优化或更复杂的算法 . 在巨大的图表上进行路由不是问题 .
但速度取决于拥有整个路由网络，我指的是分别在内存中表示路径段和连接点的弧和节点的有向图 . 主要的时间开销是创建此网络所需的时间 . 基于普通笔记本电脑运行Windows的一些粗略数字，以及整个西班牙的路由：创建网络的时间：10-15秒;计算路线所花费的时间：太短无法衡量 .
另一个重要的事情是能够重新使用网络进行任意数量的路由计算 . 如果您的算法以某种方式标记节点以记录最佳路径（当前节点的总成本，以及最佳弧度） - 就像在A *中一样 - 您必须重置或清除这些旧信息 . 与使用数十万个节点不同，使用世代数系统更容易 . 用每个节点的数据世代号标记每个节点;计算新路线时增加世代号;具有较旧世代号的任何节点都是陈旧的，并且可以忽略其信息 .
就静态道路网络的查询时间而言，现有技术是Abraham等人提出的Hub标记算法 . http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . 最近发布了一份通过并且写得非常好的该领域调查作为Microsoft技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .
简短的版本是......
Hub标记算法为静态道路网络提供最快的查询，但需要运行大量的ram（18 GiB） .
Transit节点路由稍微慢一点，但它只需要大约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/
这个问题在过去几年一直是一个活跃的研究领域 . 主要想法是在图表 once 上执行 preprocessing ，到 speed up 所有 following queries . 通过这些附加信息，可以非常快速地计算行程 . 仍然， Dijkstra's Algorithm 是所有优化的基础 .
Arachnid描述了基于分层信息的双向搜索和边缘修剪的使用 . 这些加速技术工作得很好，但最新的算法无论如何都要胜过这些技术 . 使用当前算法，可以在比大陆公路网上更短的时间内计算最短路径 . Dijkstra的未修改算法的快速实现需要 10 seconds .
文章Engineering Fast Route Planning Algorithms概述了该领域的研究进展 . 有关详细信息，请参阅该论文的参考资料 .
最快的已知算法不使用关于数据中道路的分层状态的信息，即，如果它是高速公路或本地道路 . 相反，他们在预处理步骤中计算自己的层次结构，该层次结构经过优化以加速路径规划 . 然后可以使用该预计算来修剪搜索：在Dijkstra算法期间，不需要考虑远离起点和目的地的慢速道路 . 结果的好处是非常好 performance 和 correctness 保证 .
第一个优化的路线规划算法仅处理静态道路网络，这意味着图中的边缘具有固定的成本值 . 这在实践中并非如此，因为我们想要考虑交通拥堵或车辆相关限制的动态信息 . 最新算法也可以处理这些问题，但仍有问题需要解决，研究正在进行中 .
如果您需要最短的路径距离来计算 TSP 的解决方案，那么您可能对包含源和目标之间所有距离的矩阵感兴趣 . 为此你可以考虑Computing Many-to-Many Shortest Paths Using Highway Hierarchies . 请注意，在过去的两年中，这种方法已经得到了改进 .
这是世界上最快的路由算法，比较并证明了正确性：
http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf
这是关于这个主题的谷歌技术讲座：
http://www.youtube.com/watch?v=-0ErpE8tQbw
这是schultes讨论的高速公路 - 层次结构算法的实现（目前仅在柏林，我正在编写接口，并且正在开发移动版本）：
http://tom.mapsforge.org/
这个论点不一定成立，因为Dijkstra通常不会查看完整的图形，而只是一个非常小的子集（图形越好互连，该子集越小） .
对于表现良好的图表，Dijkstra实际上可能表现得相当好 . 另一方面，通过仔细的参数化，A *总能表现得更好或更好 . 您是否已经尝试过如何对数据执行操作？
也就是说，我也很想知道其他人的经历 . 当然，谷歌 Map 搜索等突出的例子特别有趣 . 我可以想象像定向最近邻居启发式的东西 .
可能类似于主要位置和分层 Map 之间的预先计算路线的答案，但我的理解是，在游戏中，为了加速A *，你有一张非常粗略的 Map 用于宏观导航，并且有一个细粒度的 Map 导航到宏观方向的边界 . 因此，您有2个小路径可供计算，因此您的搜索空间远远小于仅仅执行到目的地的单个路径 . 如果您经常这样做，那么您需要预先计算大量的数据，因此至少部分搜索是搜索预先计算的数据，而不是搜索路径 .
全对最短路径算法将计算图中所有顶点之间的最短路径 . 这将允许预先计算路径，而不是每当有人想要找到源和目的地之间的最短路径时需要计算路径 . Floyd-Warshall算法是一对全对最短路径算法 .
这是我的纯粹猜测，但我想他们可能会使用覆盖定向 Map 的影响 Map 数据结构来缩小搜索范围 . 这将允许搜索算法在期望的旅行很长时将路径引导到主要路线 .
鉴于这是一个谷歌应用程序，假设通过广泛的缓存完成了很多魔术也是合理的 . :)如果缓存前5％最常见的谷歌 Map 路线请求允许通过简单的查找来回答大块（20％~50％？）的请求，我不会感到惊讶 .
作为在 Map 公司工作了18个月的人，其中包括研究路由算法......是的，Dijkstra's确实有效，只需进行一些修改：
而不是从源到目标执行Dijkstra's，而是从每一端开始，然后展开两边直到它们在中间相遇 . 这消除了大约一半的工作（2 * pi *（r / 2）^ 2 vs pi * r ^ 2） .
为了避免探索源和目的地之间每个城市的后巷，您可以拥有多层 Map 数据：仅包含高速公路的'highways'图层，仅包含次要街道的'secondary'图层，依此类推 . 然后，你探索只有更详细的图层的较小部分，根据需要扩展 . 显然，这个描述遗漏了很多细节，但你明白了 .
通过这些方面的修改，您甚至可以在非常合理的时间范围内进行跨国路由 .
我对使用的启发式方法非常好奇，不久前我们从圣罗莎附近的同一起始位置到约塞米蒂国家公园的两个不同的露营地 . 这些不同的目的地产生了完全不同的路线（通过I-580或CA-12），尽管两条路线在最后100英里（沿着CA-120）汇合，然后在最后几英里再次发散 . 这是非常可重复的 . 这两条路线相距50英里，行程约100英里，但距离/时间非常接近，正如您所期望的那样 .
唉，我无法重现 - 算法必须改变 . 但它让我对这个算法感到好奇 . 我可以推测的是，有一些定向修剪恰好对从远处看到的目的地之间的微小角度差异非常敏感，或者通过选择最终目的地选择了不同的预先计算的分段 .
我之前没有在谷歌，微软或雅虎 Map 上工作，所以我不能告诉你它们是如何工作的 .
然而，我确实为一家能源公司设计了一个定制的供应链优化系统，其中包括为其车队提供的调度和路由应用 . 但是，我们的路线标准远比建筑或交通减速或车道关闭更具商业性 .
我们采用了一种名为ACO（蚁群优化）的技术来安排和路由卡车 . 这种技术是一种AI技术，应用于旅行商问题以解决路由问题 . ACO的技巧是根据路由的已知事实构建错误计算，以便图解决模型知道何时退出（何时错误足够小） .
您可以使用Google ACO或TSP来查找有关此技术的更多信息 . 我没有使用任何开源AI工具，所以不能建议一个（虽然我听说SWARM非常全面） .
我已经做了很多次，实际上，尝试了几种不同的方法 . 根据 Map 的大小（地理位置），您可能需要考虑使用hasrsine函数作为启发式 .
我所做的最好的解决方案是使用具有直线距离的A *作为启发式函数 . 但是，你需要为 Map 上的每个点（交叉点或顶点）提供某种坐标 . 您还可以尝试不同的启发函数权重，即
其中k是某个大于0的常数 .
说到GraphHopper，一个基于OpenStreetMap的快速开源路由规划器，我已经阅读了一些文献并实现了一些方法 . 最简单的解决方案是Dijkstra，简单的改进是双向Dijkstra，它大致只探索了一半的节点 . 通过双向Dijkstra，通过整个德国的路线已经需要1秒（对于汽车模式），在C中它可能只有0.5秒左右;）
我用双向Dijkstra here创建了一个真实路径搜索的GIF动画 . 还有更多的想法make Dijkstra faster喜欢做A *，这是一个"goal-oriented Dijkstra" . 我也为它创建了一个gif-animation .
But how to do it (a lot) faster?
问题在于，对于路径搜索，必须探索位置之间的所有节点，并且这实际上是昂贵的，因为德国已有数百万个节点 . 但Dijkstra等另一个痛点就是这样的搜索会使用很多内存
有启发式解决方案，但也有确切的解决方案，在层次结构层中组织图形（道路网络），既有利弊，主要解决速度和RAM问题 . 我在this answer中列出了其中一些 .
对于GraphHopper，我决定使用Contraction Hierarchies因为它是相对的'easy'实现，并且不需要花费很长时间来准备图形 . 它仍然会导致非常快的响应时间，就像您可以在我们的在线实例GraphHopper Maps进行测试一样 . 例如 . from south Africa to east China这导致了23000km的距离和近14天的驾驶时间，并且在服务器上只花了0.1秒 .
我有点不高兴看不到这里提到的Floyd Warshall's algorithm . 该算法工作's very much like Dijkstra' s . 它还有一个非常好的功能，它允许您计算，只要您想继续允许更多的中间顶点 . 因此，它会自然地找到使用州际公路或高速公路的路线 .
我对此有了更多的想法：
1）请记住， Map 代表一个物理组织 . 存储每个交叉路口的纬度/经度 . 您不需要检查远远超出目标方向的点 . 只有当你发现自己被阻止时，你才需要超越这个范围 . 如果你存储一个优质连接的叠加层，你可以限制它 - 你通常不会以远离最终目的地的方式穿过其中一个 .
2）将世界划分为由有限连接定义的一大堆区域，定义区域之间的所有连接点 . 查找源和目标所在的区域，从您的位置到每个连接点的起始和结束区域路径，以及简单地在连接点之间映射的区域 . （我怀疑很多后者已经预先计算好了 . ）
请注意，区域可能小于都市区域 . 任何具有地形特征的城市（例如河流）将是多个区域 .
我看到OP中的 Map 有什么用：
查看指定中间点的路线：由于道路不直，路线略微向后移动 .
如果他们的算法不会回溯，它将看不到更短的路线 .