设为主页 | | 关于我们 | 会员专区
欢迎访问我们的网站!
| | | | |
当前位置: 主页 > 1961 >

百度地图的路径搜索算法

时间:2019-09-17 06:29来源:未知 作者:admin 点击:
百度地图能在全国范围内以极短的时间搜索出任意两点的行程路线,包括时间、路程等可选方案,还有备选方案,这涉及到K条最短路的算法,请教一下它是用什么算法,采取什么样的策略实现的... 百度地图能在全国范围内以极短的时间搜索出任意两点的行程路线,包括

  百度地图能在全国范围内以极短的时间搜索出任意两点的行程路线,包括时间、路程等可选方案,还有备选方案,这涉及到K条最短路的算法,请教一下它是用什么算法,采取什么样的策略实现的...

  百度地图能在全国范围内以极短的时间搜索出任意两点的行程路线,包括时间、路程等可选方案,还有备选方案,这涉及到K条最短路的算法,请教一下它是用什么算法,采取什么样的策略实现的?

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部这个还是要问程序猿,现在比较流行A*算法,至于百度是否开发出了新的算法不得而知,毕竟没有完全相同的程序。

  摘要:目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用,从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点。

  最短路径问题是地理信息系统(GIS)网络分析的重要内容之一,而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关, 比如: 网络路由选择, 集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法,广度优先算法和A*算法,对一具体问题进行讨论和分析,股东会]鲁商置业(600223)2009年度股东,比较三种算的的优缺点。

  在地图中最短路径的搜索算法研究中,每种算法的优劣的比较原则主要遵循以下三点:[1]

  (1)算法的完全性:提出一个问题,该问题存在答案,该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。

  (2)算法的时间复杂性: 提出一个问题,该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。

  (3)算法的空间复杂性:算法在执行搜索问题答案的同时,需要多少存储空间。算法占用资源越少,算法的性能越好。

  广度优先算法(Breadth-First-Search),又称作宽度优先搜索,或横向优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。

  这里调用了两个函数:AddQ(w,Q)是将w放于队列Q之尾;DelHead(Q)是从队列Q取第一个顶点,并将其从Q中删除。重复DelHead(Q)过程,直到队列Q空为止。

  完全性:广度优先搜索算法具有完全性。这意指无论图形的种类如何,只要目标存在,则BFS一定会找到。123彩图一100历史图库大气扩散条件略偏,然而,若目标不存在,且图为无限大,则BFS将不收敛(不会结束)。

  时间复杂度:最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为,其中V是节点的数目,而 E 是图中边的数目。

  空间复杂度:因为所有节点都必须被储存,因此BFS的空间复杂度为,其中V是节点的数目,而E是图中边的数目。另一种说法称BFS的空间复杂度为O(B),其中B是最大分支系数,而M是树的最长路径长度。由于对空间的大量需求,因此BFS并不适合解非常大的问题。[4-5]

  深度优先搜索算法(Depth First Search)英文缩写为DFS,属于一种回溯算法,正如算法名称那样,深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。[6]其过程简要来说是沿着顶点的邻点一直搜索下去,直到当前被搜索的顶点不再有未被访问的邻点为止,此时,从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点,并以此顶点作为当前被搜索顶点。继续这样的过程,直至不能执行为止。

  作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大。但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法,它的效率比较低,在数据规模变大时,这种算法就显得力不从心了。[8]关于深度优先搜索的效率问题,有多种解决方法。最具有通用性的是剪枝,也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。

  BFS:对于解决最短或最少问题特别有效,而且寻找深度小,但缺点是内存耗费量大(需要开大量的数组单元用来存储状态)。

  DFS:对于解决遍历和求所有问题有效,对于问题搜索深度小的时候处理速度迅速,然而在深度很大的情况下效率不高。

  创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。

  按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小,从最小路径的节点向下进行。

  保存路径,即 从终点开始,每个节点沿着父节点移动直至起点,这就是你的路径;

  DFS和BFS在展开子结点时均属于盲目型搜索,也就是说,它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中,均需要试探完整个解集空间, 显然,只能适用于问题规模不大的搜索问题中。而A*算法与DFS和BFS这类盲目型搜索最大的不同,就在于当前搜索结点往下选择下一步结点时,可以通过一个启发函数来进行选择,选择代价最少的结点作为下一步搜索结点而跳转其上。[11]A *算法就是利用对问题的了解和对问题求解过程的了解, 寻求某种有利于问题求解的启发信息, 从而利用这些启发信息去搜索最优路径.它不用遍历整个地图, 而是每一步搜索都根据启发函数朝着某个方向搜索.当地图很大很复杂时, 它的计算复杂度大大优于D ijks tr a算法, 是一种搜索速度非常快、效率非常高的算法.但是, 相应的A*算法也有它的缺点.启发性信息是人为加入的, 有很大的主观性, 直接取决于操作者的经验, 对于不同的情形要用不同的启发信息和启发函数, 且他们的选取难度比较大,很大程度上找不到最优路径。

  本文描述了最短路径算法的一些步骤,总结了每个算法的一些优缺点,以及算法之间的一些关系。对于BFS还是DFS,它们虽然好用,但由于时间和空间的局限性,以至于它们只能解决规模不大的问题,而最短或最少问题应该选用BFS,遍历和求所有问题时候则应该选用DFS。至于A*算法,它是一种启发式搜索算法,也是一种最好优先的算法,它适合于小规模、大规模以及超大规模的问题,但启发式搜索算法具有很大的主观性,它的优劣取决于编程者的经验,以及选用的启发式函数,所以用A*算法编写一个优秀的程序,难度相应是比较大的。每种算法都有自己的优缺点,对于不同的问题选择合理的算法,才是最好的方法。

  [1]陈圣群,滕忠坚,洪亲,陈清华.四种最短路径算法实例分析[J].电脑知识与技术(学术交流),2007(16):1030-1032

  [2]刘树林,尹玉妹.图的最短路径算法及其在网络中的应用[J].软件导刊,2011(07):51-53

  [3]刘文海,徐荣聪.几种最短路径的算法及比较[J].福建电脑,2008(02):9-12

  [4]邓春燕.两种最短路径算法的比较[J].电脑知识与技术,2008(12):511-513

  [5]王苏男,宋伟,姜文生.最短路径算法的比较[J].系统工程与电子技术,1994(05):43-49

  [6]徐凤生,李天志.所有最短路径的求解算法[J].计算机工程与科学,2006(12):83-84

  [8]徐凤生.求最短路径的新算法[J].计算机工程与科学,2006(02).

  [11] 杨长保,王开义,马生忠.一种最短路径分析优化算法的实现[J]. 吉林大学学报(信息科学版),2002(02):70-74

(责任编辑:admin)
相关内容:
中国移动新上线G信号覆盖查询 淘宝造物节携手四年合作伙伴VP 中国航司在海外数字营销中如何 怎样在地图上注册我的位置 从官方公告到优惠活动百度地图
机场巴士 | 世界天气 | 外汇牌币 | 世界时间 | 取票与付款方式 | 投诉与建议 | 联系我们 | 国际机票

Copyright © 2008 elicn.com  Inc. All rights reserved. 北京易联东方国际机票网
电话:4007-100-800 传真:65305717 地址:北京市东城区东直门南大街9号华普花园B座1206室 邮政编码:100007

 
京ICP备09065193号 经营性网站备案信息

京ICP备案号:78945612 开发维护:奇迹网络