地图中最短路径的搜索算法研究综述

地图中最短路径的搜索算法研究综述

ID:8806805

大小:58.00 KB

页数:5页

时间:2018-04-08

地图中最短路径的搜索算法研究综述_第1页
地图中最短路径的搜索算法研究综述_第2页
地图中最短路径的搜索算法研究综述_第3页
地图中最短路径的搜索算法研究综述_第4页
地图中最短路径的搜索算法研究综述_第5页
资源描述:

《地图中最短路径的搜索算法研究综述》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、地图中最短路径的搜索算法研究学生:李小坤导师:董峦摘要:目前为止,国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析,结合实际应用,从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A*算法的优缺点。关键词:最短路径算法;广度优先算法;深度优先算法;A*算法;Theshortestpathofmap'ssearchalgorithmAbstract:Sofar,alargenumberofdomesticandforeignexpertsandscholarsonthe"shortestpathproblem"in-depths

2、tudy.Inthispaper,throughtheoreticalanalysisandpracticalapplication,comprisewiththebreadth-firstsearchalgorithm(BFS),depth-firstsearchalgorithm(DFS)andtheA*algorithmsfromanyaspectsofsystematic.Keywords:shortestpathalgorithm;breadth-firstalgorithm;algorithm;A*algorithm;前言:最短路径问题是地理信息系统(GIS)网络

3、分析的重要内容之一,而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关,比如:网络路由选择,集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法,广度优先算法和A*算法,对一具体问题进行讨论和分析,比较三种算的的优缺点。在地图中最短路径的搜索算法研究中,每种算法的优劣的比较原则主要遵循以下三点:[1](1)算法的完全性:提出一个问题,该问题存在答案,该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。(2)算法的时间复杂性:提出一个问题,该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。(3)算法的

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

5、法。广度优先搜索算法伪代码如下:[2-3]BFS(v)//广度优先搜索G,从顶点v开始执行//所有已搜索的顶点i都标记为Visited(i)=1.//Visited的初始分量值全为0Visited(v)=1;Q=[];//将Q初始化为只含有一个元素v的队列whileQnotnulldou=DelHead(Q);for邻接于u的所有顶点wdoifVisited(w)=0thenAddQ(w,Q);//将w放于队列Q之尾Visited(w)=1;endifendforendwhileendBFS这里调用了两个函数:AddQ(w,Q)是将w放于队列Q之尾;DelHead(Q)是从队

6、列Q取第一个顶点,并将其从Q中删除。重复DelHead(Q)过程,直到队列Q空为止。完全性:广度优先搜索算法具有完全性。这意指无论图形的种类如何,只要目标存在,则BFS一定会找到。然而,若目标不存在,且图为无限大,则BFS将不收敛(不会结束)。时间复杂度:最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为,其中

7、V

8、是节点的数目,而

9、E

10、是图中边的数目。空间复杂度:因为所有节点都必须被储存,因此BFS的空间复杂度为,其中

11、V

12、是节点的数目,而

13、E

14、是图中边的数目。另一种说法称BFS的空间复杂度为O(B),其中B是最大分支系数,而M是树的最长路径长度。由于对

15、空间的大量需求,因此BFS并不适合解非常大的问题。[4-5]2、深度优先算法深度优先搜索算法(DepthFirstSearch)英文缩写为DFS,属于一种回溯算法,正如算法名称那样,深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。[6]其过程简要来说是沿着顶点的邻点一直搜索下去,直到当前被搜索的顶点不再有未被访问的邻点为止,此时,从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点,并以此顶点作为当前被搜索顶点。继续这样的过程,直至不能执行为止。深度优先搜索算法的伪代码如下:[7]DFS(v)//

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。