什么算法计算地图上从A点到B点的方向?

这纯粹是我的猜测，但我认为他们可能会使用覆盖有向图的影响图数据结构，以缩小搜索域。这将允许搜索算法在所需行程较长时将路径导向主要路线。

鉴于这是一个谷歌应用程序，我们也可以合理地假设，许多神奇的功能都是通过大量缓存完成的。如果缓存前5%最常见的谷歌地图路由请求，我不会感到惊讶(20%?50%?)的请求需要通过简单的查询来回答。

像Dijkstra算法这样的图算法将无法工作，因为图是巨大的。

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

对于行为良好的图，Dijkstra实际上可能表现得相当好。另一方面，通过仔细的参数化，A*总是表现得一样好，甚至更好。您是否已经尝试过它对数据的处理方式?

也就是说，我也很有兴趣听听其他人的经历。当然，像谷歌Map搜索这样的突出例子是特别有趣的。我可以想象类似于有向近邻启发式的东西。

我知道OP里的地图是怎么回事了:

用指定的中间点来观察路线:由于那条路不直，这条路线略微向后走。

如果他们的算法不会回溯，它就看不到更短的路线。

作为一个在地图公司工作了18个月的人，其中包括研究路由算法……是的，Dijkstra算法的做了一些修改:

• 不是从source到dest执行一次Dijkstra算法的，而是从每一端开始，然后展开两边，直到它们在中间相遇。这省去了大约一半的工作(2* *(r/2)^2 vs *r^2)。
• 为了避免探索源和目的地之间每个城市的后巷，可以有几个地图数据层:“高速公路”层只包含高速公路，“次要”层只包含次要街道，以此类推。然后，您只探索更详细的层的较小部分，并根据需要展开。显然，这个描述遗漏了很多细节，但您可以理解。

通过沿着这些路线进行修改，您甚至可以在非常合理的时间范围内完成跨国家路由。

这个问题在过去几年中一直是一个活跃的研究领域。主要思想是在图一次上做一个预处理，到加快全部下面的查询。有了这些附加信息，行程可以很快计算出来。尽管如此，迪杰斯特拉算法仍然是所有优化的基础。

蛛形纲动物的描述了双向搜索和基于层次信息的边缘修剪的使用。这些加速技术工作得很好，但最新的算法在任何方面都优于这些技术。使用目前的算法，在大陆公路网上计算最短路径的时间比一毫秒要短得多。快速实现未修改的Dijkstra算法需要10秒左右。

文章工程快速路线规划算法概述了该领域的研究进展。有关进一步信息，请参阅那篇论文的参考文献。

已知最快的算法不使用数据中关于道路层次状态的信息，即它是高速公路还是本地道路。相反，他们在预处理步骤中计算自己的层次结构，优化以加快路线规划。这种预计算可以用来精简搜索:在Dijkstra算法中，远离起点和目的地的缓慢道路不需要考虑。好处是非常好的性能和正确性的结果保证。

第一个优化的路线规划算法只处理静态道路网络，这意味着图中的边缘具有固定的成本值。这在实践中是不正确的，因为我们想要考虑交通堵塞或车辆相关限制等动态信息。最新的算法也可以处理这些问题，但仍有问题需要解决，研究还在继续。

如果您需要最短路径距离来计算茶匙的解，那么您可能对包含源和目的地之间所有距离的矩阵感兴趣。你可以考虑利用高速公路层次计算多对多最短路径。请注意，在过去的两年里，这已经通过更新的方法得到了改进。

我对此有了更多的想法:

1)记住地图代表一个实体组织。存储每个交叉口的经纬度。除了目标方向上的点以外，你不需要检查太多。只有当你发现自己受阻时，你才需要超越这一点。如果你储存了大量的高级连接，你就可以进一步限制它们——通常情况下，你永远不会以偏离最终目的地的方式穿过其中任何一个连接。

2)根据有限的连通性将世界划分为一系列区域，定义区域之间的所有连通性点。找出您的源和目标所在的区域，从您的位置到每个连接点的起始和结束区域路由，以及连接点之间的区域映射。(我怀疑后者在很大程度上是事先计算好的。)

请注意，区域可以比大都市区域小。任何具有地形特征的城市(比如一条河)都是多个区域。

只是解决三角形不等式的违反，希望他们优化的额外因素是常识。你不一定想要最短或最快的路线，因为它可能会导致混乱 而且 破坏。如果你想让自己的路线更适合卡车行驶，并且能够应对每个卫星导航跟踪司机都沿着这些路线行驶的情况，那么你很快就可以放弃三角形不等式[1]。

如果Y是X和Z之间的一条狭窄的住宅街道，那么您可能只想在用户明确要求X-Y-Z时使用通过Y的快捷方式。如果他们要求X-Z，他们应该坚持走主干道，即使它有点远，需要更长的时间。它类似于Braess悖论——如果每个人都试图走最短、最快的路线，所导致的拥堵意味着它不再是任何人最快的路线。从这里开始，我们将从图论转向博弈论。

事实上，当你允许单向道路并失去对称性要求时，任何产生的距离将是数学意义上的距离函数的希望都将破灭。失去三角不等式也只是在伤口上撒盐。

我以前没有在谷歌或微软或雅虎地图工作过，所以我不能告诉你他们是如何工作的。

然而，我确实为一家能源公司设计了一个定制的供应链优化系统，其中包括为他们的卡车车队提供调度和路由应用程序。然而，我们对路线的标准远比建筑、交通减速或车道封闭的地方更具体。

我们采用了一种称为ACO(蚁群优化)的技术来调度和路线卡车。该技术是一种人工智能技术，应用于旅行推销员问题来解决路由问题。ACO的技巧是基于路由的已知事实构建错误计算，以便图求解模型知道何时退出(当错误足够小时)。

你可以谷歌ACO或TSP找到更多关于这个技术。然而，我没有使用过任何开源AI工具，所以不能推荐一个(尽管我听说SWARM非常全面)。

这可能与主要地点之间的预先计算路线和分层地图的答案相似，但我的理解是，在游戏中，为了加速A*，你需要一个用于宏观导航的非常粗糙的地图，以及一个用于导航到宏观方向边界的细粒度地图。所以你有两条小路径要计算，因此你的搜索空间要比只走一条路到目的地小得多。如果你经常做这种事，你会有很多预先计算好的数据所以至少部分搜索是对预先计算好的数据的搜索，而不是对路径的搜索。

事实上，我已经做过很多次了，尝试了几种不同的方法。根据地图的大小(地理位置)，您可能会考虑使用haversine函数作为启发式方法。

我的最佳解决方案是使用带有直线距离的A*作为启发式函数。但接下来你需要地图上每个点(交集或顶点)的某种坐标。您还可以为启发式函数尝试不同的权重，即。

f(n) = k*h(n) + g(n)

k是一个大于0的常数。

我有点惊讶这里没有提到Floyd Warshall的算法。这个算法很像Dijkstra算法。它还有一个很好的特性，那就是它允许你计算，只要你想继续允许更多的中间顶点。因此，它自然会很快找到使用州际公路或高速公路的路线。

以下是世界上最快的路由算法的比较和正确性:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

下面是谷歌关于这个主题的技术演讲:

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

以下是schultes所讨论的高速公路层次算法的实现(目前仅在柏林，我正在编写界面，移动版本也正在开发中):

http://tom.mapsforge.org/

我对使用的启发式非常好奇，当我们从圣罗莎附近的同一个起始地点得到路线，到约塞米蒂国家公园的两个不同的露营地。这些不同的目的地产生了截然不同的路线(通过I-580或CA-12)，尽管这两条路线在最后100英里(沿着CA-120)交汇，然后在最后再次分开几英里。这是相当可重复的。这两条路线相距50英里，大约100英里，但距离/次数非常接近，正如你所期望的那样。

唉，我无法重现——算法肯定已经改变了。但这让我对算法很好奇。我所能推测的是，有一些方向修剪，恰好对从远处看的目的地之间的微小角度差异非常敏感，或者有不同的最终目的地选择的预先计算的片段。

我已经在路由方面工作了几年，最近由于客户的需求而引起了大量的活动，我发现a *很容易就足够快了;真的没有必要去寻找优化或更复杂的算法。在一个巨大的图上路由不是问题。

但是速度取决于整个路由网络，我指的是在内存中分别表示路由段和节点的有向图。主要的时间开销是创建这个网络所花费的时间。基于一台运行Windows系统的普通笔记本电脑，并在整个西班牙进行路由的一些粗略数字:创建网络所需时间:10-15秒;计算路线所花费的时间:太短而无法测量。

另一件重要的事情是能够重用网络进行尽可能多的路由计算。如果你的算法以某种方式标记了节点，以记录最佳路径(到当前节点的总成本，以及到该节点的最佳弧)——就像在A*中那样——你必须重置或清除这些旧信息。使用代数系统更容易，而不是通过数十万个节点。用其数据的代号标记每个节点;计算新路由时增加代数;任何具有较旧代号的节点都是过时的，可以忽略其信息。

就静态道路网络的查询时间而言，目前最先进的技术是Abraham等人提出的Hub标签算法。微软技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf最近发布了一份关于该领域的完整且出色的调查报告。

简短的说法是……

Hub标签算法为静态道路网络提供了最快的查询，但需要大量ram来运行(18 GiB)。

传输节点路由稍慢，不过它只需要大约2 GiB的内存，并且有更快的预处理时间。

收缩层次结构在快速预处理时间、低空间需求(0.4 GiB)和快速查询时间之间提供了一个很好的平衡。

没有一种算法是完全占主导地位的……

彼得·桑德斯的谷歌科技演讲可能会让你感兴趣

https://www.youtube.com/watch?v=-0ErpE8tQbw < a href = " https://www.youtube.com/watch?v=-0ErpE8tQbw " > < / >

还有Andrew Goldberg的演讲

https://www.youtube.com/watch?v=WPrkc78XLhw < a href = " https://www.youtube.com/watch?v=WPrkc78XLhw " > < / >

压缩层次结构的开源实现可从KIT的Peter Sanders研究小组网站获得。# EYZ0

还有一篇微软写的关于CRP算法用法的博客文章…# EYZ0

我用双向Dijkstra 在这里创建了一个真实路径搜索的动画gif。此外，使Dijkstra更快还有一些更多的想法，比如做A*，这是一个“目标导向的Dijkstra”。我还为它创建了gif动画。

但是怎样才能(快得多)呢?

问题是，对于路径搜索来说，必须探索位置之间的所有节点，这是非常昂贵的，因为在德国已经有数百万个节点了。但是Dijkstra等的另一个痛点是这样的搜索使用大量的RAM。

有启发式解决方案，也有精确解决方案，将图(路网)分层组织，两者都有优缺点，主要解决速度和内存问题。我在这个答案中列出了其中一些。

对于GraphHopper，我决定使用收缩的层次结构，因为它相对“容易”实现，并且不需要花很长时间来准备图表。它仍然会导致非常快的响应时间，就像你可以在我们的在线实例GraphHopper地图中测试一样。例如从南非到中国东部，结果是23000公里的距离和近14天的汽车驾驶时间，在服务器上只花了0.1秒。

此外，还有一个重要的技术动态规划，我怀疑是用在最短路径的计算。你也可以参考一下。

全对最短路径算法将计算图中所有顶点之间的最短路径。这将允许预先计算路径，而不需要每次寻找源和目的地之间的最短路径时都计算路径。Floyd-Warshall算法是一种全对最短路径算法。