gps车载导航仪中最短路径算法设计与实现毕业论文

《gps车载导航仪中最短路径算法设计与实现毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录内容提要I1.引言11.1全球定位系统GPS11.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参考文

2、献12ABSTRACT13GPS车载导航中最短路径算法设计与实现学生姓名：指导教师：内容提要在GPS导航最短路径的研究中最为常见的最短路径算法有蚁群算法、地杰斯特拉算法[1]等。本文主要讨论GPS导航的最短路径算法，总体思路为：在地图的主要街道或十字路口设置预设点，确定起点和终点坐标后，根据两点之间的坐标差找到两点间的预设点，从而找到相邻预设点间的最优值，最后根据坐标找出最短路径。关键词GPS导航最短路径算坐标差预设点1.引言自20世纪后期以来，随着全球经济的深入发展，世界各国城市（尤其是大城市）的人口和车辆持续增长，由于交

3、通拥挤而造成的损失随之逐年增加。因而各国竞相投资修建交通设施，试图解决这一问题。但是车辆的增长速度远远高于道路和其他交通设施的增长速度，由此带来的有目共睹的事实是道路交通系统的复杂性和拥挤度的与日俱增[1]。近年来人们已经逐渐认识到单纯依靠增加道路基础设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设施，才是合理可行的方法。由此出现了建设智能交通系统（IntelligentTransportationSystem,ITS）的热潮。事实上，

4、建立现代化的交通系统，已经成为国家现代化的重要标志之一。与此相关的一系列方法与技术也成为当今计算机科学、地理信息科学等相关学科中的研究重点和热点。车载导航系统的研制开发可以划分为相互关联的技术模块，其中的路径规划是其他功能模块运行的基础，包含了车载导航系统中的很多关键技术。由于车载导航系统对道路网络建模、实时路径计算等方面有着特别的要求，在学术、技术上还存在着许多没有完全解决的问题。本文就是重点研究了车载导航系统的最短路径问题[2]。1.1全球定位系统GPS全球定位系统（GlobalPositioningSystem-GPS

5、）是美国从本世纪70年代开始研制，历时20年，耗资200亿美元，于1994年全面建成，具有在海、陆、空，进行全方位实时三维导航与定位能力的新一代卫星导航与定位系统。经近10年我国测绘等部门的使用表明，GPS以全天候、高精度、自动化、高效益等显著特点，赢得广大测绘工作者的信赖，并成功地应用于大地测量、工程测量、航空摄影测量、运载工具导航和管制、地壳运动监测、工程变形监测、资源勘察、地球动力学等多种学科，从而给测绘领域带来一场深刻的技术革命[2]。GPS由三个独立的部分组成：①空间部分：21颗工作卫星，3颗备用卫星。②地面支撑系

6、统：1个主控站，3个注入站，5个监测站。③用户设备部分：接收GPS卫星发射信号，以获得必要的导航和定位信息，经数据处理，完成导航和定位工作[3]。GPS接收机硬件一般由主机、天线和电源三部分组成。GPS技术作为一种新兴的导航技术，它具有以往的任何导航技术所没有的巨大的优越性，无论是定位精度、服务提供实时性、时间的精确性、全天候不间断性等等特点，都是任何别的导航技术所不能比拟的。它刚一出现和投入使用，就极大的改变了人类的工作和生活。随着全球定位系统的不断改进，硬、软件的不断完善，应用领域正在不断地开拓，目前已遍及国民经济各种部

7、门，并开始逐步深入人们的日常生活。1.2最短路径算法的应用与发展1.2.1最短路径算法的应用最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及120医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问

8、题的实现应该是高效率的。在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪