地图提供商(如谷歌或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),尽管它有点偏僻。

编辑:这两个例子似乎都不起作用了,但在最初的帖子发布时都起作用了。


当前回答

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

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

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

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

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

http://tom.mapsforge.org/

其他回答

我对此有了更多的想法:

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

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

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

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

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

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

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

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

http://tom.mapsforge.org/

地图从不考虑整个地图。 我猜是:- 1. 根据你的位置,它们加载一个地方和那个地方的地标。 2. 当你搜索目的地时,他们会加载地图的另一部分,然后用两个地方做一个图,然后应用最短路径算法。

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

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

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

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

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

就静态道路网络的查询时间而言,目前最先进的技术是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/