發(fā)布時間：2017-09-02 18:23

  本文關(guān)鍵詞：基于GIS的大規(guī)模數(shù)據(jù)下K優(yōu)路徑規(guī)劃算法的研究與實現(xiàn)

  更多相關(guān)文章： Kth路徑 Dijkstra算法 有利度 大規(guī)模數(shù)據(jù) 地圖緩沖

【摘要】：路徑規(guī)劃問題是地理信息系統(tǒng)(GIS)研究領(lǐng)域中的關(guān)鍵內(nèi)容之一,最短路徑的尋找更是熱點問題。在數(shù)據(jù)量較大時,傳統(tǒng)前K條最短路徑算法效率較低,且不能解決某些實際需求下規(guī)劃K條差異較大的路徑問題。以Dijkstra算法為預(yù)處理,為有向圖的節(jié)點引入有利度的概念,通過對路徑結(jié)果重復(fù)度的檢測以及改變有利度引起圖的變化,循環(huán)使用A*算法尋找當(dāng)前圖中的最佳路徑,從而實現(xiàn)了Kth條差異路徑的規(guī)劃。使用的A*算法時間復(fù)雜度較低,所以與同類算法相比,效率較高,得到的Kth條路徑結(jié)果在滿足一定重復(fù)度要求的同時長度也較為合理。同時針對大規(guī)模數(shù)據(jù)量下多次路徑規(guī)劃下路段拓?fù)渎窂揭?guī)劃系統(tǒng)的效率低下的問題,提出地圖緩沖算法,優(yōu)化了路段拓?fù)?提升路徑規(guī)劃系統(tǒng)總體效率。
【關(guān)鍵詞】：Kth路徑 Dijkstra算法 有利度 大規(guī)模數(shù)據(jù) 地圖緩沖
【學(xué)位授予單位】：北京理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：P208;TP301.6
【目錄】：

• 摘要6-7
• Abstract7-10
• 第1章 緒論10-14
• 1.1 研究背景及意義10-11
• 1.2 研究現(xiàn)狀及趨勢11-12
• 1.3 本文研究內(nèi)容12-13
• 1.4 論文組織結(jié)構(gòu)13
• 1.5 本章小結(jié)13-14
• 第2章 K則路徑規(guī)劃算法概述14-25
• 2.1 KSP問題14-15
• 2.2 理論嚴(yán)密KSP算法15-21
• 2.2.1 偏離路徑算法15-19
• 2.2.2 候選刪除邊算法19-20
• 2.2.3 標(biāo)號算法20-21
• 2.3 有損KSP算法21-24
• 2.3.1 改進(jìn)遺傳算法22
• 2.3.2 混合蛙跳算法22-23
• 2.3.3 雙向搜索算法23-24
• 2.4 本章小結(jié)24-25
• 第3章 大規(guī)模數(shù)據(jù)下滿足重復(fù)度要求的K優(yōu)路徑規(guī)劃算法25-33
• 3.1 基于Dijkstra的KSP算法的優(yōu)化分析25-28
• 3.2 基于Dijkstra的KOP算法28-32
• 3.2.1 問題定義28-29
• 3.2.2 KOP算法29-30
• 3.2.3 參數(shù)控制30-31
• 3.2.4 算法分析31-32
• 3.3 本章小結(jié)32-33
• 第4章 基于GIS的路段拓?fù)溲芯颗c優(yōu)化33-43
• 4.1 基于GIS的路段拓?fù)?/span>33
• 4.2 限制拓?fù)鋮^(qū)域的選取33-34
• 4.3 路段的分割處理34-36
• 4.4 野外區(qū)域的路段拓?fù)?/span>36-38
• 4.4.1 基于A*的野的區(qū)域拓?fù)?/span>36-37
• 4.4.2 基于A*的野的區(qū)域拓?fù)洳襟E37-38
• 4.4.3 算法分析38
• 4.5 基于拓?fù)湫畔?fù)用的地圖緩沖算法38-42
• 4.5.1 地圖緩沖結(jié)構(gòu)定義38-39
• 4.5.2 地圖緩沖區(qū)域的確定39-40
• 4.5.3 地圖緩沖替換策略40-41
• 4.5.4 地圖緩沖調(diào)度算法41-42
• 4.6 本章小結(jié)42-43
• 第5章 實現(xiàn)設(shè)計及分析43-48
• 5.1 KOP算法對比實驗43-46
• 5.1.1 KOP算法效率實驗44
• 5.1.2 KOP算法數(shù)據(jù)規(guī)模實驗44-45
• 5.1.3 KOP算法道路質(zhì)量實驗45-46
• 5.2 地圖緩沖算法對比實驗46-47
• 5.3 本章小結(jié)47-48
• 第6章 結(jié)論48-49
• 參考文獻(xiàn)49-51
• 攻讀學(xué)位期間發(fā)表論文與研究成果清單51-52
• 致謝52

【相似文獻(xiàn)】

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

1 代紅兵;;適合于大規(guī)模數(shù)據(jù)快速存取的文件系統(tǒng)設(shè)計[J];中國科學(xué)院大學(xué)學(xué)報;1993年04期

2 ;[J];;年期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 徐健;陳光喜;;一種基于優(yōu)化處理較大規(guī)模數(shù)據(jù)的支持向量分類機(jī)[A];第八屆中國青年運(yùn)籌信息管理學(xué)者大會論文集[C];2006年

中國重要報紙全文數(shù)據(jù)庫 前2條

1 王麗;為大規(guī)模數(shù)據(jù)中心建設(shè)保駕護(hù)航[N];中國經(jīng)營報;2005年

2 ;戴爾務(wù)實推動云計算發(fā)展[N];網(wǎng)絡(luò)世界;2010年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 金冉;面向大規(guī)模數(shù)據(jù)的聚類算法研究及應(yīng)用[D];東華大學(xué);2015年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前8條

1 馬翠云;基于HBase的大規(guī)模數(shù)據(jù)存儲解決方案的設(shè)計和實現(xiàn)[D];山東大學(xué);2015年

2 周釗澤;面向大規(guī)模數(shù)據(jù)的局部在線學(xué)習(xí)[D];中山大學(xué);2015年

3 田大鑫;基于GIS的大規(guī)模數(shù)據(jù)下K優(yōu)路徑規(guī)劃算法的研究與實現(xiàn)[D];北京理工大學(xué);2016年

4 劉偉;面向大規(guī)模數(shù)據(jù)的高效LTR調(diào)研系統(tǒng)設(shè)計與實現(xiàn)[D];南京大學(xué);2015年

5 錢彥江;大規(guī)模數(shù)據(jù)聚類技術(shù)研究與實現(xiàn)[D];電子科技大學(xué);2009年

6 張新銘;金融應(yīng)用中大規(guī)模數(shù)據(jù)處理的性能優(yōu)化[D];浙江大學(xué);2007年

7 蔡偃武;面向大規(guī)模數(shù)據(jù)的在線新事件檢測[D];華東理工大學(xué);2014年

8 劉作志;應(yīng)用于大規(guī)模數(shù)據(jù)的極端學(xué)習(xí)機(jī)研究[D];西北大學(xué);2013年

，

本文編號：780157