本文關(guān)鍵詞：HTEDI算法的實(shí)現(xiàn)和改進(jìn)

  更多相關(guān)文章： 最短路徑 最小度的樹分解 最小填充的樹分解

【摘要】：點(diǎn)到點(diǎn)的最短路徑問題是復(fù)雜網(wǎng)絡(luò)和GIS等學(xué)科中的經(jīng)典問題,在實(shí)踐中得到廣泛應(yīng)用,如物流運(yùn)輸、車載導(dǎo)航、社交網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)等。雖然針對該問題提出過許多經(jīng)典算法,但是隨著網(wǎng)絡(luò)規(guī)模迅速擴(kuò)大,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越來越復(fù)雜,對現(xiàn)有的最短路徑算法提出新的挑戰(zhàn)。多核計(jì)算機(jī)的出現(xiàn),為最短路徑搜索算法的改進(jìn)提供新途徑。本文主要內(nèi)容如下:首先,對最短路徑的研究背景和意義、國內(nèi)外研究進(jìn)展進(jìn)行總結(jié),介紹了本文的研究內(nèi)容、組織結(jié)構(gòu)及技術(shù)路線。其次,對當(dāng)前點(diǎn)到點(diǎn)的最短路徑算法進(jìn)行分類總結(jié),包括精確最短路徑算法、近似最短路徑算法。精確最短路徑算法,如Dijkstra、BFS、SPFA、Bellman-Ford等,該類算法常應(yīng)用于精度要求較高的情形,如計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、數(shù)據(jù)庫查詢等;近似最短路徑算法,如A*、雙向算法、分層算法、ALT等,該類算法應(yīng)用在對精度要求不太高的情形,如機(jī)器人導(dǎo)航、地圖導(dǎo)航等。其次,對樹分解算法進(jìn)行分類總結(jié),主要包括兩類:基于消除序列的樹分解算法和基于割集的樹分解算法�；谙蛄械臉浞纸馑惴ㄖ饕邢覉D識(shí)別算法,如:最大基搜索泛(Maximum Cardinality Search algorithm)、字典廣度優(yōu)先搜索算法(Lexicographic Breadth First Search algorithm)等,基于貪心的三角化算法,如:基于最小度的樹分解算法(MinDegree)、基于最小填充的樹分解算法(MinFill)等,基于剪枝約束的算法等,該類算法主要特點(diǎn)是時(shí)間復(fù)雜度較低�；诟罴臉浞纸馑惴ㄖ饕谢诮M件分割策略的算法(The splitting into components strategy)、基于最小頂點(diǎn)割集的啟發(fā)式算法(The Minimum Separating Vertex Sets heuristic)等,該類算法的優(yōu)點(diǎn)是可以根據(jù)樹分解的上界作為啟發(fā),但是時(shí)間復(fù)雜度較高。然后,通過對HTEDI算法(由Fang Wei-Kleiner于2016年提出)的分析。據(jù)此對最短路徑查詢過程進(jìn)行改進(jìn),主要包括,將算法的查詢過程從雙向計(jì)算過程改為單向,使算法在有向圖中也是可靠解;將根節(jié)點(diǎn)的計(jì)算過程進(jìn)行特殊處理(見第五章),保留原算法時(shí)間和空間平衡的優(yōu)點(diǎn);根據(jù)樹分解父節(jié)點(diǎn)和子節(jié)點(diǎn)的特點(diǎn),加快最短路徑算法的查詢過程。在真實(shí)的道路網(wǎng)中進(jìn)行實(shí)證分析,證明改進(jìn)后的算法在有向有權(quán)圖上是可靠解,并且查詢速度得到有效改善。接著,考慮到樹分解方法的選擇可能會(huì)影響HTEDI算法的效率。第五章詳細(xì)對比MinFill的樹分解方法和MinDegree的樹分解方法,將MinFill的樹分解方法應(yīng)用于HTEDI算法,與采用MinDegree的HTEDI算法進(jìn)行對比,通過實(shí)驗(yàn)分析,證明采用MinFill比采用MinDegree方法在預(yù)處理部分的時(shí)間和空間上的結(jié)果都要好,同時(shí)最短路徑查詢計(jì)算速度得到提高。最后,本文給出了相關(guān)的結(jié)論,并對未來的工作進(jìn)行展望。
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 肖金聲;;關(guān)于最短路徑算法[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);1987年03期

2 馬東嶺;;城市公交網(wǎng)絡(luò)的最短路徑算法研究[J];科技信息;2008年26期

3 胡于杰;李響;;利用最短路徑算法確定地理網(wǎng)絡(luò)中心服務(wù)范圍[J];地理與地理信息科學(xué);2010年03期

4 鄭年波;陸鋒;李清泉;段瀅瀅;;顧及轉(zhuǎn)向延誤的時(shí)間依賴A~*最短路徑算法[J];測繪學(xué)報(bào);2010年05期

5 涂海麗;;最短路徑算法及其應(yīng)用探討[J];科技廣場;2011年09期

6 毛少武;張煥國;黃崇超;吳萬青;;改進(jìn)的K最短路徑算法在通信網(wǎng)絡(luò)中的應(yīng)用[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2013年06期

7 張效賢;最短路徑算法的應(yīng)用[J];甘肅高師學(xué)報(bào);1999年02期

8 馮曉輝;;交通網(wǎng)絡(luò)中的最短路徑算法探索[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2013年21期

9 竇桂琴;楊青;黃祖鋒;王雪萍;;一種基于城市應(yīng)急系統(tǒng)的最短路徑算法[J];廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

10 歐福軍;劉萍;涂亞平;吳海兵;;大規(guī)模網(wǎng)絡(luò)最短路徑算法的優(yōu)化及實(shí)現(xiàn)[J];海南大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年02期

中國重要會(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 陳志芳;基于最短路徑算法的高速路網(wǎng)建模與實(shí)證研究[D];合肥工業(yè)大學(xué);2016年

8 何亞琦;基于GPS軌跡的移動(dòng)端最短網(wǎng)絡(luò)距離推薦系統(tǒng)[D];湖南科技大學(xué);2016年

9 冀陸兵;HTEDI算法的實(shí)現(xiàn)和改進(jìn)[D];西南交通大學(xué);2017年

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

，

本文編號：1276792