什么算法计算地图上从 A 点到 B 点的方向? [英] What algorithms compute directions from point A to point B on a map?

问题描述

地图提供商(例如 Google 或 Yahoo! Maps)如何建议路线?

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

我的意思是，他们可能拥有某种形式的真实世界数据，当然包括距离，但也可能包括行驶速度、人行道的存在、火车时刻表等.但假设数据采用更简单的格式，比如说非常具有反映距离的边权重的大型有向图.我希望能够快速计算从任意点到另一点的方向.有时这些点会靠近(在一个城市内)，有时它们会相距很远(跨国).

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* 这样的启发式算法可能会奏效.但是，我们的数据非常结构化，也许某种分层方法可能有效?(例如，在某些相距较远的关键"点之间存储预先计算的方向，以及一些局部方向.那么两个远点的方向将涉及到一个关键点的局部方向，到另一个关键点的全局方向，然后是局部再次指示.)

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?

附注.这个问题的动机是在在线地图方向上寻找怪癖.与三角不等式相反，有时谷歌地图认为 XZ 比在 XYZ但也许他们的步行路线也针对另一个参数进行了优化?

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.这是对三角不等式的另一个违反，这表明(对我而言)他们使用某种分层方法:XZ 与 XYZ.前者似乎使用了著名的塞瓦斯托波尔大道，尽管它有点偏僻.

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 个月的人来说，其中包括研究路由算法......是的，Dijkstra's 确实有效，但有一些修改:

Speaking as someone who spent 18 months working at a mapping company, which included working on the routing algorithm... yes, Dijkstra's does work, with a couple of modifications:

• 不是从源到目标一次Dijkstra's，而是从每一端开始，并展开双方直到他们在中间相遇.这消除了大约一半的工作(2*pi*(r/2)^2 vs pi*r^2).
• 为避免探索源和目的地之间每个城市的小巷，您可以拥有多个地图数据图层:仅包含高速公路的高速公路"图层，仅包含次要街道的二级"图层，以及等等.然后，您仅探索更详细图层的较小部分，并根据需要进行扩展.显然，这个描述遗漏了很多细节，但你明白了.

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

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

With modifications along those lines, you can do even cross-country routing in a very reasonable timeframe.

这篇关于什么算法计算地图上从 A 点到 B 点的方向?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！