基于設(shè)置復(fù)合位置的傳遞閉包算法-論文.pdf

《基于設(shè)置復(fù)合位置的傳遞閉包算法-論文.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第31卷第3期蘇州科技學(xué)院學(xué)報(自然科學(xué)版)Vo1．31No．3Q生旦jouma1。fSuzh0uUniversity0fScie。dTeeho10gy(Natua1Science)Sep．2014基于設(shè)置復(fù)合位置的傳遞閉包算法汪小燕(安徽業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032)摘要：二元關(guān)系的傳遞閉包根據(jù)定義有時不好計算，文中提出一種通過設(shè)置二元關(guān)系中序偶的復(fù)合位置．對被刪減的二元關(guān)系按照序偶的復(fù)合位置，進行增量式復(fù)合來計算傳遞閉包的新算法，利用該算法可以較快地實現(xiàn)傳遞閉包的求解。關(guān)鍵詞：二元關(guān)系；傳遞閉包；恒等關(guān)系；復(fù)

2、合位置中圖分類號：O158文獻標識碼：A文章編號：1672—0687(2014)03—0043—03關(guān)系的傳遞閉包運算是近年來學(xué)者們研究的熱點，傳遞閉包在圖論、數(shù)據(jù)庫、編譯原理、計算機形式語言中都有重要的應(yīng)用。關(guān)系的傳遞閉包一般根據(jù)定義來計算，需要進行多次的集合復(fù)合運算。運算量大，特別是當尺中的序偶較多時，計算起來不僅麻煩，而且容易出現(xiàn)錯誤。1962年Warshall提出了計算傳遞閉包的有效算法【l_，Warshall算法比較簡單，而且也容易在計算機中實現(xiàn)，但該算法執(zhí)行所用時間較多。近年來，也有不少學(xué)者提出傳遞閉包的改進算法，文獻『2

3、—51減少了關(guān)系復(fù)合的次數(shù)，從而簡化了原有傳遞閉包的計算。文獻[6—7】提出利用關(guān)系矩陣求解傳遞閉包，也簡化了傳遞閉包的計算。文獻『8]提出如果關(guān)系中包含，>這一類的序偶，在計算傳遞閉包時，可以先不考慮，>這一類的序偶，在二元關(guān)系中刪除這些序偶后，對被刪減二元關(guān)系進行增量式復(fù)合計算，一次復(fù)合完畢，將復(fù)合計算的結(jié)果、原有的，>類序偶和新產(chǎn)生的，>類序偶合并在一起就可以計算出傳遞閉包。這種傳遞閉包的計算方法減少了，>這一類序偶的復(fù)合運算，并且只需要集合的一次復(fù)合運算。為了更進一步降低被刪減二元關(guān)系和其自身增量式復(fù)合計算量，采取設(shè)置二元關(guān)系

4、中序偶的復(fù)合位置，使得被刪減二元關(guān)系中的每個序偶都從自己的復(fù)合位置開始復(fù)合，不需要每個序偶都從被刪減二元關(guān)系的第一個序偶開始尋找它們的復(fù)合元素，使用新的傳遞閉包算法可以節(jié)省復(fù)合計算時間，并且保留了文獻中傳遞閉包算法的優(yōu)越性。1相關(guān)理論定義1t1R為集合A上的二元關(guān)系，對于任意a，b，c∈A，當<口，6>∈尺且<6，c>∈R時，有<0，c>∈R，稱R為A上的傳遞關(guān)系，或者說R在A上具有傳遞性。定義2t]設(shè)尺是集合上的二元關(guān)系，在R中添加最少的序偶集合尺，使得Ru具有傳遞性，則t(R)=尺UR是尺的傳遞閉包。如果關(guān)系本身具有傳遞性質(zhì)，則t

5、(R)。定義3t】設(shè)R是集合A上的二元關(guān)系，對于任意∈A，，>∈R，且對于任意，Y∈A，如果≠y，則，y>簪R，則尺稱為集合A中的恒等關(guān)系，記作，4。定義4閻設(shè)R是集合A上的二元關(guān)系，若={，x>lx∈A且，>∈R}，則稱為尺中的恒等關(guān)系的集合【收稿日期】2013—09—11[基金項目】計算機軟件新技術(shù)國家重點實驗室開放課題基金資助項目(KFKT2010B02)；安徽省高校自然科學(xué)基金資助項目(KJ2012ZO24)[作者簡介]汪小燕(1974一)，女，安徽桐城人，副教授，碩士，研究方向：數(shù)據(jù)挖掘，粗糙集理論，概念格，本體。蘇州科技學(xué)

6、院學(xué)報(自然科學(xué)版)20l4年定義5t。】設(shè)R是集合4上的二元關(guān)系，，y，是A中的任意三個元素，若Vs，t∈R，且5=，>，扛，若以Y為中間元素，則和t可以形成新的序偶，>，將這一運算稱為序偶的復(fù)合，記作s。拄，>。定理1閻設(shè)R是集合4上的二元關(guān)系，≠，判斷尺是否具有傳遞性，可以不考慮中的所有序偶。2改進的傳遞閉包算法文獻『81提出的傳遞閉包算法思想如下：設(shè)A是一非空集合，尺是集合A中的二元關(guān)系，計算R：尺一，將和其自身進行增量式復(fù)合運算，即計算尺。R，若產(chǎn)生序偶<，y>且=y，如果，y>譬，則將，y>并入；若產(chǎn)生序偶，y>

7、且=，，，如果，，，>∈，則將，y>舍棄；若產(chǎn)生序偶<，y>且≠，如果，>R，則將，>并人尺的末尾；若產(chǎn)生序偶，y>且≠y，如果，y>∈R，則將，y>舍棄，直到。R復(fù)合結(jié)束，則t(R)=尺U。當計算尺。時，若產(chǎn)生新的序偶，>R且≠，，y>要并人的末尾，如果產(chǎn)生這種類型的序偶較少，文獻『8]所提出的傳遞閉包算法優(yōu)越性是很明顯的，但是，如果產(chǎn)生這種類型的序偶較多，每個新產(chǎn)生的序偶都要從的第一個序偶按照定義5進行復(fù)合，計算量會增大。為了改進文獻『81提出的傳遞閉包算法，降低復(fù)合計算量．采取記錄集合中每個元素在R中作為序偶的第一元素第一次出現(xiàn)

8、的位置，現(xiàn)提出如下的3個定義。定義6設(shè)是集合4上的二元關(guān)系，尺=一，若任意，y>∈R，，y>在尺中的排序，就是序偶，>在尺中的位置。序偶，y>在R中的位置，一般從1開始編號。定義7設(shè)R是集合A上的二元關(guān)系，，Y是4中的任