开题报告-基于导航最优路径算法的设计与实现

毕业设计（论文）开题报告题 目： 基于导航最优路径算法的设计与实现学 院： 专业名称： 班级学号： 学生姓名： 指导教师： 填 表 日 期 2013 年 12 月 4 日南昌航空大学东软班 开题报告1一、选题依据、目的和意义自 20 世纪后期以来，随着全球经济的深入发展，世界各国城市（尤其是大城市）的人口和车辆持续增长，由于交通拥挤而造成的损失随之逐年增加。因而各国竞相投资修建交通设施，试图解决这一问题。但是车辆的增长速度远远高于道路和其他交通设施的增长速度，由此带来的有目共睹的事实是道路交通系统的复杂性和拥挤度的与日俱增。近年来人们已经逐渐认识到单纯依靠增加道路基础设施建设不可能从根本上解决车辆的快速增长与交通设施滞后之间的突出矛盾。只有在计算机、信息和通讯等高科技手段的辅助下充分利用现有的道路基础设施，才是合理可行的方法。由此出现了建设智能交通系统（Intelligent Transportation System, ITS）的热潮。事实上，建立现代化的交通系统，已经成为国家现代化的重要标志之一。与此相关的一系列方法与技术也成为当今计算机科学、地理信息科学等相关学科中的研究重点和热点。车载导航系统的研制开发可以划分为相互关联的技术模块，其中的路径规划是其他功能模块运行的基础，包含了车载导航系统中的很多关键技术。由于导航系统对道路网络建模、实时路径计算等方面有着特别的要求，在学术、技术上还存在着许多没有完全解决的问题。本课题就是重点研究了导航系统的最短路径问题。望能通过几种最短路径算法的设计与实现，来深入探讨最优路径搜索的问题。二、国内外研究现状及发展趋势2.1 国外现状及发展趋势在国外，各种导航系统对最短路径算法的应用比较发达。最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接的应用。在很多目标信息引导系统的设计中需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏南昌航空大学东软班 开题报告2导系统时，将图论中 Dijkstra 算法应用于目标信息引导系统的设计中，通过 Dijkstra 算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序，动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的。这些现象表面，最优路径算法呈现了越来越重要的发展趋势。2.2 国内现状及发展趋势在国内，最短路径算法也有着很广的应用。比如在实际中的汽车导航系统以及各种应急系统等(如 110 报警、119 火警以及 120 医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在 15 一 35 内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。按照城乡运输一体化的总体思路，为实现农村村村通客车的目标，针对农村客运线路繁杂，节点众多的特点，布局优化农村公路客运网的规划和建设是农村发展的重要内容，为落实贯彻中央 2004 年 l 号文件，解决三农问题，全面建设小康社会，实现人便于行，货畅其流。需要从规划布局的角度，科学地审视农村公路网和客运线路。村村通客车，是农村客运网的基本要求，但农村村屯点多面广，线路繁杂，网络节点众多，道路迂回曲折。如何科学合理的选择路径，即达到农村客运网络畅达便捷，合理布局即是关键问题。 现有的客运线路，系依托路网，村屯自然经济和区域特点，经经营者申报，交通运政管理部门审批而形成；其路径是否合理，线路覆盖和便捷程度，总体资源配置是否优化，尚无完整定量分析，系统和路网是否科学等一系列问题还有待确定。 在未来，最短路径算法将应用到更加微元化的用户群体中，所以加快对最短路径算法的研发是大势所趋。三、研究的主要内容及实验方案3.1、毕业设计的主要研究内容对最短路问题的研究早在上个世纪 60 年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家 E.W.Dijkstra 在 1959 年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图 G 中一特定点到其它各顶点的最短路。后来海斯在 Dijkstra 算法的基础之上南昌航空大学东软班 开题报告3提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由 Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题。在地图中最短路径的搜索算法研究中，每种算法的优劣的比较原则主要遵循以下三点:(1)算法的完全性：提出一个问题，该问题存在答案，该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。(2)算法的时间复杂性: 提出一个问题，该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。(3)算法的空间复杂性:算法在执行搜索问题答案的同时，需要多少存储空间。算法占用资源越少，算法的性能越好。故本课题的研究方向在于模拟实现 Dijkstra 算法、Floyd 算法、A*算法，并比较其在各种环境下的优劣。3.2、实验方案使用 Visual C+ MFC 进行开发，成果物软件通过对地图数据的加载，在界面上绘制出一张模拟地图，再用用户选择起点、终点以及调用的最短路径算法，进而由程序进行计算搜索出该起点到终点的最优路径，并绘制成图形展现给用户。我们再次可以通过同一起点、终点的情况来比较不同算法的计算结果是否会有不同，也可以通过不同的起点、终点来比较同一种最短路径算法在各种情况下进行计算的优劣。四、目标，主要特色及工作进度4.1 目标：最短路径问题是图论研究中的一个重要课题，也是网络分析中关键的问题，它广泛应用于网络优化、交通运输、物流配送、电子导航等领域。而此时最短路径问题不仅仅指一般“纯距离”意义上的最短路径，还可以引申到其他意义上的度量，如经济费用、时间、吞吐量等。例如，城市交通中旅行者选择出游最佳路径，交通网络中的最可靠路径、最大容量，最少费用问题，及统筹方法中关键路线问题等，都可以转化为最短路径问题。本文就正是研究不同算法在不同情况下搜索最优路径的优劣，希望能通过本课题加深大家对最优路径算法的认识。南昌航空大学东软班 开题报告44.2 主要特色：本 研 究 主 要 针 对 于 算 法 设 计 ， 实 现 了 Dijkstra 算法、Floyd 算法、A*算法等三种算法在最短路径搜索中的应用，并能通过 Visual C+ MFC 直观的将搜索结果绘制出来。4.3 工作进度：已基本实现 A*算法在最短路径中的应用，其他两种算法还是研究之中。Visual C+ MFC的绘图方法本人之前有过了解，但还仍需对该方面技术的调研。已经理解清 楚 项 目 需 要 ， 并 编制 了 开 题 报 告 。五、主要参考文献1 卜月华图论及其应用M南京：东南大学出版社，20002 李玲最短路问题在运输网络中的应用M，20063 戴文舟交通网络中最短路径算法的研究D重庆大学硕士学位论，20044 乐阳，龚健雅Dijkstra 最短路径算法的一种高效率实现N武汉测绘科技大学学报5 唐一珠，郑茜颖GPS 车载多媒体导航系统的研究与开发M福州大学计算机系，2000-12-016 刘大杰，施一民，过静珺全球定位系统（GPS）的原理与数据处理M上海：同济大学出版社，19967 赵伟华，章复嘉，梁红兵车辆导航系统最优路径规划的研究与实现N杭州电子工业学院学报，2003，23（1） 8 严蔚敏，吴伟民数据结构M北京：清华大学出版社，20079 毕军，付梦印，周培德一