【摘要】：最短路徑問題是圖論中較為經典也是相對基礎的問題,其經過了大半個世紀的研究,受到許多領域研究人員的關注,最短路徑算法的研究成果十分豐富。最短路徑算法廣泛運用在各種現實場景中,其中交通網中選取最優(yōu)出行路徑就是最短路徑算法的一項具體應用。隨著城市的發(fā)展,城市交通網的規(guī)模逐漸擴大,網絡節(jié)點數量龐大且網絡結構復雜多元,使得經典最短路徑算法無法使用,因此,應用于大規(guī)模網絡中最短路徑的優(yōu)化技術和優(yōu)化算法成為近幾年最短路徑算法研究的重點。在這些研究中,并行計算成為大規(guī)模網絡最短路徑算法的主要研究方向。近幾年,國內外學者針對大規(guī)模網絡和動態(tài)網絡提出了一系列最短路徑算法,其中部分算法使用了啟發(fā)式路徑搜索方式、并行計算方式或使用網絡分層模型進行最短路徑計算。本文在現有的研究成果中總結出相關經驗,綜合了并行計算思想和啟發(fā)式搜索方式,提出了一個適合于城市交通網任意節(jié)點間最短路徑計算的層次最短路徑算法。本算法主要由三個子算法組成,分別是大圖分解過程、PFloyd算法和SPS算法。由于最短路徑計算的時間復雜度與圖中節(jié)點個數相關,因此,在圖分解過程中,我們設計了一個兩層網絡模型,即將原始網絡分割為若干個子網,再將子網抽象為節(jié)點并構造二層網絡。當路徑查詢的起點與終點同屬于一個子圖時,本文設計了并行的任意節(jié)點間最短路徑算法PFloyd算法,該算法根據任意節(jié)點間最短路徑計算迭代公式與矩陣乘法運算公式之間的映射關系,將任意節(jié)點間最短路徑計算移植至MapReduce上,通過MapReduce的′?次矩陣迭代相乘,計算出最短路徑的權值矩陣和路徑矩陣,算法通過對權值矩陣和路徑矩陣的查詢得到所求的最短路徑。當路徑查詢的起點與終點屬于不同的子圖時,本文設計了一個跨子圖的路徑搜索算法SPS算法。SPS算法采用了啟發(fā)式的搜索模式以構建路徑,它定義了子圖間的距離計算方式,并將子圖間距離信息作為啟發(fā)式的引導信息,在當前訪問子圖的鄰接子圖中,遞歸選取若干個與當前子圖相近的子圖作為下一次訪問的子圖對象。SPS算法采用雙向搜索模式,前向搜索與后向搜索同步進行,使得前向搜索與后向搜索的對象快速逼近,從而實現搜索算法的加速。通過對參數的調整,可以提升路徑搜索的精確度,減少路徑搜索的時間。當路徑構建完成后,只需挑選出所有路徑中最短的那條即為SPS算法所求。文中選取美國舊金山港灣區(qū)交通網路徑數據作為本文實驗數據,對層次最短路徑算法進行實驗分析,驗證了算法的可用性。本文的層次最短路徑算法在層次網絡模型中進行,三個子算法共同配合,完成了算法在子圖層與二層網絡中的路徑搜索與路徑拼接。二層網絡中的路徑搜索采用雙向的啟發(fā)式路徑搜索模式,加快了算法的搜索效率。針對交通網路段的權值根據時間動態(tài)變化的問題,算法在圖分解過程中將原始網絡進行切分,使得路段權值以子圖為單位動態(tài)更新,減少了權值更新帶來的額外消耗。通過實驗結果,證明了本文算法在大規(guī)模交通網最短路徑計算中有良好表現。
【學位授予單位】：江西財經大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP301.6
【圖文】：

圖 1-1 本文組織架構一章為緒論。介紹了本文研究背景及研究意義，首先詳細介紹經典以及其改進方法；其次討論經典算法不適合處理大規(guī)模網絡的原因大規(guī)模網絡中最短路徑算法的國內外研究現狀，列舉出算法的研究介紹國內外在并行計算方面的研究成果；最后概括了本文的主要研文的結構安排。二章為預備知識分析。在提出本文算法前，將讀者需要了解的預備。首先介紹本算法中圖的存儲結構以及 HDFS 的基礎架構；其educe 計算模型，并使用它計算兩個二維矩陣相乘；最后介紹動態(tài)數以及動態(tài)數據獲取所用到的工具。三章為層次最短路徑算法設計。介紹了一個層次最短路徑算法，該子算法，分別是圖分解過程、PFloyd 算法和 SPS 算法。圖分解過進行切分、分層，并抽象得到二層網絡。根據路徑查詢的起點與終

和邊的數量龐大，存儲交通網數據直接關系到最短路徑算法的執(zhí)行效目前，常見的簡單圖存儲結構主要分組成，存儲圖中節(jié)點數據的一二維數組 二維 （n 為圖中節(jié)，以圖 2-1 中的無向圖為例（圖中 ，0 11 01 10 10 0Arcs

據分析的城市交通網最短路徑算法設計接矩陣存儲結構可以看出，鄰接矩陣存儲可以快速查找兩個節(jié)點之其最大的缺點是無關聯的節(jié)點也需要占用存儲空間，這會消耗大量]。表的存儲邏輯是將每個節(jié)點的鄰接節(jié)點串聯，并以單鏈表的形式-1 中無向圖，鄰接表的存儲結構如圖 2-2 所示。

【參考文獻】

相關期刊論文 前10條

1 李祥池;;基于ELK和Spark Streaming的日志分析系統(tǒng)設計與實現[J];電子科學技術;2015年06期

2 徐建閩;王鈺;林培群;;大數據環(huán)境下的動態(tài)最短路徑算法[J];華南理工大學學報(自然科學版);2015年10期

3 佘敦偉;蔡先華;;大型復雜網絡中最短路徑查詢的優(yōu)化方法[J];科技信息;2012年05期

4 李建江;崔健;王聃;嚴林;黃義雙;;MapReduce并行編程模型研究綜述[J];電子學報;2011年11期

5 唐晉韜;王挺;王戟;;適合復雜網絡分析的最短路徑近似算法[J];軟件學報;2011年10期

6 盧照;師軍;于海蛟;方昕;;城市路網的最短路徑并行求解[J];計算機技術與發(fā)展;2010年01期

7 李樹彬;高自友;林勇;吳建軍;李珂;許兆霞;丁青燕;;大規(guī)模交通網絡實時路徑搜索算法研究[J];交通運輸系統(tǒng)工程與信息;2009年05期

8 方義秋;楊曦;;基于滑動窗口的車輛計數和位置預測[J];微計算機信息;2008年18期

9 林瀾;閆春鋼;蔣昌俊;周向東;;動態(tài)網絡最短路問題的復雜性與近似算法[J];計算機學報;2007年04期

10 王景存;張曉彤;陳彬;陳和平;;一種基于Dijkstra算法的啟發(fā)式最優(yōu)路徑搜索算法[J];北京科技大學學報;2007年03期

相關碩士學位論文 前2條

1 楊琰;基于Petri網的城市交通網絡建模及最優(yōu)路徑算法研究[D];廣西師范學院;2013年

2 荊長林;基于分布式蟻群算法的城市路網動態(tài)最短路徑搜索研究與實現[D];北京交通大學;2012年

本文編號：2786791