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

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


当前回答

只是解决三角形不等式的违反,希望他们优化的额外因素是常识。你不一定想要最短或最快的路线,因为这可能会导致混乱和破坏。如果你想让自己的路线更适合卡车行驶,并且能够应对每个卫星导航跟踪司机都沿着这些路线行驶的情况,那么你很快就可以放弃三角形不等式[1]。

如果Y是X和Z之间的一条狭窄的住宅街道,那么您可能只想在用户明确要求X-Y-Z时使用通过Y的快捷方式。如果他们要求X-Z,他们应该坚持走主干道,即使它有点远,需要更长的时间。这类似于Braess悖论——如果每个人都试图选择最短、最快的路线,那么随之而来的拥堵意味着这条路线不再是任何人最快的路线。从这里开始,我们将从图论转向博弈论。

事实上,当你允许单向道路并失去对称性要求时,任何产生的距离将是数学意义上的距离函数的希望都将破灭。失去三角不等式也只是在伤口上撒盐。

其他回答

这纯粹是我的猜测,但我认为他们可能会使用覆盖有向图的影响图数据结构,以缩小搜索域。这将允许搜索算法在所需行程较长时将路径导向主要路线。

鉴于这是一个谷歌应用程序,我们也可以合理地假设,许多神奇的功能都是通过大量缓存完成的。如果缓存前5%最常见的谷歌地图路由请求,我不会感到惊讶(20%?50%?)的请求需要通过简单的查询来回答。

只是解决三角形不等式的违反,希望他们优化的额外因素是常识。你不一定想要最短或最快的路线,因为这可能会导致混乱和破坏。如果你想让自己的路线更适合卡车行驶,并且能够应对每个卫星导航跟踪司机都沿着这些路线行驶的情况,那么你很快就可以放弃三角形不等式[1]。

如果Y是X和Z之间的一条狭窄的住宅街道,那么您可能只想在用户明确要求X-Y-Z时使用通过Y的快捷方式。如果他们要求X-Z,他们应该坚持走主干道,即使它有点远,需要更长的时间。这类似于Braess悖论——如果每个人都试图选择最短、最快的路线,那么随之而来的拥堵意味着这条路线不再是任何人最快的路线。从这里开始,我们将从图论转向博弈论。

事实上,当你允许单向道路并失去对称性要求时,任何产生的距离将是数学意义上的距离函数的希望都将破灭。失去三角不等式也只是在伤口上撒盐。

这个问题在过去几年中一直是一个活跃的研究领域。主要思想是对图进行一次预处理,以加快所有后续查询的速度。有了这些附加信息,行程可以很快计算出来。尽管如此,Dijkstra算法仍然是所有优化的基础。

Arachnid描述了双向搜索和基于层次信息的边缘修剪的用法。这些加速技术工作得很好,但最新的算法在任何方面都优于这些技术。使用目前的算法,在大陆公路网上计算最短路径的时间可大大少于1毫秒。快速实现未修改的Dijkstra算法大约需要10秒。

工程快速路线规划算法概述了该领域的研究进展。有关进一步信息,请参阅那篇论文的参考文献。

已知最快的算法不使用数据中关于道路层次状态的信息,即它是高速公路还是本地道路。相反,他们在预处理步骤中计算自己的层次结构,优化以加快路线规划。这种预计算可以用来精简搜索:在Dijkstra算法中,远离起点和目的地的缓慢道路不需要考虑。好处是非常好的性能和结果的正确性保证。

第一个优化的路线规划算法只处理静态道路网络,这意味着图中的边缘具有固定的成本值。这在实践中是不正确的,因为我们想要考虑交通堵塞或车辆相关限制等动态信息。最新的算法也可以处理这些问题,但仍有问题需要解决,研究还在继续。

如果您需要最短路径距离来计算TSP的解,那么您可能对包含源和目的地之间所有距离的矩阵感兴趣。为此,您可以考虑使用高速公路层次结构计算多对多最短路径。请注意,在过去的两年里,这已经通过更新的方法得到了改进。

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.

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

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

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