搜索
GPS车载导航中最短路径算法设计与实现作者姓名指导教师所学专业计算机科学与技术班级所属院系学院学习年限2008年9月至2012年7月二○一二年六月学号：本科毕业论文（设计）目录内容提要..................................................................I1.引言...................................................................11.1全球定位系统GPS...................................................11.2最短路径算法的应用与发展..........................................11.2.1最短路径算法的应用.............................................21.2.2最短路径算法的发展趋势........................................22.最短路径算法的设计与实现...............................................32.1经典的Dijkstra算法Floyd算法.....................................32.1.1Dijkstra算法..................................................32.1.2Floyd算法.....................................................52.2A*算法的设计与实现................................................52.2.1A*算法的优势...................................................52.2.2总体设计思想...................................................52.2.3详细论述.......................................................62.2.4算法总结.......................................................73.GPS车载导航最短路径算法的实现.........................................83.1道路网中信息的采集................................................83.2算法实现步骤......................................................83.3程序运行结果......................................................94.结语..................................................................10致谢.....................................................................11参考文献.................................................................12ABSTRACT.................................................................13IGPS车载导航中最短路径算法设计与实现学生姓名：指导教师：内容提要在GPS导航最短路径的研究中最为常见的最短路径算法有蚁群算法、地杰斯特拉算法[1]等。本文主要讨论GPS导航的最短路径算法，总体思路为：在地图的主要街道或十字路口设置预设点，确定起点和终点坐标后，根据两点之间的坐标差找到两点间的预设点，从而找到相邻预设点间的最优值，最后根据坐标找出最短路径。关键词GPS导航最短路径算坐标差预设点山西大学商务学院本科毕业论文（设计）11.引言自20世纪后期以来，随着全球经济的深入发展，世界各国城市（尤其是大城市）的人口和车辆持续增长，由于交通拥挤而造成的损失随之逐年增加。因而各国竞相投资修建交通设施，试图解决这一问题。但是车辆的增长速度远远高于道路和其他交通设施的增长速度，由此带来的有目共睹的事实是道路交通系统的复杂性和拥挤度的与日俱增[1]。近年来人们已经逐渐认识到单纯依靠增加道路基础设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设施，才是合理可行的方法。由此出现了建设智能交通系统（IntelligentTransportationSystem,ITS）的热潮。事实上，建立现代化的交通系统，已经成为国家现代化的重要标志之一。与此相关的一系列方法与技术也成为当今计算机科学、地理信息科学等相关学科中的研究重点和热点。车载导航系统的研制开发可以划分为相互关联的技术模块，其中的路径规划是其他功能模块运行的基础，包含了车载导航系统中的很多关键技术。由于车载导航系统对道路网络建模、实时路径计算等方面有着特别的要求，在学术、技术上还存在着许多没有完全解决的问题。本文就是重点研究了车载导航系统的最短路径问题[2]。1.1全球定位系统GPS全球定位系统（GlobalPositioningSystem-GPS）是美国从本世纪70年代开始研制，历时20年，耗资200亿美元，于1994年全面建成，具有在海、陆、空，进行全方位实时三维导航与定位能力的新一代卫星导航与定位系统。经近10年我国测绘等部门的使用表明，GPS以全天候、高精度、自动化、高效益等显著特点，赢得广大测绘工作者的信赖，并成功地应用于大地测量、工程测量、航空摄影测量、运载工具导航和管制、地壳运动监测、工程变形监测、资源勘察、地球动力学等多种学科，从而给测绘领域带来一场深刻的技术革命[2]。GPS由三个独立的部分组成：①空间部分：21颗工作卫星，3颗备用卫星。②地面支撑系统：1个主控站，3个注入站，5个监测站。③用户设备部分：接收GPS卫星发射信号，以获得必要的导航和定位信息，经数据处理，完成导航和定位工作[3]。GPS接收机硬件一般由主机、天线和电源三部分组成。GPS技术作为一种新兴的导航技术，它具有以往的任何导航技术所没有的巨大的优越性，无论是定位精度、服务提供实时性、时间的精确性、全天候不间断性等等特点，都是任何别的导航技术所不能比拟的。它刚一出现和投入使用，就极大的改变了人类的工作和生活。随着全球定位系统的不断改进，硬、软件的不断完善，应用领域正在不断地开拓，目前已遍及国民经济各种部门，并开GPS车载导航中最短路径算法设计与实现2始逐步深入人们的日常生活。1.2最短路径算法的应用与发展1.2.1最短路径算法的应用最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及120医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序，动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的。按照城乡运输一体化的总体思路，为实现农村村村通客车的目标，针对农村客运线路繁杂，节点众多的特点，布局优化农村公路客运网的规划和建设是农村发展的重要内容，为落实贯彻中央2004年l号文件，解决三农问题，全面建设小康社会，实现人便于行，货畅其流。需要从规划布局的角度，科学地审视农村公路网和客运线路。村村通客车，是农村客运网的基本要求，但农村村屯点多面广，线路繁杂，网络节点众多，道路迂回曲折。如何科学合理的选择路径，即达到农村客运网络畅达便捷，合理布局即是关键问题。现有的客运线路，系依托路网，村屯自然经济和区域特点，经经营者申报，交通运政管理部门审批而形成；其路径是否合理，线路覆盖和便捷程度，总体资源配置是否优化，尚无完整定量分析，系统和路网是否科学等一系列问题还有待确定[4]。1.2.2最短路径算法的发展趋势目前，静态的最短路径算法已经十分完善。但是，在实践中，网络特征可能时刻会发生变化，要求最短路径算法必须能够实时地自动更新。这类问题主要集中在交通网络的实时导航、通勤、调度和计算机互联网的数据传递路由等发面。在动态最短路径为题中弧段权值、节点耗费等均为时间山西大学商务学院本科毕业论文（设计）3t的函数，既可以是连续的，也可以是离散的。假定网络路径权值服从FIFO原则的一致性假设前提，任何静态的LS和LC算法均可拓展为时间依赖的最短路径算法。文献[5]提出了一个动态最短路径算法的范例Chrono-SPT，通过对时态弧段的离散化时态的拓扑访问，给出了无环图的最小代价路径问题的一般解法，并对其理论上的时间复杂度进行了初步的分析，讨论了FIFO时空网络的基本特征，并形式化讨论了对应的最短路径算法。文献[6]考虑了弧段权值依时间变化的最短路径问题，针对互联网的数据实时传输过程，提出了3种依赖时间的最短路径模型和相应算法。文献[7]也对弧段权值变化的最短路径算法进行了讨论，给出了针对弧段添加和弧段权值减少的时间复杂度为O(n*n)的修改算法。随着计算机处理数据量的逐渐增多，传统的串行计算机的负荷也逐渐加重。运行在服务器端的最短路径算法必须向基于图分解的并行算法的方向发展，以满足大量的实时最短路径查询的需要。关于最短路径并行算法的讨论有两种类型，一种基于教抽象的并行计算模型，不限制处理器的数目，研究给定问题的计算复杂度在并行计算的情况下能降到什么程度。如果已经达到下界，在设法减少处理器的数目，或放松对处理器间耦合程度的一些不尽合理或不尽现实的要求；另一类研究则针对实际的并行计算系统，其处理器数是有限的（至少不可能与问题规模相当），研究如何设计或实现某个或某类问题的并行求解。此类并行算法的设计往往还伴有在实际系统上的计算实例和性能分析。由于对处理器的数目进行了合理的限制，并行计算系统在实践中更有价值，是最短路径问题算法并行化研究的趋势所在。2.最短路径算法的设计与实现对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图0ijw的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。2.1经典的最短路径算法2.1.1Dijkstra算法Dijkstra算法基本步骤：GPS车载导航