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

问题描述

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

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。这个问题的动机是寻找在在线地图方向怪癖。相反三角不等式，有时谷歌地图认为<一href="http://maps.google.com/maps?f=d&saddr=Place+Jacques+Bonsergent,+75010+Paris&daddr=Place+Louis+Lepine,+75004+Paris&hl=en&geo$c$c=&mra=ls&dirflg=w&sll=48.861295,2.35161&sspn=0.013778,0.029655&ie=UTF8&z=14">X-Z需要更长的时间和更远比使用的中间点作为<一个href="http://maps.google.com/maps?f=d&saddr=Place+Jacques+Bonsergent,+75010+Paris&daddr=Square+Emile+Chautemps,+75003+Paris+to%3aPlace+Louis+Lepine,+75004+Paris&hl=en&geo$c$c=&mra=ls&dirflg=w&sll=48.869359,2.357833&sspn=0.006888,0.014827&ie=UTF8&z=14">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。这里还有一个违反三角不等式的建议（对我来说），他们使用某种分级方法的：<一href="http://maps.google.com/maps?f=d&saddr=214,+boulevard+de+la+Villette,+75019+Paris&daddr=Passage+des+Patriarches,+75005+Paris&hl=en&geo$c$c=&sll=48.86278,2.35595&sspn=0.05511,0.118618&mra=cc&dirflg=w&ie=UTF8&z=13">X-Z与<一个href="http://maps.google.com/maps?f=d&saddr=214,+boulevard+de+la+Villette,+75019+Paris&daddr=Square+Emile+Chautemps,+75003+Paris+to%3aPassage+des+Patriarches,+75005+Paris&hl=en&geo$c$c=&mra=ls&dirflg=w&sll=48.86278,2.35595&sspn=0.05511,0.118618&ie=UTF8&ll=48.862682,2.357941&spn=0.05511,0.118618&z=13">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个月的映射公司，其中包括工作在路由算法的工作......是的，的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的一次dest的，你开始在每年年底，并扩大双方直到他们在中间相遇。这消除了大约一半的工作（2 * PI *（R / 2）^ 2 VS PI * R ^ 2）。
• 要避免探索背街巷源和目标之间的每个城市，你可以有地图数据的几层：A'高速公路'层只包含高速公路，只包含次级街道次要层，等等。然后，您探索更详细层只有小部分，根据需要扩大。显然，这说明漏掉了很多细节，但你的想法。

• 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屋！