地图提供商(如谷歌或Yahoo!地图)指示方向?
I mean, they probably have real-world data in some form, certainly including distances but also perhaps things like driving speeds, presence of sidewalks, train schedules, etc. But suppose the data were in a simpler format, say a very large directed graph with edge weights reflecting distances. I want to be able to quickly compute directions from one arbitrary point to another. Sometimes these points will be close together (within one city) while sometimes they will be far apart (cross-country).
Graph algorithms like Dijkstra's algorithm will not work because the graph is enormous. Luckily, heuristic algorithms like A* will probably work. However, our data is very structured, and perhaps some kind of tiered approach might work? (For example, store precomputed directions between certain "key" points far apart, as well as some local directions. Then directions for two far-away points will involve local directions to a key points, global directions to another key point, and then local directions again.)
实践中实际使用的算法是什么?
PS:这个问题的动机是发现在线地图方向的怪癖。与三角形不等式相反，有时谷歌Maps认为X-Z比使用中间点(如X-Y-Z)花费的时间更长，距离更远。但也许他们的行走方向也会优化另一个参数?
pp。这是对三角不等式的另一个违反，这表明(对我来说)他们使用了某种分层方法:X-Z vs X-Y-Z。前者似乎使用了著名的塞瓦斯托波尔大道(Boulevard de Sebastopol)，尽管它有点偏僻。
编辑:这两个例子似乎都不起作用了，但在最初的帖子发布时都起作用了。
作为一个在地图公司工作了18个月的人，其中包括研究路由算法……是的，Dijkstra的方法确实有效，只是做了一些修改:
Instead of doing Dijkstra's once from source to dest, you start at each end, and expand both sides until they meet in the middle. This eliminates roughly half the work (2*pi*(r/2)^2 vs pi*r^2).
To avoid exploring the back-alleys of every city between your source and destination, you can have several layers of map data: A 'highways' layer that contains only highways, a 'secondary' layer that contains only secondary streets, and so forth. Then, you explore only smaller sections of the more detailed layers, expanding as necessary. Obviously this description leaves out a lot of detail, but you get the idea.
通过沿着这些路线进行修改，您甚至可以在非常合理的时间范围内完成跨国家路由。
说到GraphHopper，
一个基于OpenStreetMap的快速开源路线规划器，我阅读了一些文献并实现了一些方法。最简单的解决方案是Dijkstra，一个简单的改进是双向Dijkstra，它大致只探索一半的节点。在双向Dijkstra模式下，穿越整个德国需要1秒(汽车模式)，在C模式中可能只需要0.5秒左右;)
我在这里用双向Dijkstra创建了一个真实路径搜索的动图。还有一些想法可以让Dijkstra更快，比如做A*，这是一个“面向目标的Dijkstra”。我还为它创建了一个gif动画。
但是怎样才能(快得多)呢?
问题是，对于路径搜索来说，必须探索位置之间的所有节点，这是非常昂贵的，因为在德国已经有数百万个节点了。但是Dijkstra等的另一个痛点是这样的搜索使用大量的RAM。
有启发式解决方案，也有精确解决方案，将图(路网)分层组织，两者都有优缺点，主要解决速度和RAM问题。我在这个回答中列出了其中的一些。
对于GraphHopper，我决定使用收缩层次结构，因为它相对“容易”实现，并且不需要花时间来准备图表。它仍然会导致非常快的响应时间，就像你可以在我们的在线实例GraphHopper Maps上测试一样。例如，从南非到中国东部，距离23000公里，汽车行驶时间近14天，在服务器上只需要0.1秒。
就静态道路网络的查询时间而言，目前最先进的技术是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标签算法为静态道路网络提供了最快的查询，但需要大量ram来运行(18 GiB)。
传输节点路由稍慢，不过它只需要大约2 GiB的内存，并且有更快的预处理时间。
收缩层次结构在快速预处理时间、低空间需求(0.4 GiB)和快速查询时间之间提供了一个很好的平衡。
没有一种算法是完全占主导地位的……
彼得·桑德斯的谷歌科技演讲可能会让你感兴趣
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
还有一篇微软写的关于CRP算法用法的博客文章…http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/
