本文關(guān)鍵詞：面向大圖的傳遞歸約問題研究　出處：《燕山大學(xué)》2016年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 有向無環(huán)圖 傳遞歸約 傳遞閉包 路徑分解

【摘要】：給定有向無環(huán)圖G,G的傳遞歸約是和G有相同傳遞閉包的最小唯一子圖。傳遞歸約是圖論中的經(jīng)典問題之一,并廣泛應(yīng)用于實(shí)際中簡化問題的求解,包括傳遞閉包、背包問題、可達(dá)性問題等。然而,現(xiàn)有傳遞歸約方法的計(jì)算代價(jià)高昂。隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和新型應(yīng)用的不斷涌現(xiàn),實(shí)際應(yīng)用中的圖規(guī)模越來越大,在機(jī)器內(nèi)存容量受限的情況下,已有的傳遞歸約算法因其較高的空間復(fù)雜度面臨無法使用的尷尬境地。本文從以下幾個(gè)方面對(duì)有向無環(huán)圖的傳遞歸約方法進(jìn)行研究,具體內(nèi)容如下。首先,提出自底向上的BUTR算法。該算法首先將G分解為k條路徑,以自底向上的方式處理每條路徑p。其特點(diǎn)體現(xiàn)在處理每條路徑p時(shí),可以利用p中頂點(diǎn)間的父子關(guān)系來避免對(duì)部分頂點(diǎn)和邊的重復(fù)訪問,并保證在處理完p的所有頂點(diǎn)后,所有涉及到的邊僅被訪問一次。當(dāng)處理完所有的k條路徑之后,即可得到傳遞歸約。BUTR時(shí)間與空間復(fù)雜度分別為O(km)和O(n),其中n、m分別為圖G中結(jié)點(diǎn)和邊的個(gè)數(shù)。其次,針對(duì)BUTR算法在實(shí)際應(yīng)用中路徑分解規(guī)模過大的問題,提出無需路徑分解的算法TDTR來避免BUTR算法存在的冗余計(jì)算問題。TDTR通過棧來緩存已處理結(jié)點(diǎn)并標(biāo)記其逆向傳遞閉包,從而盡可能早的利用結(jié)點(diǎn)間的父子關(guān)系來避免BUTR算法存在的冗余計(jì)算問題。算法TDTR時(shí)間與空間復(fù)雜度分別為O(wavgm)和O(n),wavg為為處理單個(gè)結(jié)點(diǎn)時(shí)平均訪問結(jié)點(diǎn)數(shù)目。最后,在26個(gè)不同規(guī)模的真實(shí)數(shù)據(jù)集上,通過實(shí)驗(yàn)從不同角度對(duì)算法的性能進(jìn)行深入比較和分析。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的高效性和擴(kuò)展性。
[Abstract]:In this paper , the paper presents the algorithm TDTR , which can be used to solve the problem of redundancy calculation of the BUTR algorithm . In this paper , the algorithm TDTR is used to solve the problem of redundancy calculation of the BUTR algorithm .

【學(xué)位授予單位】：燕山大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 陸正福,何英,楊鄧奇,王國棟;模歸約算法的數(shù)學(xué)基礎(chǔ)研究[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

2 葉恒舟;羅曉娟;牛秦洲;;基于歸約圖的Web服務(wù)自動(dòng)組合[J];桂林工學(xué)院學(xué)報(bào);2009年03期

3 謝宜暉;蘇運(yùn)霖;;關(guān)于Petri網(wǎng)歸約問題[J];暨南大學(xué)學(xué)報(bào)(自然科學(xué)與醫(yī)學(xué)版);1990年01期

4 王潔;p-t-歸約及sn-t-歸約的一些性質(zhì)[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);1986年03期

5 楊東屏;結(jié)構(gòu)多項(xiàng)式復(fù)雜性研究中使用的一些方法[J];數(shù)學(xué)進(jìn)展;1995年04期

6 李傳湘;字集的識(shí)別模型[J];數(shù)學(xué)物理學(xué)報(bào);1998年02期

7 韋元軍;;實(shí)函數(shù)的歸約性[J];貴州大學(xué)學(xué)報(bào)(自然科學(xué)版);1987年03期

8 ;[J];;年期

相關(guān)會(huì)議論文 前1條

1 林珠;邢延;;適用于時(shí)間序列分類的數(shù)據(jù)歸約方法[A];2009年中國智能自動(dòng)化會(huì)議論文集（第二分冊(cè)）[C];2009年

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

1 劉云霞;數(shù)據(jù)歸約的統(tǒng)計(jì)方法研究及應(yīng)用[D];廈門大學(xué);2007年

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

1 周世杰;面向大圖的傳遞歸約問題研究[D];燕山大學(xué);2016年

2 孫寅龍;X-DSP 64位定點(diǎn)ALU和歸約單元的設(shè)計(jì)優(yōu)化與驗(yàn)證[D];國防科學(xué)技術(shù)大學(xué);2014年

3 張闖;X-DSP64位定點(diǎn)運(yùn)算單元與向量歸約網(wǎng)絡(luò)的設(shè)計(jì)與實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2013年

，

本文編號(hào)：1379894