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

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

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

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

9 李楷;鐘耳順;曾志明;曹國(guó)峰;;基于分層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最優(yōu)路徑算法[J];中國(guó)圖象圖形學(xué)報(bào);2006年07期

本文編號(hào)：910547