本文關(guān)鍵詞：顧及地理實體屬性信息的網(wǎng)絡(luò)最短路徑分析算法研究

  更多相關(guān)文章： 最短路徑分析 層次劃分 距離搜索 路徑搜索

【摘要】：網(wǎng)絡(luò)圖中最短路徑的計算問題在圖論中是一個經(jīng)典的問題,一個最實際的應(yīng)用就是在道路網(wǎng)絡(luò)中進行路徑分析,如在給定的道路網(wǎng)中,尋找起點到目標(biāo)點的最佳路徑問題。在本課題研究中,假設(shè)給定的道路網(wǎng)中節(jié)點和邊不經(jīng)常改變,即在穩(wěn)定的道路網(wǎng)中進行最短路徑分析。對一般的小規(guī)模路網(wǎng)的路徑分析問題已有較為成熟的算法,而對大規(guī)模道路網(wǎng)的最短路徑分析問題,經(jīng)典的Di jkstra算法因為計算速度非常慢,故而這種經(jīng)典算法并不適用。在近幾年的時間里,針對大規(guī)模路網(wǎng)的路徑分析問題,提出了許多新的快速算法,這些算法有個共同點,就是預(yù)先計算和存儲輔助數(shù)據(jù)用于加速最短路徑的查詢。然而,在邊為非負(fù)權(quán)重的圖中,這些算法通常只考慮計算源點到目標(biāo)點的最短路徑簡單問題,而實際問題并沒有那么簡單,因此,在此需要擴充一下研究問題的定義,設(shè)置從源點到目標(biāo)點的所需要的時間作為邊的權(quán)重,充分考慮路網(wǎng)中節(jié)點和邊的屬性信息。雖然當(dāng)前已有根據(jù)此提出一些新的算法,但是這些算法并不是很有效。因此研究出一種新的算法是非常有必要的。 在本文中,基于道路網(wǎng)節(jié)點和邊實體的屬性信息,對最短路徑的分析提出了一種新的加速算法-HP (Hierarchy Partition)算法,這種算法包括如何對道路網(wǎng)的層次劃分、如何在路網(wǎng)中構(gòu)建輔助邊、如何對同一層級上的節(jié)點進行排序、如何對節(jié)點進行抽樣和最短路徑的求解。實驗數(shù)據(jù)從OpenStreetMap的鏡像站點下載,在數(shù)據(jù)預(yù)處理階段應(yīng)用開源插件-ArcGIS Editor For OSM Data,安裝嵌入ArcGIS中,應(yīng)用此插件提供的功能對OSM原數(shù)據(jù)進行預(yù)處理,把初步處理好的數(shù)據(jù),應(yīng)用XML2RDF格式轉(zhuǎn)換工具,把OSM數(shù)據(jù)轉(zhuǎn)成RDF數(shù)據(jù)格式,并保存在RDF-3X數(shù)據(jù)庫中。 在CH算法和TNR啟發(fā)下,對路網(wǎng)進行層次劃分和構(gòu)建輔助邊,結(jié)合Reach算法,對實驗數(shù)據(jù)抽樣,并求出近似解。在實驗過程中,采用5個實驗數(shù)據(jù),數(shù)據(jù)節(jié)點從5萬到2000萬,把實驗數(shù)據(jù)分成10個數(shù)據(jù)集作為查詢數(shù)據(jù)進行實驗,在實驗中分別比較HP算法、CH算法、Dijkstra算法和TNR算法在距離和路徑查詢效率。最后對整個實驗結(jié)果進行了詳細(xì)的分析,得出在預(yù)處理過程HP的空間消耗稍微比CH算法差,但是比其他的2種算法消耗要低得多,而在空間復(fù)雜度和時間復(fù)雜度上都比其他3種算法優(yōu)越。
【關(guān)鍵詞】：最短路徑分析 層次劃分 距離搜索 路徑搜索
【學(xué)位授予單位】：蘭州交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：P208
【目錄】：

• 摘要4-5
• Abstract5-9
• 1、緒論9-15
• 1.1 課題研究背景9
• 1.2 研究現(xiàn)狀綜述9-11
• 1.3 研究內(nèi)容和方法11-14
• 1.3.1 研究的內(nèi)容描述11-12
• 1.3.2 研究的方法12-14
• 1.4 論文結(jié)構(gòu)安排14-15
• 2、網(wǎng)絡(luò)數(shù)據(jù)表達模型與網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理15-25
• 2.1 網(wǎng)絡(luò)數(shù)據(jù)表達模型15-16
• 2.1.1 鄰接矩陣對網(wǎng)絡(luò)數(shù)據(jù)的表達15
• 2.1.2 鄰接表對網(wǎng)絡(luò)數(shù)據(jù)的表達15-16
• 2.2 地理數(shù)據(jù)的獲取與處理16-20
• 2.2.1 OSM地理數(shù)據(jù)的獲取16-17
• 2.2.2 OSM數(shù)據(jù)模型結(jié)構(gòu)17-19
• 2.2.3 OSM原始數(shù)據(jù)處理19-20
• 2.3 地理數(shù)據(jù)與網(wǎng)絡(luò)數(shù)據(jù)的轉(zhuǎn)換20-21
• 2.4 大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的表達與存儲21-25
• 2.4.1 RDF數(shù)據(jù)模型簡介21-23
• 2.4.2 RDF-3X數(shù)據(jù)庫存儲結(jié)構(gòu)23
• 2.4.3 道路網(wǎng)數(shù)據(jù)的存儲與查詢23-25
• 3、基于屬性信息的層次化網(wǎng)絡(luò)構(gòu)建25-30
• 3.1 基于屬性信息的地理實體構(gòu)建25-27
• 3.1.1 道路網(wǎng)的節(jié)點屬性25
• 3.1.2 城市道路網(wǎng)級別劃分25-26
• 3.1.3 道路網(wǎng)邊的屬性信息26-27
• 3.2 基于實體的重要路徑發(fā)現(xiàn)與賦權(quán)27-30
• 3.2.1 道路網(wǎng)重要路徑發(fā)現(xiàn)27-28
• 3.2.2 道路網(wǎng)重要路徑賦權(quán)28-30
• 4、層次化網(wǎng)絡(luò)下的最短路徑算法30-46
• 4.1 Reach、TNR和CH算法30-35
• 4.1.1 Bidirectional Dijkstra算法30
• 4.1.2 Reach算法30-32
• 4.1.3 CH算法32-33
• 4.1.4 TNR算法33-35
• 4.2 層次化網(wǎng)絡(luò)下最短路徑算法35-41
• 4.2.1 層次劃分36-39
• 4.2.2 輔助邊構(gòu)建39-41
• 4.2.3 節(jié)點級別排序的確定41
• 4.3 最短路徑近似算法41-43
• 4.3.1 樣本的選取42-43
• 4.3.2 近似最短路徑的求解43
• 4.4 空間復(fù)雜度和時間復(fù)雜度分析43-46
• 4.4.1 空間復(fù)雜度分析44
• 4.4.2 時間復(fù)雜度分析44-46
• 5、實驗46-53
• 5.1 實驗數(shù)據(jù)介紹46
• 5.2 數(shù)據(jù)預(yù)處理46-48
• 5.3 距離查詢效率48-50
• 5.4 路徑查詢效率50-51
• 5.5 空間消耗和預(yù)處理消耗51-53
• 6、總結(jié)與展望53-56
• 6.1 總結(jié)53
• 6.2 應(yīng)用前景53-54
• 6.3 下一步研究計劃54-56
• 致謝56-58
• 參考文獻58-63
• 攻讀學(xué)位期間的研究成果63

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 宋青;汪小帆;;最短路徑算法加速技術(shù)研究綜述[J];電子科技大學(xué)學(xué)報;2012年02期

，

本文編號：696845