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

发布时间：2021-07-27 06:03

　　数字高程模型（Digital Elevation Model,DEM）已成为空间地形分析中的主要数据模型,基于DEM地形数据的路径规划问题也成为研究的热点。最短路径问题是图论中经典问题,已被广泛应用于机器人路径规划,旅行商问题（Traveling Salesman Problem,TSP）,电子地图导航等方面。作为求解单源点问题的经典算法,Dijkstra算法可有效、准确地求解出图结构中单点源的全局最优路径。经典Dijkstra算法的时间复杂度为O（n2）,使用最小堆存储结构可使其时间复杂度降为O（nlogn）。但对于求解地形数据的最短路径问题,随着节点数或边数增加,算法时间将会呈指数级增长,其效率也随之降低。面对大规模三维地形数据,Dijkstra算法却难以胜任。因此,如何使Dijkstra算法更好地求解大范围高精度的栅格DEM地形数据的最短路径成为重要的研究问题之一。本文主要工作如下:1)提出了一种快速的转化地形数据的最短路径方法。根据地形格网邻域模型,本文将离散地形数据转化为图数据,利用DEM相关地形信息,通过剪枝删除不符合条件的节点之间的边,以减少图数据量。同时,数据转化过程可... 

【文章来源】：南京师范大学江苏省 211工程院校

【文章页数】：75 页

【学位级别】：硕士

【部分图文】：

图２．２边划分??

⑷无向图Ｇ１?（ｂ）有向图Ｇ２??图２．１图结构??无向图（Ｇｒａｐｈ）是一种边没有方向的图，如图２．１⑷所示。即相同的边连接的两??个点没有次序关系，例如（Ｒ，?ｖ２）和〇２，?代表的是相同的边。??有向图（Ｄｉｇｒａｐｈ）是一种边有方向的图，如图２．１（ｂ）所示。即每一条边都是有次序??关系，例如＜?＞与＜?＞是表示两条不同的边，而边＜?＞是指从节点ｖｉ??指向节点方向的边，化代表该边的尾，代表该边的头。＜?巧，＾１?＞是指从节点ｈ指??向节点Ｖｉ方向的边，代表该边的尾，１＾代表该边的头。??稀疏图与稠密图无准确的定义，而是相对而言。在图Ｇ＝?（Ｖ，?Ｅ）中，边数小于??ｎ＊ｌ〇ｇ（ｎ）的图称为稀疏图；反之

＼＾ｍＴ?５？〇?Ｖ??〇?ｔｉｆ??图２．４三维概率路图的路径??图２．５为二维空间上的可视图法，图２．６为三维空间上的可视图法。根据二维空??间的可视图法，在二维空间上求解最短路径的搜索空间数据是由障碍物若干个顶点的??连线组成的。Ｋｕｗａｔａ和Ｈ〇Ｗｆ４Ｇ］将可视图法由二维空间推广到三维空间上并让其适??用于ＵＡＶ路径规划。在图２．６中，通过从可视图法构造的路线图获得的最短路径必??定穿过长方体障碍物的顶点，但实际ＵＡＶ的运动最优轨迹（折线ＳＭＮＧ）可能并不??经过障碍物的顶点，这种情况表明可视图法对三维空间环境建模得到的路图非优的。??图２．５二维可视图法??１４??


本文编号：3305233