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

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

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

当前回答

I was very curious about the heuristics used, when a while back we got routes from the same starting location near Santa Rosa, to two different campgrounds in Yosemite National Park. These different destinations produced quite different routes (via I-580 or CA-12) despite the fact that both routes converged for the last 100 miles (along CA-120) before diverging again by a few miles at the end. This was quite repeatable. The two routes were up to 50 miles apart for around 100 miles, but the distances/times were pretty close to each other as you would expect.

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

2011-01-08 03:52:10

其他回答

作为一个在地图公司工作了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.

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

2009-01-11 12:41:34

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

2017-04-20 06:39:47

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

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

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

2009-01-10 01:53:41

2011-01-08 03:52:10

我对此有了更多的想法:

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

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