基于栅格地形数据的最短路径算法研究

论文摘要

数字高程模型(Digital Elevation Model,DEM)已成为空间地形分析中的主要数据模型,基于DEM地形数据的路径规划问题也成为研究的热点。最短路径问题是图论中经典问题,已被广泛应用于机器人路径规划,旅行商问题(Traveling Salesman Problem,TSP),电子地图导航等方面。作为求解单源点问题的经典算法,Dijkstra算法可有效、准确地求解出图结构中单点源的全局最优路径。经典Dijkstra算法的时间复杂度为O(n2),使用最小堆存储结构可使其时间复杂度降为O(nlogn)。但对于求解地形数据的最短路径问题,随着节点数或边数增加,算法时间将会呈指数级增长,其效率也随之降低。面对大规模三维地形数据,Dijkstra算法却难以胜任。因此,如何使Dijkstra算法更好地求解大范围高精度的栅格DEM地形数据的最短路径成为重要的研究问题之一。本文主要工作如下:1)提出了一种快速的转化地形数据的最短路径方法。根据地形格网邻域模型,本文将离散地形数据转化为图数据,利用DEM相关地形信息,通过剪枝删除不符合条件的节点之间的边,以减少图数据量。同时,数据转化过程可通过并行化方法来实现,从而提高路径算法的效率。在转换为图数据之后,Dijkstra算法用于求解基于图数据的最短路径。实验结果表明,本文提出的地形最短路径求解大大提高了算法的效率,并保证了结果的准确性。2)提出了一种基于MapReduce的Dijkstra并行化算法的网络优化方法。依据串行Dijkstra算法数据并行化特点,本文基于MapReduce并行计算框架,根据广度优先算法思想,实现了基于MapReduce的Dijkstra算法并行化方法。本文通过在Shuffle阶段合并关键字方法来减少网络通信开销,优化了算法并行化处理的效率。实验结果表明,该方法大大提高了基于大规模地形数据时求解最短路径的效率。3)提出了一种基于瓦片金字塔模型的最短路径加速方法。依据瓦片金字塔模型,本文采用同一区域范围不同分辨率DEM地形数据表示方法,利用层次空间关系将低分辨率地形数据映射到相应的高分辨率地形数据上。本文依据低分辨地形数据进行路径求解可有效地缩小高分辨率地形数据上的求解范围,从而提高算法求解效率。实验结果表明,该方法有效抑制搜索区域中节点数增加,大大提高算法的效率。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 论文研究背景与意义
•   1.2 国内外研究现状
•   1.3 论文组织结构
• 第2章 最短路径优化算法研究综述
•   2.1 图
•     2.1.1 图的基本概念
•     2.1.2 图的存储结构
•     2.1.3 图结构的并行化策略
•   2.2 路径规划
•     2.2.1 最短路径模型
•     2.2.2 基于二维空间路径规划
•     2.2.3 基于三维空间路径规划
•   2.3 最短路径规划方法
•   2.4 本章小结
• 第3章 基于DEM栅格数据的最短路径方法
•   3.1 DEM数字高程模型
•     3.1.1 地形的到数字表达
•     3.1.2 DEM格网模型
•   3.2 基于DEM的地形模型到图转化方法
•     3.2.1 格网邻域模型
•     3.2.2 基于格网邻域模型的数据转化方法
•     3.2.3 权重计算公式
•     3.2.4 剪枝处理
•   3.3 快速转化地形数据的的最短路径算法
•     3.3.1 常用最短路径算法介绍
•     3.3.2 算法框架
•     3.3.3 算法过程描述
•   3.4 实验分析
•     3.4.1 数据转化效率分析
•     3.4.2 不同的最短路算法对比
•     3.4.3 Dijkstra+算法与Dijkstra*算法的效率对比
•   3.5 本章小结
• 第4章 一种基于Dijkstra最短路径算法的并行化方法
•   4.1 Dijkstra算法并行化策略
•   4.2 MapReduce并行化框架
•     4.2.1 MapReduce原理
•     4.2.2 广度优先搜索（BFS）
•   4.3 基于广度优先搜索思想的Dijkstra算法并行化
•   4.4 实验分析
•     4.4.1 网络传输优化
•     4.4.2 数据量分析
•   4.5 本章小结
• 第5章 一种基于瓦片金字塔模型的最短路径加速算法
•   5.1 限制搜索区域法加速方法
•     5.1.1 搜索距离限制
•     5.1.2 搜索角度限制
•   5.2 瓦片金字塔模型
•   5.3 基于瓦片金字塔的加速策略
•   5.4 算法实现
•     5.4.1 DEM数据的压缩删减算法实现
•     5.4.2 最短路加速算法的实现
•   5.5 实验分析
•     5.5.1 相邻间隔点数的时间
•     5.5.2 算法的效率分析
•     5.5.3 精确度对比分析
•   5.6 本章小结
• 第6章 总结与展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 攻读硕士学位期间参加科研项目及发表/录用论文
• 致谢

文章来源

类型: 硕士论文

作者: 王艳丽

导师: 窦万峰

关键词: 最短路径,瓦片金字塔模型

来源: 南京师范大学

年度: 2019

分类: 基础科学,信息科技

专业: 自然地理学和测绘学,计算机软件及计算机应用

单位: 南京师范大学

分类号: TP301.6;P217

DOI: 10.27245/d.cnki.gnjsu.2019.000677

总页数: 75

文件大小: 7104K

下载量: 130