试析个人导航软件系统中的一种路径搜索算法及其优化

《试析个人导航软件系统中的一种路径搜索算法及其优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代号10530学号200611051171分类号TP391.72密级硕士学位论文个人导航软件系统中的一种路径搜索算法及其优化学位申请人胡伟凡导师姓名及职称杨恢先教授学院名称信息工程学院学科专业控制理论与控制工程研究方向控制系统计算机辅助设计二〇〇九年六月七日个人导航软件系统中的一种路径搜索算法及其优化学位申请人胡伟凡导师姓名及职称杨恢先教授学院名称信息工程学院学科专业控制理论与控制工程研究方向控制系统计算机辅助设计学位申请级别工学硕士学位学位授予单位湘潭大学论文提交日期2009-6-07APathSearchingAlgorithmand

2、It’sOptimizationinPersonalNavigationSystemCandidateHuWeifanSupervisorandRankProfessorYangHuixianCollegeCollegeofInformationEngineeringProgramControlTheory&ControlEngineeringSpecializationCADofControlSystemDegreeMasterofEngineeringUniversityXiangtanUniversityDate2009-6-07湘潭大

3、学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可

4、以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日摘要GIS技术在当前计算机应用领域中很热门，本文研究了GIS技术在实际工程中的应用及实现问题。地理信息系统的研究产生于上世纪六十年代，随着计算机技术的发展，其研究也越来越深入，其应用越来越广泛。从军事上的战场电子指挥到日常生活中的个人导航系统，无不应用了GIS技术。如何快速又节省系统资源的实现大型网络图中的最短路径搜索是GIS技术在实际应用非常有意义的一个课题，很多具有现实意义的功能需求，比如：如何最快？如何路程最短？如何

5、最少经费？都和GIS技术息息相关，因而对GIS系统中最短路径搜索算法的研究具有重要的研究价值和实际意义。详细介绍了一种最短路径搜索算法的设计及其优化。经典的Dijkstra算法是针对网状图中求取任意两个结点间的最短路径的一种贪心算法，具有原理简单，易于实现，技术成熟，可扩展性强等优点。但是面对例如中大型城市交通网络这种大型的网络计算，经典的算法也暴露出多次迭代后误差增大，效率低下，资源耗费大等缺点，无论是计算精度还是算法响应时间都无法满足实际应用的要求。因此如何保证精度和速度求解大规模复杂网络的最短路径问题成为了实现GIS应用系统的瓶颈问题。

6、针对这个问题，从算法精度和算法优化两方面对经典的Dijkstra算法进行了优化设计。算法精度方面，由于经纬度求算的实际距离在多次叠加后误差增大，提出采用参数修正的高斯投影算法，不仅大大减少了迭代计算误差也提高了计算速度。算法优化方面，采用效率更高，更加智能的A*算法控制搜索过程；数据结构方面采用邻接矩阵表示网络图的拓扑结构，然后用动态十字链表结构存储邻接矩阵元素，把计算所需的数据分块提炼精简到内存中，通过多次到内存中交换数据达到减少内存使用的目的。实践结果表明，优化后的算法在计算时间上和计算精度上都比经典Dijkstra算法有明显改善。较为详

7、细地介绍了一个GIS系统的设计，内容包括地图信息的处理和优化，针对城市交通网络的数据结构优化等等。重点介绍了系统显示和动态地图的相关问题和原理等。最后介绍了系统的人机交互和紧急中心的相关内容。关键词：GIS；Dijkstra算法；高斯投影；最短路径搜索；A*算法；十字链表；IAbstractGIStechnologyisverypopularinthefieldofcurrentcomputerapplications.ThispaperresearchestheapplicationandimplementationofGIStechnol

8、ogyinactualengineering.ThestudyofGISisstartedinthe60’soflastcentury.Withthedevelop