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

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

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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李祥池;;基于ELK和Spark Streaming的日志分析系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J];電子科學(xué)技術(shù);2015年06期

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

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

4 李建江;崔健;王聃;嚴(yán)林;黃義雙;;MapReduce并行編程模型研究綜述[J];電子學(xué)報(bào);2011年11期

5 唐晉韜;王挺;王戟;;適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J];軟件學(xué)報(bào);2011年10期

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

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

8 方義秋;楊曦;;基于滑動(dòng)窗口的車輛計(jì)數(shù)和位置預(yù)測(cè)[J];微計(jì)算機(jī)信息;2008年18期

9 林瀾;閆春鋼;蔣昌俊;周向東;;動(dòng)態(tài)網(wǎng)絡(luò)最短路問題的復(fù)雜性與近似算法[J];計(jì)算機(jī)學(xué)報(bào);2007年04期

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

相關(guān)碩士學(xué)位論文 前2條

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

2 荊長(zhǎng)林;基于分布式蟻群算法的城市路網(wǎng)動(dòng)態(tài)最短路徑搜索研究與實(shí)現(xiàn)[D];北京交通大學(xué);2012年

本文編號(hào)：2786791