近年來,隨著大數(shù)據(jù)時(shí)代的到來以及在線社交網(wǎng)絡(luò)的興起,圖上的算法研究越來越受到人們的重視,因?yàn)闊o論是社交網(wǎng)絡(luò)還是交通道路網(wǎng)都可以被抽象為一張圖。迄今為止,許多優(yōu)秀的圖算法已經(jīng)被運(yùn)用到實(shí)際應(yīng)用中,并且給人們的生活帶來了極大的便利。但是現(xiàn)有的圖算法大都基于靜態(tài)圖并且只考慮單個(gè)屬性,而忽略了實(shí)際生活中的時(shí)序性以及多屬性特征。比如在路網(wǎng)中,不同時(shí)刻下兩點(diǎn)間是否存在汽車班次;又比如出行時(shí),除了考慮時(shí)間因素,人們往往還會(huì)考慮道路擁擠程度,汽車油耗等多個(gè)屬性因素。綜合以上情況,本文研究了基于時(shí)序圖的多約束路徑查詢問題,在傳統(tǒng)的路徑查詢算法基礎(chǔ)上進(jìn)行擴(kuò)展和創(chuàng)新,將時(shí)序信息和多屬性信息嵌入到對(duì)圖的建模和處理當(dāng)中,更加真實(shí)地模擬了實(shí)際情況,也為用戶提供了更加準(zhǔn)確和細(xì)致的結(jié)果。本文致力于在時(shí)序圖上找到滿足用戶提出的多個(gè)屬性上的約束的目標(biāo)路徑,這里的目標(biāo)路徑包括最快到達(dá)路徑以及運(yùn)行時(shí)間最短路徑。為了有效并且高效地解決上述問題,本文分別提出了基于Skyline路徑的算法以及基于雙向搜索的算法。它們充分考慮了圖上的時(shí)序特征和多屬性特征,并在查詢的過程中不斷剪枝和優(yōu)化,極大地減少了搜索空間�；赟kyline路徑的算... 

【文章來源】：蘇州大學(xué)江蘇省 211工程院校

【文章頁數(shù)】：65 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖３－１時(shí)序圖轉(zhuǎn)靜態(tài)圖實(shí)例??，，

Ｓ?爸?ＳＫＹ－Ｓ?，＊??｜?★?ＴＰ－Ｓ?Ｉ?３０?★?ＴＰ－Ｓ?／?ｖ??Ｉ０６?＇?Ｍ?■￣￣＾￣￣＊—一一Ｉ＇?｜?Ｘ??〇＞?〇）?２０?／?■??ｉ°４ｆ?ｉ?／??，丨ｒ??〇▼：?▼?▼?Ｔ?ＩＴ?〇（Ｗ?￣?￣?ｆ?－７：?－?－?■玄??Ｔ１?Ｔ２?Ｔ３?Ｔ４?Ｔ５?Ｔ１?Ｔ２?Ｔ３?Ｔ４?Ｔ５??Ｔｉｍｅ?ｉｎｔｅｒｖａｌ?（Ｏｐｓａｈｌ）?Ｔｉｍｅ?ｉｎｔｅｒｖａｌ?（Ｔａｓｍａｎｉａ）??圖５－１時(shí)間區(qū)間對(duì)查詢效率的影響??【Ｃ的影響】該組實(shí)驗(yàn)研宂的是屬性約束值對(duì)算法效率的影響。如圖５－２所示，??橫坐標(biāo)表示的是約束值的大小，縱坐標(biāo)表示的是平均響應(yīng)時(shí)間。首先，隨著約束值??變大，所有算法的查詢時(shí)間都變大了，這是因?yàn)榧s束值放寬，有更多的路徑滿足約?＇??束條件，增大了搜索空間，所以所有算法的響應(yīng)時(shí)間都增加了。其次，本文提出的??兩種算法在時(shí)間效率上都要明顯優(yōu)于基線算法，因?yàn)榛冢樱耄欤椋睿迓窂降乃惴▽r(shí)序??圖轉(zhuǎn)成了靜態(tài)圖，并且通過設(shè)計(jì)啟發(fā)函數(shù)值和剪枝策略來加速查詢，而基于雙向搜??索的方法通過正反向搜索以及相關(guān)支配剪枝策略也達(dá)到了加速查詢的效果。最后，??對(duì)比本文提出的兩種算法，基于Ｓｋｙｌｉｎｅ路徑算法的平均查詢效率要優(yōu)于基于雙向搜??索的，原因跟上組實(shí)驗(yàn)分析的類似。??３２??

?？?３０?＇?ｘ?ｉ：??§，０２?？?＾?Ｓ．?ｉｒ＾?ｘ??！?ｆ，?！２。??０１＾?’???▼?Ｖ?Ｕ，卜—看?？?？?°??１?ｆ－??－?＊?Ｈｔ－?????■?１?……二琴?羃?■一一…■…＾??６０?１２０?１８０?２４０?３００?６０?１２０?１８０?２４０?３００??Ｖａｌｕｅｓ?ｏｆ?ｃｏｎｓｔｒａｉｎｔｓ?（Ｏｐｓａｈｌ）?Ｖａｌｕｅｓ?ｏｆ?ｃｏｎｓｔｒａｉｎｔｓ?（Ｔａｓｍａｎｉａ）??圖５－２約束值對(duì)查詢效率的影響??【Ｘ的影響】該組實(shí)驗(yàn)研宄的是約束個(gè)數(shù)對(duì)算法效率的影響。如圖５－３所示，橫??坐標(biāo)表示的是約束的個(gè)數(shù)，縱坐標(biāo)表示的是平均響應(yīng)時(shí)間。首先，隨著約束個(gè)數(shù)的??增大，所有算法的查詢時(shí)間都變大了，原因分別為：對(duì)于基線方法來說，它需要分??別處理尺個(gè)約束，所以約束個(gè)數(shù)越多，花費(fèi)時(shí)間越長；對(duì)于基于Ｓｋｙｌｉｎｅ路徑的算法，??約束個(gè)數(shù)越多，它涉及的目標(biāo)方程值就越復(fù)雜，其次，兩種支配策略處理起來需要??判斷的情況也越多，所以時(shí)間消耗變大；對(duì)于基于雙向搜索的算法，約束個(gè)數(shù)越多，??它處理的屬性聚合函數(shù)就越復(fù)雜，同時(shí)，在正反向過程中剪枝的處理就變得較為復(fù)??雜，所以平均響應(yīng)時(shí)間也會(huì)增加。綜合以上分析，這種現(xiàn)象是符合預(yù)期的。其次，??本文提出的兩種算法在時(shí)間效率上都要明顯優(yōu)于基線算法，原因類似于上面兩組實(shí)??驗(yàn)。最后，本文提出的兩種算法相比，基于Ｓｋｙｌｉｎｅ路徑算法的平均查詢效率也要略??優(yōu)于基于雙向搜索的，原因也跟上面兩組實(shí)驗(yàn)分析相似。??３３??

【參考文獻(xiàn)】：
期刊論文
[1]關(guān)于最短路徑的SPFA快速算法[J]. 段凡丁.  西南交通大學(xué)學(xué)報(bào). 1994(02)



本文編號(hào)：3383592