本文關(guān)鍵詞：地圖服務系統(tǒng)設計及路徑查找算法研究

  更多相關(guān)文章： 地圖服務 路徑查找 Dijkstra算法 A*算法

【摘要】：在科技與經(jīng)濟日益交融，協(xié)調(diào)發(fā)展的現(xiàn)代社會，地圖服務技術(shù)的廣泛應用深刻的影響著我們每天接觸到的各個領域。小范圍包括人們的定位搜索，交通出行和道路導航等，大范圍包括國家的物流運輸，緊急救援和軍事行動等。作為地理信息系統(tǒng)（GIS）學科的一部分，隨著電子計算機技術(shù)、人工智能技術(shù)和制圖渲染技術(shù)等的飛速發(fā)展與進步，地圖服務技術(shù)也日趨發(fā)展成熟與完善。 地圖服務的主要功能是存儲、發(fā)布、組織和管理海量的空間數(shù)據(jù)，方便客戶端的在線查詢、檢索、分析和下載等，，使得各種實時實地的空間地理信息得以高效利用，滿足不同的現(xiàn)實需求。作為地圖服務系統(tǒng)的重要組成部分，因為不斷完善的圖論理論和數(shù)據(jù)結(jié)構(gòu)，路徑查找功能逐步發(fā)展成為地圖服務的一個重要應用，通過多種經(jīng)典路徑查找算法的相互結(jié)合，各種新的更切合實際的最短路徑查找算法不斷地被研究出來，特別是在算法步驟的易實現(xiàn)性、算法運算的時間和空間復雜度以及算法結(jié)果的應用范圍等方面各有進展。 總體來說，在地圖服務系統(tǒng)中，針對道路交通網(wǎng)絡的路徑查找問題有三種查找策略，分別是廣度優(yōu)先查找策略、深度優(yōu)先查找策略和啟發(fā)式查找策略。具體的幾種研究較成熟的經(jīng)典路徑查找算法主要包括Dijkstra算法和A*算法等。其中，Dijkstra算法是一種貪心算法，其基本原則是在進行每一步的結(jié)點計算時都是通過選擇一個局部的最優(yōu)解以期得到一個最終總體的最優(yōu)解。而A*算法是一種先通過最大可能加載計算已知信息，向最有希望結(jié)點為查找目標去查找的啟發(fā)式查找算法，這種查找策略在靜態(tài)路網(wǎng)中解決最短路問題有很好的效果。 本文對幾種經(jīng)典的路徑查找算法做了深入分析和研究，在分層路網(wǎng)的基礎上，考慮到實時實地的交通道路網(wǎng)絡中變量較多的情況，將道路屬性和路況信息等影響因子的不同權(quán)重值加載到路徑查找算法的計算公式中，通過算法計算得出不同的路徑優(yōu)先級，在每個計算結(jié)點處形成不同優(yōu)先級的路徑集。邊計算路徑優(yōu)先級，邊查找下一路徑，在減少路徑查找規(guī)模的同時，使得路徑查找計算的邏輯更加清晰。再結(jié)合項目背景和實際交通道路網(wǎng)絡的不同限制條件以及用戶不同的實際需求，計算出“空間距離”最短的選擇路徑，“時間距離”最短的選擇路徑和“經(jīng)濟距離”最短的選擇路徑等。最后對具體實驗數(shù)據(jù)進行對比分析，驗證本文設計的地圖服務系統(tǒng)中所涉及到的路徑計算方法具有一定的穩(wěn)定性、優(yōu)越性和高效性等。
【關(guān)鍵詞】：地圖服務 路徑查找 Dijkstra算法 A*算法
【學位授予單位】：河南大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：P208
【目錄】：

• 摘要4-6
• ABSTRACT6-11
• 第一章 緒論11-17
• 1.1 研究背景及意義11-12
• 1.2 國內(nèi)外研究現(xiàn)狀12-15
• 1.2.1 地圖服務的發(fā)展現(xiàn)狀與研究趨勢13-14
• 1.2.2 路徑查找算法的研究現(xiàn)狀14-15
• 1.3 主要內(nèi)容及組織結(jié)構(gòu)15-17
• 第二章 相關(guān)理論及技術(shù)介紹17-27
• 2.1 開發(fā)語言與開發(fā)環(huán)境17
• 2.2 地圖服務相關(guān)理論介紹17-20
• 2.2.1 地圖服務的概述18-19
• 2.2.2 空間地理信息的表達19-20
• 2.3 道路網(wǎng)絡拓撲結(jié)構(gòu)的構(gòu)建20-24
• 2.3.1 路網(wǎng)的分層21-22
• 2.3.2 路段的分割處理22-23
• 2.3.3 道路網(wǎng)絡拓撲結(jié)構(gòu)的構(gòu)建23-24
• 2.4 路徑查找算法的理論介紹24-25
• 2.5 本章小結(jié)25-27
• 第三章 系統(tǒng)設計27-45
• 3.1 系統(tǒng)開發(fā)與部署27-28
• 3.1.1 架構(gòu)設計27-28
• 3.1.2 系統(tǒng)開發(fā)部署的計算機配置28
• 3.2 系統(tǒng)功能描述28-33
• 3.2.1 單點坐標附近查找功能設計29-30
• 3.2.2 固定公交路線查找功能設計30-32
• 3.2.3 非固定交通路線查找功能設計32-33
• 3.3 類與接口33-38
• 3.3.1 分析網(wǎng)絡：NetworkManager 類33-34
• 3.3.2 限制搜索路徑：SysConstraint 類34-35
• 3.3.3 高級分析功能：網(wǎng)絡約束35
• 3.3.4 拓撲網(wǎng)絡結(jié)構(gòu)：Network、Node、Link 和 Path 類35-37
• 3.3.5 創(chuàng)建拓撲網(wǎng)絡：NetworkBuilder 類37
• 3.3.6 接口實現(xiàn)37-38
• 3.4 數(shù)據(jù)庫表設計38-41
• 3.4.1 空間地理信息的數(shù)據(jù)表設計38
• 3.4.2 空間地理分層網(wǎng)絡的數(shù)據(jù)表設計38-41
• 3.5 系統(tǒng)維護41-43
• 3.5.1 網(wǎng)絡拓撲數(shù)據(jù)維護41-42
• 3.5.2 數(shù)據(jù)庫維護42-43
• 3.6 本章小結(jié)43-45
• 第四章 算法研究與實驗驗證45-57
• 4.1 優(yōu)先級的定義45-49
• 4.1.1 路徑優(yōu)先級基類45-46
• 4.1.2 路徑優(yōu)先級分級計算流程46
• 4.1.3 路徑優(yōu)先級的計算方法46-49
• 4.2 以 DIJKSTRA 算法為基礎的算法改進實現(xiàn)49
• 4.3 以 A*算法為基礎的算法改進實現(xiàn)49-51
• 4.4 實驗內(nèi)容51-56
• 4.4.1 單點坐標附近查找功能實驗52-53
• 4.4.2 固定公交路線查找實驗53-55
• 4.4.3 非固定交通線路查找實驗55-56
• 4.5 本章小結(jié)56-57
• 第五章 總結(jié)57-59
• 參考文獻59-61
• 參加項目61-62
• 致謝62-63

【參考文獻】

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

1 張山山,邊馥苓;地理信息系統(tǒng)數(shù)據(jù)模型分析[J];測繪通報;2004年08期

2 潘農(nóng)菲;GIS的空間數(shù)據(jù)在關(guān)系型數(shù)據(jù)庫的實現(xiàn)理論及應用技術(shù)[J];計算機應用研究;2002年02期

3 樂陽,龔健雅;Dijkstra最短路徑算法的一種高效率實現(xiàn)[J];武漢測繪科技大學學報;1999年03期

4 肖樂斌,鐘耳順,劉紀遠,宋關(guān)福;GIS概念數(shù)據(jù)模型的研究[J];武漢大學學報(信息科學版);2001年05期

5 李德仁,朱欣焰,龔健雅;從數(shù)字地圖到空間信息網(wǎng)格——空間信息多級網(wǎng)格理論思考[J];武漢大學學報(信息科學版);2003年06期

6 艾廷華,成建國;對空間數(shù)據(jù)多尺度表達有關(guān)問題的思考[J];武漢大學學報(信息科學版);2005年05期

7 李德仁;苗前軍;邵振峰;;信息化測繪體系的定位與框架[J];武漢大學學報(信息科學版);2007年03期

8 唐文武,施曉東,朱大奎;GIS中使用改進的Dijkstra算法實現(xiàn)最短路徑的計算[J];中國圖象圖形學報;2000年12期

9 李楷;鐘耳順;曾志明;曹國峰;;基于分層網(wǎng)絡拓撲結(jié)構(gòu)的最優(yōu)路徑算法[J];中國圖象圖形學報;2006年07期

本文編號：910547