我不知道该算法的谷歌地图使用计算2点之间的方向？谷歌有没有提起过这件事？

I wonder which algorithm Google maps use to compute the direction between 2 points ? Has Google ever mentioned about it ?

P / S：我是问算法，谷歌用它来寻找2点之间的最短路径

p/s : I am asking the algorithm which google use to find the shortest route between 2 points.

推荐答案

要尽我所知，谷歌从未公开表示其算法，它使用的P2P查询。虽然在查询时间方面的技术人员从文献中的当前状态是提出Abraham等集线器标记算法。 http://link.springer.com/chapter/10.1007/978 -3-642-20662-7_20 。现场的通过和出色的书面调查最近公布的微软技术报告的 http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf 。

To the best of my knowledge Google has never publicly stated which algorithm it uses of P2P queries. Although the current state of the art from the literature in terms of query times is the Hub labelling algorithm proposed by Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . A through and excellently written survey of the field was recently published as a Microsoft technical report http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

短的版本是...

集线器标记算法可以为静电道路网络最快查询，但需要大量的RAM来运行（18吉布）。

The Hub labelling algorithm provides the fastest queries for static road networks but requires a large amount of ram to run (18 GiB).

传输节点路由稍慢，虽然，只需要大约2吉布的存储器，并具有更快的preprocessing时间

Transit node routing is slightly slower, although, it only requires around 2 GiB of memory and has a quicker preprocessing time.

收缩层次快速preprocessing时间，空间要求低（0.4 GIB）和快速查询时间之间提供了一个很好的权衡。

Contraction Hierarchies provide a nice trade off between quick preprocessing times, low space requirements (0.4 GiB) and fast query times.

没有一种算法是完全主宰......

No one algorithm is completely dominate...

这谷歌技术讲座，由彼得·桑德斯可能会感兴趣

This Google tech talk by Peter Sanders may be of interest

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

另外这个讲座，由安德鲁·戈德堡

Also this talk by Andrew Goldberg

https://www.youtube.com/watch?v=WPrk​​c78XLhw

收缩层次的开源实现可从彼得·桑德斯研究小组的网站套件。 http://algo2.iti.kit.edu/english/routeplanning.php

An open source implementation of contraction hierarchies is available from Peter Sanders research group website at KIT. http://algo2.iti.kit.edu/english/routeplanning.php