当前位置:首页>> 电子毕业设计 >>


基于导航最优路径算法的设计与实现.rar

收藏

资源目录
    文档预览:
    编号:20181007103100660    类型:共享资源    大小:62.94MB    格式:RAR    上传时间:2018-10-07
    尺寸:148x200像素    分辨率:72dpi   颜色:RGB    工具:   
    65
    金币
    关 键 词:
    基于 导航 最优 路径 算法 设计 实现
    资源描述:
    南昌航空大学软件学院东软班 摘 要i基于导航最优路径算法的设计与实现学生姓名:廖黄山 班级:102042 班指导老师:刘丹关键词:导航 最优路径 算法 a* dijistra Floyd摘要:自 20 世纪后期以来,随着全球经济的深入发展,世界各国城市(尤其是大城市)的人口和车辆持续增长,由于交通拥挤而造成的损失随之逐年增加。因而各国竞相投资修建交通设施,试图解决这一问题。但是车辆的增长速度远远高于道路和其他交通设施的增长速度,由此带来的有目共睹的事实是道路交通系统的复杂性和拥挤度的与日俱增。近年来人们已经逐渐认识到单纯依靠增加道路基础设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设施,才是合理可行的方法。由此出现了建设智能交通系统(Intelligent Transportation System, ITS)的热潮。事实上,建立现代化的交通系统,已经成为国家现代化的重要标志之一。与此相关的一系列方法与技术也成为当今计算机科学、地理信息科学等相关学科中的研究重点和热点。车载导航系统的研制开发可以划分为相互关联的技术模块,其中的路径规划是其他功能模块运行的基础,包含了车载导航系统中的很多关键技术。由于导航系统对道路网络建模、实时路径计算等方面有着特别的要求,在学术、技术上还存在着许多没有完全解决的问题。本课题就是重点研究了导航系统的最短路径问题。望能通过几种最短路径算法(a*/dijistra/floyd)的设计与实现,来深入探讨最优路径搜索的问题。Abstract: Since the late 20th century, with the further development of the global economy, world cities ( especially in large cities ) and vehicle population continues to grow , losses due to congestion caused by increased year by year. Thus countries compete investment in the construction of transport facilities , trying to solve this problem. However, the growth rate is much higher than the growth rate of the vehicle roads and other transportation facilities , and the resulting obvious fact is that the increasing complexity of the road transport system and crowding . In recent years, people have come to realize that relying solely on the increase in road infrastructure can not solve major problems with the rapid growth 南昌航空大学软件学院东软班 摘 要iiof vehicle traffic facilities lag between radically. Only in the secondary computer, information and communications tech means of the full use of the existing road infrastructure , is reasonable and feasible approach. Hence there are building intelligent transportation systems craze. In fact , the establishment of a modern transportation system , has become an important symbol of national modernization. A series of methods and techniques associated with this has become today's computer science, geographic information science and related disciplines in the research priorities and focus. Research and development of car navigation systems can be divided into technical interrelated modules which path planning is the basis of other modules running , the vehicle navigation system includes many key technologies. Since the terms of the road network on the navigation system modeling , real-time route calculation has special requirements, academic, technically there are still many not completely solve the problem. This topic is focused on the shortest path problem navigation system. Hope through the design and implementation of several shortest path algorithm to explore in depth the problem of searching the optimal path .南昌航空大学软件学院东软班 摘 要iii1.研究的背景与意义:自 20 世纪后期以来,随着全球经济的深入发展,世界各国城市(尤其是大城市)的人口和车辆持续增长,由于交通拥挤而造成的损失随之逐年增加。因而各国竞相投资修建交通设施,试图解决这一问题。但是车辆的增长速度远远高于道路和其他交通设施的增长速度,由此带来的有目共睹的事实是道路交通系统的复杂性和拥挤度的与日俱增。近年来人们已经逐渐认识到单纯依靠增加道路基础设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设施,才是合理可行的方法。由此出现了建设智能交通系统(Intelligent Transportation System, ITS)的热潮。事实上,建立现代化的交通系统,已经成为国家现代化的重要标志之一。与此相关的一系列方法与技术也成为当今计算机科学、地理信息科学等相关学科中的研究重点和热点。车载导航系统的研制开发可以划分为相互关联的技术模块,其中的路径规划是其他功能模块运行的基础,包含了车载导航系统中的很多关键技术。由于导航系统对道路网络建模、实时路径计算等方面有着特别的要求,在学术、技术上还存在着许多没有完全解决的问题。本课题就是重点研究了导航系统的最短路径问题。望能通过几种最短路径算法的设计与实现,来深入探讨最优路径搜索的问题。2.系统的研究现状在国外,各种导航系统对最短路径算法的应用比较发达。最短路径问题在交通网络结构的分析,交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择,通讯线路的建造与维护,运输货流的最小成本分析,城公共交通网络的规划等,都有直接的应用。在很多目标信息引导系统的设计中.需要获得最优化路径引导信息。例如,在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统,需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息;而当这些场合发生盗窃、抢劫等突发犯罪事件时,安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息.则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时,将图论中 Dijkstra 算法应用于目标信息引导系统的设计中,通过 Dijkstra 算法,首先计算出任一指定位置点距各疏导出口的最短路径树,进而通过编制辅助方向指示箭头程序,动态地将火灾事故现场救生疏导路径引导图加以显示,从而达到优化目标引导路径的目的。这些现象表面,最优路径算法呈现了越来越重要的发展趋势。在国内,最短路径算法也有着很广的应用。比如在实际中的汽车导航系统以及各种应急系南昌航空大学软件学院东软班 摘 要iv统等(如 110 报警、119 火警以及 120 医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在 15 一 35 内,在行车过程中还需要实时计算出车辆前方的行驶路线,这就决定了最短路径问题的实现应该是高效率的。按照城乡运输一体化的总体思路,为实现农村村村通客车的目标,针对农村客运线路繁杂,节点众多的特点,布局优化农村公路客运网的规划和建设是农村发展的重要内容,为落实贯彻中央 2004 年 l 号文件,解决三农问题,全面建设小康社会,实现人便于行,货畅其流。需要从规划布局的角度,科学地审视农村公路网和客运线路。村村通客车,是农村客运网的基本要求,但农村村屯点多面广,线路繁杂,网络节点众多,道路迂回曲折。如何科学合理的选择路径,即达到农村客运网络畅达便捷,合理布局即是关键问题。 现有的客运线路,系依托路网,村屯自然经济和区域特点,经经营者申报,交通运政管理部门审批而形成;其路径是否合理,线路覆盖和便捷程度,总体资源配置是否优化,尚无完整定量分析,系统和路网是否科学等一系列问题还有待确定。在未来,最短路径算法将应用到更加微元化的用户群体中,所以加快对最短路径算法的研发是大势所趋。3.系统主要研究内容对最短路问题的研究早在上个世纪 60 年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家 E.W.Dijkstra 在 1959 年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图 G 中一特定点到其它各顶点的最短路。后来海斯在 Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由 Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题。在地图中最短路径的搜索算法研究中,每种算法的优劣的比较原则主要遵循以下三点:(1)算法的完全性:提出一个问题,该问题存在答案,该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。(2)算法的时间复杂性: 提出一个问题,该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。(3)算法的空间复杂性:算法在执行搜索问题答案的同时,需要多少存储空间。算法占用资源越少,算法的性能越好。故本课题的研究方向在于模拟实现 Dijkstra 算法、Floyd 算法、A*算法,并比较其在各种环境下的优劣。4.系统架构以及模块动作时序图:南昌航空大学软件学院东软班 摘 要v最优路径算法研究地图数据处理模块最优路径搜索模块界面信息处理模块地图数据读出模块地图数据写入模块A * 算法搜索最优路径模块F l o y d算法搜索最优路径模块界面显示输出模块界面信息输入处理模块D i j k s t ra 算法搜索最优路径模块图 1 系统架构图界面信息处理 最优路径搜索 地图数据处理顶层包 : : 用户用户信息输入起点终点信息地图数据修改信息修改成功与否最优路径结果返回结果反馈算法种类选择图 2 模块时序图概要:本系统主要分为最优路径搜索、界面信息处理、地图数据处理等模块,三个模块之间由一些全局变量存储信息以达到关联。用户一旦打开程序,就自动读取地图数据并显示在界面中,用户可以自由选取起点、终点,改变地图迷宫结构,并最后选择最优路径算法进行计算,再由 UI 接口将路径动态的显示出来。5.Dijkstra 算法的设计与实现:南昌航空大学软件学院东软班 摘 要viDijkstra 算法是典型的算法。Dijkstra 算法是很有代表性的算法。Dijkstra 一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用 OPEN, CLOSE 表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。首先,引进一个辅助向量 D,它的每个分量 D[i]表示当前所找到的从始点 v 到每个终点 vi的的长度:如 D[3]=2 表示从始点 v 到终点 3 的路径相对最小长度为 2。这里强调相对就是说在算法过程中 D 的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为:若从 v 到 vi 有弧,则 D 为弧上的权值;否则置 D 为∞。显然,长度为 D[j]=Min{D | vi∈V} 的路径就是从 v 出发的长度最短的一条。此路径为(v,vj)。 那么,下一条长度次短的是哪一条呢?假设该次短路径的终点是 vk,则可想而知,这条路径或者是(v,vk),或者是(v,vj,vk)。它的长度或者是从 v 到 vk 的弧上的权值,或者是 D[j]和从 vj 到 vk 的弧上的权值之和。 一般情况下,假设 S 为已求得的终点的集合,则可证明:下一条最短路径(设其终点为 X)或者是弧(v,x),或者是中间只经过 S 中的顶点而最后到达顶点 X 的路径。因此,下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中, D 或者是弧(v,vi)上的权值,或者是 D[k](vk∈S)和弧(vk,vi)上的权值之和。算法描述如下: 1)arcs 表示弧上的权值。若不存在,则置 arcs 为∞(在本程序中为 MAXCOST) 。S 为已找到从 v 出发的的终点的集合,初始状态为空集。那么,从 v 出发到图上其余各顶点 vi 可能达到的度的初值为 D=arcs[Locate Vex(G,v),i] vi∈V 2)选择 vj,使得 D[j]=Min{D | vi∈V-S} 3)修改从 v 出发到集合 V-S 上任一顶点 vk可达的最短路径长度。按路径长度递增次序产生算法:把顶点集合 V 分成两组:(1)S:已求出的顶点的集合(初始时只含有源点 V0)(2)V-S=T:尚未确定的顶点集合将 T 中顶点按递增的次序加入到 S 中,保证:(1)从源点 V0 到 S 中其他各顶点的长度都不大于从 V0 到 T 中任何顶点的最短路径长度(2)每个顶点对应一个距离值S 中顶点:从 V0 到此顶点的长度T 中顶点:从 V0 到此顶点的只包括 S 中顶点作中间顶点的最短路径长度依据:可以证明 V0 到 T 中顶点 Vk 的,或是从 V0 到 Vk 的直接路径的权值;或是从 V0 经 S 中顶点到 Vk 的路径权值之和。 (反证法可证)南昌航空大学软件学院东软班 摘 要vii求最短路径算法步骤如下:1. 初始时令 S={V0},T={其余顶点},T 中顶点对应的距离值若存在,d(V0,Vi)为弧上的权值若不存在,d(V0,Vi)为∞2. 从 T 中选取一个其距离值为最小的顶点 W 且不在 S 中,加入 S3. 对其余 T 中顶点的距离值进行修改:若加进 W 作中间顶点,从 V0 到 Vi 的距离值缩短,则修改此距离值。重复上述步骤 2、3,直到 S 中包含所有顶点,即 W=Vi 为止以下是算法流程图:开始令 S = { V 0 } , T = { 其余顶点 对应的距离值 }从 T 中选取一个其距离值为最小的顶点 W 且不在 S 中 , 加入 S对其余 T 中顶点的距离值进行修改W = V i ?结束Y e sN o图 3 Dijkstra 算法流程图6.A*算法的设计与实现:A*算法,A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。估价值与实际值越接近,估价函数取得就越好。南昌航空大学软件学院东软班 摘 要viiiA*[1](A-Star)算法是一种静态路网中求解最短路最有效的方法,公式表示为: f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点 n 到目标点的估价函数,g(n) 是在状态空间中从初始节点到 n 节点的实际代价,h(n) 是从 n 到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件,关键在于估价函数 h(n)的选取:估价值 h(n)实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。开始把起始点 S 添加到 o p e n l i s tO p e n l i s t 是否为空从 o p e n l i s t 取得一个节点 X , 并将其从 o p e n l i s t 中删除判断该 X 节点是否是目标节点取出 X 的所有子节点 Y , 组成集合 { Y }Y 是否在 o p e n l i s t 和c l o s e l i s t 当中求 Y 的估价值 ; 并将 Y 插入 O P E N 表中若 Y 的估价值小于 O P E N 表的估价值 ,则 更新 O P E N 表中的估价值更新 C L O S E 表中的估价值 ,从 C L O S E 表中移出节点 , 并放入 O P E N 表中将 X 节点插入 C L O S E 表中 , 按照估价值将 O P E N 表中的节点排序结束检查 c l o s e l i s t 是否为空 , 若不空则将 c l o s e l i s t 输入作为最优路径Y e sN oY 不在 O P E N 表和 C L O S E 表中Y 在 O P E N 表中Y 在 C L O S E 表中N oY e s图 4 A*算法流程图南昌航空大学软件学院东软班 摘 要ix7.floyd 算法的设计与实现:Floyd 算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该算法通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n 开始,递归地进行 n 次更新,即由矩阵 D(0)=A,按一个公式,构造出矩阵 D(1);又用同样地公式由 D(1)构造出 D(2);……;最后又用同样的公式由 D(n-1)构造出矩阵 D(n)。矩阵 D(n)的 i 行 j 列元素便是 i 号顶点到 j 号顶点的最短路径长度,称 D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵 path 来记录两点间的最短路径。并且 Floyd 算法采用了松弛技术,对在 i 和 j 之间的所有其他点进行一次松弛。所以时间复杂度为 O(n^3);其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表示 i 到 j 的最短距离,K 是穷举 i,j 的断点,map[n,n]初值应该为 0,或者按照实际需求来定义。当然,如果这条路没有通的话,还必须特殊处理,比如设定为不存在 map[i,k]这条路。Floyd 算法具体实现流程为:1,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵 G 表示出来,如果从 Vi 到 Vj 有路可达,则 G[i,j]=d,d 表示该路的长度;否则 G[i,j]=无穷大。定义一个矩阵 D 用来记录所插入点的信息,D[i,j]表示从 Vi 到 Vj 需要经过的点,初始化 D[i,j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j] = min( G[i,j], G[i,k]+G[k,j] ),如果 G[i,j]的值变小,则 D[i,j]=k。在 G 中包含有两点之间最短道路的信息,而在 D 中则包含了最短通路径的信息。例子:如果要寻找从 V5 到 V1 的路径。根据 D,假如 D(5,1)=3 则说明从 V5 到 V1 经过 V3,路径为{V5,V3,V1},如果 D(5,3)=3,说明 V5 与 V3 直接相连,如果 D(3,1)=1,说明 V3 与 V1 直接相连。Floyd 算法适用于 APSP(All Pairs Shortest Paths),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra 算法。南昌航空大学软件学院东软班 摘 要x优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单缺点:时间复杂度比较高,不适合计算大量数据开始初始化D i s ( i , j ) = j选取除了 u , v 以及探索过的 k 点外的任一节点 k 。检查 D i s ( i , k ) + D i s ( k , j ) < D i s ( i , j ) 是否成立将点 k 假如 D i s ( i , j ) 中 , 更新 D i s ( i , j )是否还存在未探寻到的节点 k结束Y e sN oY e sN o图 5 Floyd 算法流程图8.三种算法之间的比较与总结:a.搜索速度比较:对5张图分别采用Dijkstra算法、 算法、遗传算法进行路径规划,他们各自花费的时间A如表1所示.
    展开阅读全文
    1
      金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

    暂无评论,赶快抢占沙发吧。

    关于本文
    本文标题:基于导航最优路径算法的设计与实现.rar
    链接地址:http://www.gold-doc.com/p-218119.html
    收起
    展开