dijkstra algorithm




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

地图提供商(如Google或Yahoo! Maps)如何提供方向建议?

我的意思是,他们可能以某种形式存在真实世界的数据,当然包括距离,但也可能包括驾驶速度,人行道,列车时刻表等等。但假设数据是一种更简单的格式,例如一个非常大的有向图边缘权重反映距离。 我希望能够快速计算从一个任意点到另一个点的方向。 有时候这些点会在一起(在一个城市内)接近,而有时它们会相距甚远(跨国)。

像Dijkstra算法这样的图形算法将不起作用,因为图形非常庞大。 幸运的是,像A *这样的启发式算法可能会起作用。 但是,我们的数据是非常有条理的,也许某种分层方法可能有用? (例如,存储相距很远的某些“关键”点之间的预先计算的方向以及一些局部方向,然后两个远处点的方向将涉及到关键点的局部方向,另一个关键点的全局方向,然后是局部再次指示。)

在实践中实际使用哪些算法?

PS。 这个问题的动机是发现在线测绘方向的怪癖。 与三角形不平等相反,有时谷歌地图认为X-Z需要更长的时间,并且比使用X-Y-Z的中间点更远。 但是,也许他们的步行方向也可以优化另一个参数?

PPS。 这是另一种违反三角形不平等的表现(对我来说)他们使用某种分层方法: X-ZX-Y-Z 。 前者似乎使用着名的塞瓦斯托波尔大道,虽然它略微偏离了道路。

编辑 :这些例子都没有工作了,但都在原来的帖子时。


像Dijkstra算法这样的图形算法将不起作用,因为图形非常庞大。

这个论点并不一定成立,因为Dijkstra通常不会看完整的图,而只是一个非常小的子集(图中相互关联越好,这个子集越小)。

对于表现良好的图表,Dijkstra可能表现得相当不错。 另一方面,如果仔细参数化,A *将始终表现良好或更好。 您是否已经尝试过如何对您的数据执行操作?

也就是说,我也很想听听别人的经历。 当然,Google Map搜索等突出的例子特别有趣。 我可以想象像定向最近邻的启发式。



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


只要解决三角形不平等违规问题,希望他们优化的额外因素是常识。 你不一定需要最短或最快的路线,因为它可能导致chaos and destruction 。 如果你想让自己的路线更喜欢卡车友好的主要路线,并且可以应付让每个坐着驾驶员的司机下车,那么你很快就会丢弃三角形的不平等[1]。

如果Y是X和Z之间狭窄的住宅街道,如果用户明确要求XYZ,则可能只想通过Y使用快捷方式。 如果他们要求XZ,他们应该坚持主要道路,即使它稍远一点,需要更长的时间。 这与Braess的悖论相似 - 如果每个人都试图采用最短,最快的路线,则由此产生的拥堵意味着它不再是任何人的最快路线。 从这里我们偏离图论到博弈论。

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


在静态道路网络的查询时间方面,本领域的当前状态是由Abraham等人提出的Hub标记算法。 http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 。 最近作为微软技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf发布了一篇关于该领域的优秀书面调查。

简短的版本是...

Hub标记算法为静态路网提供了最快的查询,但需要大量RAM(18 GiB)。

Transit节点路由稍慢,但它只需要大约2 GiB的内存并且预处理时间更快。

收缩层次结构在快速预处理时间,低空间要求(0.4 GiB)和快速查询时间之间提供了良好的折衷。

没有一个算法完全支配...

彼得桑德斯的Google技术讲座可能会引起人们的兴趣

https://www.youtube.com/watch?v=-0ErpE8tQbw

此外,安德鲁戈德堡的这次演讲

https://www.youtube.com/watch?v=WPrkc78XLhw

KIT的Peter Sanders研究小组网站提供了收缩层级的开源实现。 http://algo2.iti.kit.edu/english/routeplanning.php

另外还有一个由微软编写的关于那里使用CRP算法的博客文章。http: http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/


地图从不考虑整个地图。 我的猜测是: - 1.根据您的位置,他们在该地点加载一个地点和地标。 2.当你搜索目的地时,这是当他们加载地图的另一部分,并从两个地方制作图表,然后应用最短路径算法。

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


我之前没有在Google或微软或雅虎地图上工作,所以我不能告诉你他们是如何工作的。

然而,我的确为能源公司构建了定制供应链优化系统,其中包括为其卡车车队安排和路线应用。 然而,我们的路线标准要比建筑或交通减速或车道封闭的地方更具针对性。

我们采用了一种名为ACO(蚁群优化)的技术来安排和路由卡车。 这项技术是一种应用于旅行商问题解决路由问题的AI技术。 ACO的诀窍是根据路由的已知事实构建错误计算,以便图解模型知道何时退出(错误何时足够小)。

你可以谷歌ACO或TSP找到更多关于这种技术。 但是我没有使用任何开源AI工具,所以不能提出一个(尽管我听说SWARM非常全面)。


我对使用的启发式技术非常好奇,一段时间后,我们从圣罗莎附近的相同起始位置获得路线,到达优胜美地国家公园的两个不同的露营地。 这些不同的目的地产生了完全不同的路线(通过I-580或CA-12),尽管两条路线在最后100英里(沿着CA-120)汇合,然后在最后再分散几英里。 这是相当可重复的。 两条路线相隔达50英里,距离约100英里,但距离/时间彼此非常接近,就像您期望的那样。

唉,我不能重现 - 算法必须改变。 但它让我对算法感到好奇。 我可以推测的是,有一些定向修剪恰好对从远处看到的目的地之间的微小角度差异非常敏感,或者由最终目的地的选择选择了不同的预计算段。


我已经在路由上工作了几年,最近一连串的活动都是由我的客户的需求引起的,我发现A *很容易就足够快; 实际上不需要寻找优化或更复杂的算法。 在巨大的图表上路由不是问题。

但速度取决于整个路由网络,我的意思是分别代表路由段和节点的弧和节点的有向图。 主要的时间开销是创建这个网络所需的时间。 基于运行Windows的普通笔记本电脑的一些粗略数字,以及在整个西班牙的路由:创建网络所用的时间:10-15秒; 计算路线所需的时间:太短而无法衡量。

另一个重要的事情是能够重新使用网络进行尽可能多的路由计算。 如果您的算法以某种方式标记了节点,以记录最佳路径(总成本到当前节点以及最佳弧段) - 就像在A *中一样 - 您必须重置或清除这些旧信息。 而不是通过成千上万的节点,使用世代号码系统更容易。 用每个节点的数据代号标记每个节点; 计算新路线时增加世代号; 具有旧代号的任何节点都是陈旧的,并且其信息可以被忽略。


我有点惊讶没有看到这里提到的Floyd Warshall的算法 。 这个算法的工作非常像Dijkstra的。 它还有一个非常好的功能,只要你想继续允许更多的中间顶点,它可以让你计算。 所以它很自然地会找到使用州际公路或高速公路的路线。


说到基于OpenStreetMap的快速开源路由规划器GraphHopper ,我已经阅读了一些文献并实现了一些方法。 最简单的解决方案是Dijkstra,简单的改进是双向Dijkstra,它大致只探索一半的节点。 对于迪克斯特拉而言,通过整个德国的路线已经是1秒(对于汽车模式),在C中它可能只有0.5秒左右;)

我在这里创建了一个带有双向Dijkstra的真实路径搜索的动画gif。 还有一些更多的想法可以让Dijkstra更快地像做一个“面向目标的Dijkstra”的A *。 我也为它创建了一个gif-animation

但如何更快地做到这一点?

问题在于,对于路径搜索,必须探索位置之间的所有节点,并且这在德国已经有数百万个这样的成本。 但是Dijkstra等人的另一个痛点是这种搜索使用了大量的RAM。

有启发式的解决方案,但也有层次结构图(道路网络)组织的精确解决方案,都有优缺点,主要解决速度和内存问题。 我在这个答案中列出了他们中的一些。

对于GraphHopper,我决定使用“ 收缩层次”,因为它实现起来相对“容易”,并且不需要花费时间准备图表。 它仍然会产生非常快速的响应时间,就像您可以在我们的在线实例GraphHopper Maps中测试一样。 例如从南非到华东 ,导致23000公里的距离和接近14天的驾车时间,并且在服务器上仅花费约0.1秒。


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

Arachnid描述了基于分层信息的双向搜索和边缘修剪的用法。 这些加速技术工作得很好,但最新的算法通过一切手段胜过这些技术。 使用当前的算法,可以在大陆路网上以比毫秒少得多的时间来计算最短路径。 未经修改的Dijkstra算法的快速实现需要大约10秒

文章工程快速路线规划算法给出了该领域研究进展的概述。 有关更多信息,请参阅该文件的参考资料。

已知最快的算法不使用关于数据中道路的分层状态的信息,即,如果是公路或当地道路。 相反,他们在预处理步骤中计算自己的层次结构,以便加速路线规划。 这个预计算可以用来修剪搜索:远离开始和目的地,在Dijkstra算法期间,不需要考虑慢速道路。 好处是非常好的性能和结果的正确性保证。

第一种优化的路线规划算法仅处理静态道路网络,这意味着图中的边缘具有固定的成本值。 实际情况并非如此,因为我们想要考虑交通堵塞或依赖车辆限制等动态信息。 最新的算法也可以处理这些问题,但仍然存在需要解决的问题和正在进行的研究。

如果您需要最短路径距离来计算TSP的解决方案,那么您可能对包含源和目标之间所有距离的矩阵感兴趣。 为此,您可以考虑使用公路层次结构计算多对多最短路径 。 请注意,过去两年新方法改善了这一点。







mapping