數(shù)字高程模型（Digital Elevation Model,DEM）已成為空間地形分析中的主要數(shù)據(jù)模型,基于DEM地形數(shù)據(jù)的路徑規(guī)劃問題也成為研究的熱點(diǎn)。最短路徑問題是圖論中經(jīng)典問題,已被廣泛應(yīng)用于機(jī)器人路徑規(guī)劃,旅行商問題（Traveling Salesman Problem,TSP）,電子地圖導(dǎo)航等方面。作為求解單源點(diǎn)問題的經(jīng)典算法,Dijkstra算法可有效、準(zhǔn)確地求解出圖結(jié)構(gòu)中單點(diǎn)源的全局最優(yōu)路徑。經(jīng)典Dijkstra算法的時(shí)間復(fù)雜度為O（n2）,使用最小堆存儲(chǔ)結(jié)構(gòu)可使其時(shí)間復(fù)雜度降為O（nlogn）。但對(duì)于求解地形數(shù)據(jù)的最短路徑問題,隨著節(jié)點(diǎn)數(shù)或邊數(shù)增加,算法時(shí)間將會(huì)呈指數(shù)級(jí)增長,其效率也隨之降低。面對(duì)大規(guī)模三維地形數(shù)據(jù),Dijkstra算法卻難以勝任。因此,如何使Dijkstra算法更好地求解大范圍高精度的柵格DEM地形數(shù)據(jù)的最短路徑成為重要的研究問題之一。本文主要工作如下:1)提出了一種快速的轉(zhuǎn)化地形數(shù)據(jù)的最短路徑方法。根據(jù)地形格網(wǎng)鄰域模型,本文將離散地形數(shù)據(jù)轉(zhuǎn)化為圖數(shù)據(jù),利用DEM相關(guān)地形信息,通過剪枝刪除不符合條件的節(jié)點(diǎn)之間的邊,以減少圖數(shù)據(jù)量。同時(shí),數(shù)據(jù)轉(zhuǎn)化過程可... 

【文章來源】：南京師范大學(xué)江蘇省 211工程院校

【文章頁數(shù)】：75 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖２．２邊劃分??

⑷無向圖Ｇ１?（ｂ）有向圖Ｇ２??圖２．１圖結(jié)構(gòu)??無向圖（Ｇｒａｐｈ）是一種邊沒有方向的圖，如圖２．１⑷所示。即相同的邊連接的兩??個(gè)點(diǎn)沒有次序關(guān)系，例如（Ｒ，?ｖ２）和〇２，?代表的是相同的邊。??有向圖（Ｄｉｇｒａｐｈ）是一種邊有方向的圖，如圖２．１（ｂ）所示。即每一條邊都是有次序??關(guān)系，例如＜?＞與＜?＞是表示兩條不同的邊，而邊＜?＞是指從節(jié)點(diǎn)ｖｉ??指向節(jié)點(diǎn)方向的邊，化代表該邊的尾，代表該邊的頭。＜?巧，＾１?＞是指從節(jié)點(diǎn)ｈ指??向節(jié)點(diǎn)Ｖｉ方向的邊，代表該邊的尾，１＾代表該邊的頭。??稀疏圖與稠密圖無準(zhǔn)確的定義，而是相對(duì)而言。在圖Ｇ＝?（Ｖ，?Ｅ）中，邊數(shù)小于??ｎ＊ｌ〇ｇ（ｎ）的圖稱為稀疏圖；反之

＼＾ｍＴ?５？〇?Ｖ??〇?ｔｉｆ??圖２．４三維概率路圖的路徑??圖２．５為二維空間上的可視圖法，圖２．６為三維空間上的可視圖法。根據(jù)二維空??間的可視圖法，在二維空間上求解最短路徑的搜索空間數(shù)據(jù)是由障礙物若干個(gè)頂點(diǎn)的??連線組成的。Ｋｕｗａｔａ和Ｈ〇Ｗｆ４Ｇ］將可視圖法由二維空間推廣到三維空間上并讓其適??用于ＵＡＶ路徑規(guī)劃。在圖２．６中，通過從可視圖法構(gòu)造的路線圖獲得的最短路徑必??定穿過長方體障礙物的頂點(diǎn)，但實(shí)際ＵＡＶ的運(yùn)動(dòng)最優(yōu)軌跡（折線ＳＭＮＧ）可能并不??經(jīng)過障礙物的頂點(diǎn)，這種情況表明可視圖法對(duì)三維空間環(huán)境建模得到的路圖非優(yōu)的。??圖２．５二維可視圖法??１４??


本文編號(hào)：3305233