發(fā)布時間：2021-12-01 17:33

　　現(xiàn)實生活中的很多應(yīng)用可以抽象為圖里面的問題,比如基因網(wǎng)絡(luò)中的疾病進(jìn)展跟蹤,可以抽象為圖里面的路徑查詢問題;城市建設(shè)的規(guī)劃,可以抽象為圖里面的k個最近鄰節(jié)點對查詢問題;蛋白質(zhì)交互網(wǎng)絡(luò)的分析比較,可以抽象為圖匹配問題等等。本文的研究主要涉及前兩個問題,即路徑查詢和k個最近鄰節(jié)點對的查詢�，F(xiàn)有的路徑查詢和k個最近鄰節(jié)點對查詢的工作中,主要存在以下兩個問題:（1）現(xiàn)有的研究大多數(shù)是基于靜態(tài)圖,也有一些研究涉及到動態(tài)圖上的路徑查詢問題,但是目前還沒有動態(tài)圖上的k個最近鄰節(jié)點對的相關(guān)研究;（2）現(xiàn)有的研究沒有考慮圖的邊上可能會有屬性信息,也沒有考慮用戶在進(jìn)行查詢的時候會對時間以及邊上的屬性有特定的需求。本文主要考慮了以上這兩點,從而提出了模型來貼切地描述現(xiàn)實生活中的網(wǎng)絡(luò),也提出了查詢方法來更好地滿足用戶的查詢需求。本文的主要貢獻(xiàn)如下:（1）提出了屬性時序圖的概念,并在屬性時序圖上提出了多約束下的最早到達(dá)路徑、最晚出發(fā)路徑以及多約束下的k個最近鄰節(jié)點對的查詢問題;（2）提出了一組近似算法,稱為兩次掃描算法。第一次掃描中定義了一個時序目標(biāo)函數(shù),它由多個約束和不斷變化的屬性值組成,指示時序路徑是否可行。... 

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

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

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

【部分圖文】：

圖１－１多屬性時序圖??

路徑及々個最近鄰節(jié)點對問題研究?第三章多約朿下的時序路徑??少。??１????１??２０「－■?＿＿■?＇?—??????■Ｉｑｌａ－ｅａ?■Ｉｑｌａ－ｅａ??■Ｉｔｓａ－ｅａ?＾Ｈｔｓａ－ｅａ??一?０．８?Ｉ?ＩｂＬＡ－ＬＤ?１５?？?Ｉ?ＩｂＬＡ－ＬＤ??念?Ｉ?Ｉｔｓａ－ｌｄ?象?１?Ｉｔｓａ－ｌｄ??ｉ?ｌｏ?ｌ?｜??＂：？ＬｅｓＪ?ｌＵ＼ｍｉ??Ｅｌｅｃ?Ｏｐｅｎｆｌｉｇｈｔｓ?Ｅｎｒｏｎ?Ａｒｘｉｖ??數(shù)據(jù)集?數(shù)據(jù)集??圖３－２平均執(zhí)行時間??分析：實驗結(jié)果說明，兩次掃描算法首先在第一次掃描過程中采用時序目標(biāo)函??數(shù)來研究屬性時序圖中是否存在可行的時序路徑，對于多約束下的最早到達(dá)路徑??（多約束下的最晚出發(fā)路徑）而言，如果起點（終點）的最小目標(biāo)函數(shù)值大于１，那??么表明該屬性時序圖中從起點到終點＋存在一條可行的時序路徑，因此就不需要再??進(jìn)行第二次的掃描；如果起點（終點）的最小目標(biāo)函數(shù)值小于等于１，則表明圖中存??在可行的時序路徑，因此接下來進(jìn)行第二次掃描，并且利用一次掃描得到的目標(biāo)函??數(shù)值以及時刻信息進(jìn)行預(yù)判，從而加速第二次掃描搜索的速度。對于基礎(chǔ)算法而言，??需要依次搜索滿足單個屬性上約束的時序路徑，如果在所有屬性的約束下查找到的??路徑都－致，那么才能返回一條路徑，否則，就找不到滿足多個約束的路徑。因此，??基礎(chǔ)算法的查詢速度相對較慢。此外，數(shù)據(jù)集Ｅｌｅｃ和Ｏｐｅｎｆｌｉｇｈｔｓ的節(jié)點數(shù)，時序邊數(shù)??遠(yuǎn)小于數(shù)據(jù)集Ｅｎｒｏｎ和Ａｒｘｉｖ的節(jié)點數(shù)和時序邊數(shù)，即前兩個數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)較為簡??單，包含的時序邊數(shù)較少，因此，算法掃描完全部的時序邊花費(fèi)的時間較

果。??８?丨１????１?１?８?－?－?－?■???????■Ｈｂｌａ－ｅａ?＾Ｈｂｌａ－ｅａ??■Ｉｔｓａ－ｅａ?＾Ｈｔｓａ－ｅａ??＿?６?■?１?Ｉｂｌａ－ｌｄ?Ｊ?＿?６?■?Ｉ?Ｉｂｌａ－ｌｄ??毅?１?Ｉｔｓａ－ｌｄ?ｂｓ?——＇?＾?Ｉ?Ｉｔｓａ－ｌｄ??Ｓ?４?■?■?＿?運(yùn)?４?？??〇?￣＾￣—?＾Ｊ—￣?〇?￣＾￣—?＾——￣??Ｅｌｅｃ?Ｏｐｅｎｆｌｉｇｈｔｓ?Ｅｎｒｏｎ?Ａｒｘｉｖ??數(shù)據(jù)集?數(shù)據(jù)集??圖３－３平均路徑數(shù)量??分析：實驗結(jié)果說明，兩次掃描算法能比基礎(chǔ)算法找到更多的時序路徑。主要??原因在于，兩次掃描算法把多個屬性以及這些屬性上的約束做聚合，首先進(jìn)行一次??掃描來對時序圖中是否存在可行路徑進(jìn)行判斷，然后接著第二次掃描來查找滿足約??束的目標(biāo)路徑�；A(chǔ)算法分別研究每個屬性上的約束，對于每個屬性，基礎(chǔ)算法都??要對時序圖進(jìn)行一次掃描，只有當(dāng)找到的多條路徑一致時，才能返回結(jié)果；否則，??基礎(chǔ)算法就找到不到路徑。然而，如果存在可行路徑，那么兩次掃描算法總是可以??返回可行的時序路徑。??３．５?本章小結(jié)??本小節(jié)在屬性時序圖中提出了一種新型的具有多約束的時序路徑的查找模型，??它是許多基于動態(tài)圖的應(yīng)用的基矗然后，本小節(jié)提出了一種新穎的時序目標(biāo)函數(shù)??來動態(tài)地研究時序路徑是否滿足相應(yīng)的約束。最后，本小節(jié)提出一組兩次掃描算法，??采用兩次掃描來尋找ＴＰＭＣ。此外，在４個真實動態(tài)數(shù)據(jù)集上進(jìn)行的實驗證明了本章??提出的兩次掃描算法的有效性和高效性。??２６??

【參考文獻(xiàn)】：
期刊論文
[1]動態(tài)圖數(shù)據(jù)上查詢與挖掘算法的研究綜述[J]. 楊雅君,高宏,李建中.  智能計算機(jī)與應(yīng)用. 2013(04)



本文編號：3526766