如何地图提供商（如谷歌或雅虎地图）建议的方向？

How do map providers (such as Google or Yahoo! Maps) suggest directions?

我的意思是，他们可能有某种形式的真实世界的数据，当然包括距离，也或许是像驾驶速度，人行道presence，列车时刻表等，但假设数据是在一个简单的格式，说一个非常大的向图，边权反映的距离。我希望能够快速地从一个任意点计算指示到另一个。有时，这些点将会接近（在一个城市），而有时他们会相距甚远（越野）。

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).

图算法像Dijkstra算法是行不通的，因为该图是巨大的。幸运的是，启发式算法，如A *可能会工作。然而，我们的数据是很有计划的，也许某种分层方法可能会奏效？ （例如，存储precomputed某些关键点相距甚远，以及一些当地的方向之间的方向，然后方向有两个遥远的积分将涉及到当地的方向的一个关键点，整体方向到另一个关键点，然后再次局部方向。）

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.)

在实践中实际使用什么算法？

What algorithms are actually used in practice?

PS。这个问题的动机是寻找在在线地图方向怪癖。相反三角不等式，有时谷歌地图认为X-Z需要更长的时间和更远比使用的中间点作为X-Y-Z.但也许他们的步行路线优化另一个参数，过？

PS. This question was motivated by finding quirks in online mapping directions. Contrary to the triangle inequality, sometimes Google Maps thinks that X-Z takes longer and is farther than using an intermediate point as in X-Y-Z. But maybe their walking directions optimize for another parameter, too?

PPS。这里还有一个违反三角不等式的建议（对我来说），他们使用某种分级方法的：X-Z与X-Y-Z.前者似乎用突出的塞瓦斯托波尔大道即使它稍稍闪开。

PPS. Here's another violation of the triangle inequality that suggests (to me) that they use some kind of tiered approach: X-Z versus X-Y-Z. The former seems to use prominent Boulevard de Sebastopol even though it's slightly out of the way.

修改：这些都不例子似乎工作了，但都没有在原岗位的时间

Edit: Neither of these examples seem to work anymore, but both did at the time of the original post.

推荐答案

在谈到谁的人花了18个月的映射公司，其中包括工作在路由算法的工作......是的，的