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

论文摘要

GIS技术在当前计算机应用领域中很热门,本文研究了GIS技术在实际工程中的应用及实现问题。地理信息系统的研究产生于上世纪六十年代,随着计算机技术的发展,其研究也越来越深入,其应用越来越广泛。从军事上的战场电子指挥到日常生活中的个人导航系统,无不应用了GIS技术。如何快速又节省系统资源的实现大型网络图中的最短路径搜索是GIS技术在实际应用非常有意义的一个课题,很多具有现实意义的功能需求,比如:如何最快?如何路程最短?如何最少经费?都和GIS技术息息相关,因而对GIS系统中最短路径搜索算法的研究具有重要的研究价值和实际意义。详细介绍了一种最短路径搜索算法的设计及其优化。经典的Dijkstra算法是针对网状图中求取任意两个结点间的最短路径的一种贪心算法,具有原理简单,易于实现,技术成熟,可扩展性强等优点。但是面对例如中大型城市交通网络这种大型的网络计算,经典的算法也暴露出多次迭代后误差增大,效率低下,资源耗费大等缺点,无论是计算精度还是算法响应时间都无法满足实际应用的要求。因此如何保证精度和速度求解大规模复杂网络的最短路径问题成为了实现GIS应用系统的瓶颈问题。针对这个问题,从算法精度和算法优化两方面对经典的Dijkstra算法进行了优化设计。算法精度方面,由于经纬度求算的实际距离在多次叠加后误差增大,提出采用参数修正的高斯投影算法,不仅大大减少了迭代计算误差也提高了计算速度。算法优化方面,采用效率更高,更加智能的A*算法控制搜索过程;数据结构方面采用邻接矩阵表示网络图的拓扑结构,然后用动态十字链表结构存储邻接矩阵元素,把计算所需的数据分块提炼精简到内存中,通过多次到内存中交换数据达到减少内存使用的目的。实践结果表明,优化后的算法在计算时间上和计算精度上都比经典Dijkstra算法有明显改善。较为详细地介绍了一个GIS系统的设计,内容包括地图信息的处理和优化,针对城市交通网络的数据结构优化等等。重点介绍了系统显示和动态地图的相关问题和原理等。最后介绍了系统的人机交互和紧急中心的相关内容。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景与研究意义
• 1.2.1 研究背景
• 1.2.2 研究意义
• 1.3 最短路径搜索问题的研究现状
• 1.4 GIS 技术
• 1.5 本论文的工作和论文编排
• 第二章 最短路径问题的理论基础
• 2.1 最短路径问题
• 2.1.1 最短路径问题的引出
• 2.1.2 解决最短路径问题的思路
• 2.2 图论
• 2.2.1 图论的基本概念
• 2.2.2 图的基本概念在城市网络图中的应用
• 2.2.3 图的矩阵表示
• 2.3 高斯投影
• 2.3.1 地球椭球基本参数
• 2.3.2 高斯投影基本几何模型
• 2.3.3 高斯投影的计算公式及其简化
• 2.3.4 高斯投影的分带
• 2.4 现代优化算法
• 2.4.1 组合最优化问题
• 2.4.2 启发式搜索算法
• 2.4.3 启发式搜索算法中的A*算法
• 2.5 数学规划
• 2.5.1 线性规划
• 2.5.2 非线性规划
• 2.5.3 多目标规划
• 2.5.4 目标规划
• 第三章 Dijkstra 算法及其优化
• 3.1 最短路径问题的数学描述
• 3.2 经典Dijkstra 算法
• 3.2.1 跌代移动
• 3.2.2 经典算法存在的问题
• 3.2.3 算法的优化解决方案
• 3.3 最短路径搜素算法的实现
• 3.3.1 约束条件和数据建模
• 3.3.2 优化算法程序实现相关问题
• 3.4 实验结果与分析
• 第四章 个人导航软件系统的设计与实现
• 4.1 地图数据的获取与处理
• 4.1.1 节点道路信息的提取
• 4.1.2 经纬度校准
• 4.1.3 图层和比例尺划分
• 4.2 图形显示
• 4.2.1 坐标系
• 4.2.2 窗口与视区
• 4.2.3 裁减算法
• 4.3 动态地图相关问题
• 4.3.1 轨迹与道路判交
• 4.3.2 地图的几何变换
• 4.3.3 目标点在某区域内部的判断
• 4.4 人机交互与紧急中心
• 4.4.1 交互导航的概要描述
• 4.4.2 交互导航的过程描述
• 4.4.3 紧急中心
• 总结与展望
• 一、总结
• 二、展望
• 参考文献
• 致谢
• 附录A：读学位期间发表的论文及参与的课题