本文關(guān)鍵詞：Hadoop平臺(tái)下基于路網(wǎng)加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法研究

  更多相關(guān)文章： 最短路徑算法 加權(quán)分層 關(guān)聯(lián)規(guī)則 Hadoop

【摘要】：傳統(tǒng)Dijkstra、Floyd、A*等算法適合于求解具有串行化、計(jì)算復(fù)雜度不高、存儲(chǔ)消耗不大等特性的最短路徑問題,在大規(guī)模復(fù)雜路網(wǎng)中的搜索效率不高。伴隨著大數(shù)據(jù)技術(shù)的熱潮,如何運(yùn)用分布式存儲(chǔ)、并行化計(jì)算和強(qiáng)大的分析處理能力實(shí)現(xiàn)快速、準(zhǔn)確地求解最短路徑問題,是交通領(lǐng)域?qū)W者關(guān)注和研究的重點(diǎn)之一。因此,本文基于Hadoop大數(shù)據(jù)平臺(tái)的HDFS模塊,分布式存儲(chǔ)海量浮動(dòng)車數(shù)據(jù);基于新一代YARN計(jì)算框架,并行化迭代求解最短路徑,減少算法的時(shí)間復(fù)雜度。在此基礎(chǔ)上,分析處理交通路網(wǎng)加權(quán)分層所需要的動(dòng)態(tài)、靜態(tài)道路屬性數(shù)據(jù),并提取關(guān)聯(lián)規(guī)則方法挖掘交叉口間關(guān)聯(lián)性的浮動(dòng)車出行路徑集。然后,采用層次分析法對道路等級(jí)、車道數(shù)量、路段長度、紅綠燈、收費(fèi)站、平均行程速度和通行次數(shù)等影響因素進(jìn)行權(quán)重加權(quán)計(jì)算,從而實(shí)現(xiàn)分層分區(qū),從空間拓?fù)浣Y(jié)構(gòu)上簡化路網(wǎng)搜索規(guī)模。接著,使用關(guān)聯(lián)規(guī)則方法挖掘海量浮動(dòng)車的出行路徑數(shù)據(jù),尋找分區(qū)內(nèi)各交叉口間的強(qiáng)關(guān)聯(lián)規(guī)則,減少搜索的節(jié)點(diǎn)數(shù)目。最后,搭建Hadoop集群實(shí)驗(yàn)平臺(tái),對比分析傳統(tǒng)A*算法、基于YARN并行化迭代計(jì)算模型的最短路徑算法、Hadoop平臺(tái)下基于加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法等的有效性能指標(biāo)。實(shí)驗(yàn)結(jié)果表明,該算法在搜索速度上具有明顯的優(yōu)勢,而且求解的最短路徑結(jié)果符合出行者的行駛習(xí)慣,滿足居民快捷出行的需求。
【關(guān)鍵詞】：最短路徑算法 加權(quán)分層 關(guān)聯(lián)規(guī)則 Hadoop
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：U491
【目錄】：

• 摘要5-6
• Abstract6-10
• 第一章 緒論10-18
• 1.1 研究背景和意義10
• 1.2 國內(nèi)外研究現(xiàn)狀分析10-14
• 1.2.1 國外研究現(xiàn)狀10-12
• 1.2.2 國內(nèi)研究現(xiàn)狀12-14
• 1.2.3 研究現(xiàn)狀分析總結(jié)14
• 1.3 研究內(nèi)容14-15
• 1.4 技術(shù)路線與章節(jié)安排15-17
• 1.4.1 技術(shù)路線15-16
• 1.4.2 章節(jié)安排16-17
• 1.5 本章小結(jié)17-18
• 第二章 交通路網(wǎng)最短路徑算法研究18-26
• 2.1 最短路徑概述18-19
• 2.2 最短路徑算法分類體系19-21
• 2.2.1 問題類型19-20
• 2.2.2 路網(wǎng)特性20-21
• 2.2.3 求解技術(shù)21
• 2.3 交通路網(wǎng)常用最短路徑算法分析21-25
• 2.3.1 Dijkstra算法22
• 2.3.2 Floyd算法22-23
• 2.3.3 A*算法23-25
• 2.4 本章小結(jié)25-26
• 第三章 基于Hadoop大數(shù)據(jù)平臺(tái)的最短路徑算法研究26-38
• 3.1 交通大數(shù)據(jù)26
• 3.2 交通數(shù)據(jù)挖掘技術(shù)26-28
• 3.2.1 數(shù)據(jù)挖掘定義26-27
• 3.2.2 交通數(shù)據(jù)挖掘算法27
• 3.2.3 交通數(shù)據(jù)挖掘技術(shù)流程27-28
• 3.3 Hadoop平臺(tái)28-35
• 3.3.1 MapReduce29-33
• 3.3.2 HDFS33-34
• 3.3.3 YARN34-35
• 3.4 基于YARN的最短路徑算法設(shè)計(jì)35-37
• 3.5 本章小結(jié)37-38
• 第四章 基于加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法研究38-60
• 4.1 交通路網(wǎng)概述38
• 4.2 交通路網(wǎng)分層策略38-42
• 4.2.1 交通路網(wǎng)分層模型描述38-41
• 4.2.2 交通路網(wǎng)分層原則41
• 4.2.3 交通路網(wǎng)分層數(shù)量41-42
• 4.3 交通路網(wǎng)加權(quán)分層42-52
• 4.3.1 層次分析法概述42-45
• 4.3.2 交通路網(wǎng)權(quán)重確定45-48
• 4.3.3 交通路網(wǎng)分層分區(qū)48-52
• 4.4 分區(qū)交叉口間關(guān)聯(lián)規(guī)則挖掘52-57
• 4.4.1 關(guān)聯(lián)規(guī)則概述52-53
• 4.4.2 交叉口間關(guān)聯(lián)規(guī)則挖掘模型53-57
• 4.5 基于加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法設(shè)計(jì)57-58
• 4.6 本章小結(jié)58-60
• 第五章 最短路徑快速搜索算法驗(yàn)證與具體應(yīng)用60-74
• 5.1 Hadoop集群實(shí)驗(yàn)平臺(tái)搭建60-63
• 5.1.1 安裝Ubuntu / SSH60
• 5.1.2 安裝Java運(yùn)行環(huán)境60-61
• 5.1.3 安裝Hadoop平臺(tái)61
• 5.1.4 Hadoop集群部署61-63
• 5.2 最短路徑搜索算法的驗(yàn)證63-71
• 5.2.1 算法評(píng)價(jià)指標(biāo)63-64
• 5.2.2 算法測試與分析64-70
• 5.2.3 算法有效性能對比總結(jié)70-71
• 5.3 最短路徑快速搜索算法的具體應(yīng)用71-73
• 5.4 本章小結(jié)73-74
• 結(jié)論與展望74-76
• 參考文獻(xiàn)76-81
• 攻讀碩士學(xué)位期間取得的研究成果81-82
• 致謝82-83
• 附件83

【相似文獻(xiàn)】

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

1 任剛;張永;周竹萍;;交通建模中的最短路徑算法分析與測試[J];中國科技論文在線;2009年10期

2 康太平;張曉剛;王宗峰;何尚錄;;基于k短路徑算法的多目標(biāo)最短路徑算法[J];常州工學(xué)院學(xué)報(bào);2011年Z1期

3 王蘇男，，宋偉，姜文生;最短路徑算法的比較[J];系統(tǒng)工程與電子技術(shù);1994年05期

4 伍貝妮;;兩種分級(jí)網(wǎng)絡(luò)最短路徑算法(一)[J];江蘇航空;2000年04期

5 伍貝妮;;兩種分級(jí)網(wǎng)絡(luò)最短路徑算法(二)[J];江蘇航空;2001年01期

6 余為波;吳曉光;王濤;陳立;周巍;;基于最短路徑算法的艦船通道逃逸路線研究[J];中國艦船研究;2008年02期

7 楊爭;;基于分區(qū)域最短路徑算法的警力調(diào)配系統(tǒng)[J];重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年06期

8 周培德;多面體面上任意兩點(diǎn)間最短路徑算法[J];北京理工大學(xué)學(xué)報(bào);2005年04期

9 楊天石;劉曉東;于小平;;城市道路最短路徑算法的研究[J];長春工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年02期

10 王昊;;一種電子地圖最短路徑算法研究[J];硅谷;2009年05期

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

1 王闖;董志江;;最短路徑算法[A];吉林省測繪學(xué)會(huì)2008年學(xué)術(shù)年會(huì)論文集（下）[C];2008年

2 唐小勇;程琳;徐上;;考慮轉(zhuǎn)向延誤最短路徑算法及實(shí)現(xiàn)[A];2007第三屆中國智能交通年會(huì)論文集[C];2007年

3 陳再春;張?jiān)魄?潘伯鳴;;最短路徑算法在公交查詢中的實(shí)現(xiàn)[A];首屆長三角科技論壇數(shù)字區(qū)域建設(shè)與地理空間技術(shù)論壇優(yōu)秀論文集[C];2004年

4 羅飛;魏開平;萬潤澤;;復(fù)雜網(wǎng)絡(luò)中最短路徑算法的研究及應(yīng)用[A];2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

5 王明福;彭群生;;基于編碼圖的求解最短路徑算法[A];中國計(jì)算機(jī)圖形學(xué)進(jìn)展2008--第七屆中國計(jì)算機(jī)圖形學(xué)大會(huì)論文集[C];2008年

6 孫紹河;朱瑞艷;;GIS中最短路徑算法的研究[A];第二屆“測繪科學(xué)前沿技術(shù)論壇”論文精選[C];2010年

7 張惠謙;;電信規(guī)劃最短路徑算法的Excel宏實(shí)現(xiàn)[A];中國通信學(xué)會(huì)信息通信網(wǎng)絡(luò)技術(shù)委員會(huì)2005年年會(huì)論文集[C];2005年

8 王冬;張麗果;杜慧敏;韓俊剛;;基于R-Torus結(jié)構(gòu)和最短路徑算法的NoC建模[A];全國第19屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（上冊）[C];2008年

9 馮盼盼;藺宏偉;于金輝;;投影法生成網(wǎng)格上的路徑[A];第六屆全國幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集[C];2013年

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

1 廖遠(yuǎn);一對一最短路徑算法研究及車載導(dǎo)航系統(tǒng)設(shè)計(jì)[D];南昌大學(xué);2012年

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

1 呂志超;面向資源優(yōu)化配置的集群航天器網(wǎng)絡(luò)拓?fù)涔芾硌芯縖D];哈爾濱工業(yè)大學(xué);2015年

2 湯博蔚;基于云計(jì)算的智能交通系統(tǒng)[D];南京郵電大學(xué);2015年

3 尹伊伊;基于A*算法的多目標(biāo)和約束條件下的k優(yōu)換乘方案研究[D];中國鐵道科學(xué)研究院;2015年

4 羅麗虹;考慮轉(zhuǎn)向限制的路網(wǎng)中最短路徑算法研究[D];清華大學(xué);2015年

5 郭東;基于Virtools的煤礦井下逃生系統(tǒng)的研究[D];太原理工大學(xué);2016年

6 吳友寶;Hadoop平臺(tái)下基于路網(wǎng)加權(quán)分層和關(guān)聯(lián)規(guī)則的最短路徑算法研究[D];華南理工大學(xué);2016年

7 鄧禮禮;求圖中受限制的所有最短路徑算法的分析與研究[D];華東師范大學(xué);2009年

8 楊蔓;最短路徑算法在煤礦安全分區(qū)分析中的應(yīng)用研究[D];西安科技大學(xué);2009年

9 張志敏;手機(jī)導(dǎo)航系統(tǒng)中最短路徑算法的優(yōu)化與實(shí)現(xiàn)[D];西北大學(xué);2011年

10 王世明;典型城市路網(wǎng)中最短路徑算法研究及實(shí)現(xiàn)[D];山東大學(xué);2012年

本文編號(hào)：670310