【摘要】：最短路徑查詢是圖領(lǐng)域中研究的一個重要課題,用于計算一個頂點到其他頂點的最短路徑,應(yīng)用非常的廣泛。主要特點是由起始頂點出發(fā),向外逐層遍歷,擴(kuò)展到目標(biāo)終點結(jié)束。經(jīng)典最短路徑查詢通常是定義在靜態(tài)圖中,發(fā)展至今已有很多成熟高效的求解算法。然而在當(dāng)今許多現(xiàn)實應(yīng)用中,圖模型往往具有時間特性,例如時間序列圖。經(jīng)典最短路徑查詢算法在面對此類圖模型時遇到了很大的挑戰(zhàn),往往不能給出滿足查詢條件的最優(yōu)解決方案。本文研究分析時間序列圖中的路徑查詢問題,針對其時間特性,提出了最優(yōu)路徑查詢算法。同時考慮到大數(shù)據(jù)環(huán)境下圖的規(guī)模將日益擴(kuò)大,因此對算法進(jìn)行了擴(kuò)展,提出了一種基于Hadoop的分布式查詢算法。首先,本文對時間序列圖的概念及特性進(jìn)行了描述,同時基于時間代價和費用代價的考慮,定義了五種“最優(yōu)”路徑:最早到達(dá)路徑、最晚出發(fā)路徑、最少用時路徑、最少中轉(zhuǎn)路徑、最小費用路徑,并且提出了時間序列圖的入邊表示法。其次,針對經(jīng)典最短路徑查詢算法的不足,本文提出了一種基于時間序列圖的最優(yōu)路徑查詢算法。算法采用基于條件約束的中途頂點盡早淘汰策略,使用反向搜索的方式,由目標(biāo)頂點向出發(fā)頂點反向逐級推進(jìn),有效的提高了查詢效率。同時,考慮到隨著信息技術(shù)的發(fā)展,圖的規(guī)模將日益擴(kuò)大,集中式的解決方案不能滿足大規(guī)模時間序列圖的查詢需求。因此,本文針對大數(shù)據(jù)環(huán)境下大規(guī)模時間序列圖的查詢,對最優(yōu)路徑查詢算法進(jìn)行了擴(kuò)展,采用MapReduce編程模型,提出了一種基于Hadoop的分布式計算方法。最后分別在集中式和分布式環(huán)境中進(jìn)行了實驗。實驗結(jié)果表明,本文提出的兩種最優(yōu)路徑查詢方法均具有較高的執(zhí)行效率和準(zhǔn)確性。
【圖文】：

12圖 3-1 時間序列圖示，對于任意的 i（1 < i ≤ k），將邊i e =的元素組合連接成五元組( i i i+v ,d ,v 0iw ，iw 為第 i 個頂點iv 的等待時要等待iw 時間，才能于時間id 出發(fā)。定義：對于任意的 i（1 < i ≤ k），路徑 P。同時定義： ( ) ( )k karrive P = d t，即路徑 P 的出發(fā)時間；d ura (P ) = arr

14圖 3-2 時間序列圖的入邊索引示意圖3.2 基于時間序列圖的最優(yōu)路徑查詢算法3.2.1 最優(yōu)路徑查詢算法時間序列圖的時間特性和費用特性決定了計算得到的路徑如果沒有滿足最優(yōu)路徑查詢的時間條件和費用條件，則選取的路徑是完全沒有意義的。因此，本節(jié)基于時間序列圖的相關(guān)概念，結(jié)合基于條件約束的中途頂點盡早淘汰策略，提出最優(yōu)路徑查詢算法 OPQA（Optimal Path Query Algorithm）。最優(yōu)路徑查詢算法包含兩個階段。第一個階段為反向搜索階段，，即執(zhí)行基于代價限制的反向
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【參考文獻(xiàn)】

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

1 邱勝海;王云霞;樊樹海;賈曉林;;云環(huán)境下圖數(shù)據(jù)庫建模技術(shù)及其應(yīng)用研究[J];計算機(jī)應(yīng)用研究;2016年03期

2 李桃陶;周斌;王忠振;;基于社交網(wǎng)絡(luò)的圖數(shù)據(jù)挖掘應(yīng)用研究[J];計算機(jī)技術(shù)與發(fā)展;2014年10期

3 劉貴松;解修蕊;黃海波;屈鴻;;基于最短路徑信任關(guān)系的推薦項目計算方法[J];電子科技大學(xué)學(xué)報;2014年02期

4 韓衛(wèi)國;彭偉;唐晉韜;;基于路標(biāo)的最短路徑長度快速估計算法[J];重慶理工大學(xué)學(xué)報(自然科學(xué));2013年07期

5 陳克寒;韓盼盼;吳健;;基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J];計算機(jī)學(xué)報;2013年02期

6 郝樹魁;;Hadoop HDFS和MapReduce架構(gòu)淺析[J];郵電設(shè)計技術(shù);2012年07期

7 王樹西;吳政學(xué);;改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J];計算機(jī)科學(xué);2012年05期

8 張倩倩;秦瑩瑩;;基于動態(tài)最短路徑策略的多QoS路由算法[J];軟件導(dǎo)刊;2011年06期

9 劉勇;李建中;高宏;;從圖數(shù)據(jù)庫中挖掘頻繁跳躍模式[J];軟件學(xué)報;2010年10期

10 張毅;張猛;梁艷春;;改進(jìn)的最短路徑算法在多點路由上的應(yīng)用[J];計算機(jī)科學(xué);2009年08期

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

1 宋青;大規(guī)模網(wǎng)絡(luò)最短路徑的分層優(yōu)化算法研究[D];上海交通大學(xué);2012年

2 吳增海;社交網(wǎng)絡(luò)模型的研究[D];中國科學(xué)技術(shù)大學(xué);2012年

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

1 馬建剛;最短路徑算法在組播路由和物流配送中的應(yīng)用研究[D];西安電子科技大學(xué);2007年

本文編號：2537305