当前位置:  开发笔记 > 编程语言 > 正文

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

如何解决《什么算法计算地图上从A点到B点的方向?》经验,为你挑选了9个好方法。

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

我的意思是,他们可能有某种形式的真实数据,当然包括距离,但也可能包括行驶速度,人行道的存在,火车时刻表等.但是假设数据格式较简单,比如一个非常大的有向图边缘权重反映距离.我希望能够快速计算从任意点到另一个点的方向.有时这些点将在一起(在一个城市内),而有时它们将相隔很远(越野).

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

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

PS.这个问题的动机是通过在线地图方向找到怪癖.与三角形不等式相反,有时谷歌地图认为XZ需要更长时间,并且比使用XYZ中的中间点更远.但也许他们的步行路线也会针对另一个参数进行优化?

PPS.这是对三角不等式的另一个违反,它暗示(对我来说)他们使用某种分层方法:XZ与XYZ.前者似乎使用着名的Boulevard de Sebastopol,尽管它稍微偏离了方向.

编辑:这些例子似乎都不再起作用,但两者都是在原始帖子时完成的.



1> Nick Johnson..:

作为在地图公司工作了18个月的人,其中包括研究路由算法...是的,Dijkstra确实有效,只做了几处修改:

你不是将Dijkstra的一次从源头转移到dest,而是从每一端开始,然后扩展两边直到他们在中间相遇.这消除了大约一半的工作(2*pi*(r/2)^ 2 vs pi*r ^ 2).

为了避免探索源和目的地之间的每个城市的后巷,您可以拥有多层地图数据:仅包含高速公路的"高速公路"图层,仅包含次要街道的"次要"图层,依此类推.然后,您只浏览更详细图层的较小部分,并根据需要进行扩展.显然这个描述遗漏了很多细节,但你明白了.

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


"它只能保证产生解决方案,不一定是最有效的解决方案"这是不真实的; 只要使用的启发式是可接受的,A*算法就会产生成本最低的路径.可接受意味着成本永远不会被高估,但可能被低估(但估算不佳会使算法变慢).使用来自预处理的数据可能有助于制定更好的可接受启发式算法,从而使A*工作更快.
在现实世界中为此工作过的人,太棒了!您是否知道可以预先计算多少,就像在另一条评论中提到的关于Google的文章一样?
A*,在最坏的情况下(一种说明所有路径都相同的启发式算法),与Djikstra完全相同.
我们没有对这种性质进行任何预处理,但它看起来似乎是一个有趣的优化.
实际上,经过进一步考虑,你是完全正确的.您可以通过简单地将目标节点和目标之间的大圆距离添加到要评估的边的成本来增强现有算法以利用此算法.我实际上不确定我们的算法是否做到了 - 但这是一个非常合理的优化.
我不知道A*这样的估计器如何比dijkstra更有效率.如果找到成本为n的路径,为了确定没有更便宜的路径,它必须探索所有成本路径A*可能更有效率,但它只能保证产生_a_解决方案,不一定是效率最高的解决方案.对于用户而言,这可能是一个问题,在这种情况下,效率低下的解决方案会转化为浪费时间或金钱,或者用户认为软件很糟糕.尽管如此,你可能会建立一些关于什么时候放弃A*为Dijkstra的启发式方法.
@ivan_petrushenko半径为r/2的两个圆的面积是半径为r的一次圆的面积的一半.

2> SebastianK..:

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

Arachnid描述了基于分层信息的双向搜索和边缘修剪的使用.这些加速技术运行良好,但最新的算法无论如何都优于这些技术.利用当前的算法,可以在大陆公路网上以相当短的时间计算最短路径,而不是一毫秒.Dijkstra的未修改算法的快速实现需要大约10秒.

工程快速路线规划算法这篇文章概述了该领域的研究进展.有关详细信息,请参阅该论文的参考资料.

最快的已知算法不使用关于数据中道路的分层状态的信息,即,如果它是高速公路或本地道路.相反,他们在预处理步骤中计算自己的层次结构,该层次结构经过优化以加速路径规划.然后可以使用该预计算来修剪搜索:在Dijkstra算法期间,不需要考虑远离起点和目的地的慢速道路.优点是非常好的性能和结果的正确性保证.

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

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



3> stevemegson..:

只是解决三角不等式违规问题,希望他们优化的额外因素是常识.您不一定需要最短或最快的路线,因为它可能导致混乱 和 破坏.如果您希望您的路线更喜欢卡车友好的主要路线,并且可以应对每个坐下导航的驾驶员发送它们,您很快就会丢弃三角形不等式[1].

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

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



4> eikes..:

这是世界上最快的路由算法,比较并证明了正确性:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

这是关于这个主题的谷歌技术讲座:

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

这是schultes讨论的高速公路 - 层次结构算法的实现(目前仅在柏林,我正在编写接口,并且正在开发移动版本):

http://tom.mapsforge.org/



5> 小智..:

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

然而,我确实为一家能源公司设计了一个定制的供应链优化系统,其中包括为其车队提供的调度和路由应用.但是,我们的路线标准远比建筑或交通减速或车道关闭更具商业性.

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

您可以使用Google ACO或TSP来查找有关此技术的更多信息.我没有使用任何开源AI工具,所以不能建议一个(虽然我听说SWARM非常全面).


路由!= tsp.在tsp你知道所有的距离,你优化停止顺序 - 这不是一个点对点的算法.

6> Konrad Rudol..:

像Dijkstra算法这样的图算法不起作用,因为图形是巨大的.

这个论点不一定成立,因为Dijkstra通常不会查看完整的图,而只是一个非常小的子集(图表越好互连,这个子集就越小).

对于表现良好的图表,Dijkstra实际上可能表现得相当好.另一方面,通过仔细的参数化,A*总能表现得更好或更好.您是否已经尝试过如何对数据执行操作?

也就是说,我也很想知道其他人的经历.当然,谷歌地图搜索等突出的例子特别有趣.我可以想象像定向最近邻居启发式的东西.


假设您正在尝试查找从A点到B点的方向,其最佳距离为d.Dijkstra的算法至少会检查距离A最远距离的所有点.如果A是旧金山而B是波士顿,这意味着它会检查美国的大部分地区.N'est-ce pas?
是的.我想要的是,A*可以代替使用,它总能找到最佳解决方案(即使它使用启发式)!
好吧,重点是A**使用*启发式(而不是*是*one)来确定下一步.这一个决定确实可能不是最理想的.但它只会影响运行时,而不会影响结果,因为它只能确定它比Dijstra更好的效果.

7> Barnaby Huss..:

就静态道路网络的查询时间而言,现有技术是Abraham等人提出的Hub标记算法.http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20.最近发布了该领域的最佳书面调查,作为Microsoft技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf.

简短的版本是......

Hub标记算法为静态道路网络提供最快的查询,但需要运行大量的ram(18 GiB).

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

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

没有一种算法完全占主导地位......

Peter Sanders的Google技术讲座可能会引起人们的兴趣

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

这也是Andrew Goldberg的演讲

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

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

此外,还有一篇由Microsoft撰写的关于CRP算法使用的易于访问的博客文章... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/



8> dennisjtaylo..:

我有点不高兴看不到这里提到的Floyd Warshall的算法.这个算法与Dijkstra非常相似.它还有一个非常好的功能,它允许您计算,只要您想继续允许更多的中间顶点.因此,它会自然地找到使用州际公路或高速公路的路线.



9> Pål GD..:

我已经做了很多次,实际上,尝试了几种不同的方法.根据地图的大小(地理位置),您可能需要考虑使用hasrsine函数作为启发式算法.

我所做的最好的解决方案是使用具有直线距离的A*作为启发式函数.但是,你需要为地图上的每个点(交叉点或顶点)设置某种坐标.您还可以尝试不同的启发函数权重,即

f(n) = k*h(n) + g(n)

其中k是某个大于0的常数.

推荐阅读
ar_wen2402851455
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有