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

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

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

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

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

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

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

6、院學(xué)報(bào)(自然科學(xué)版)20l4年定義5t?！吭O(shè)R是集合4上的二元關(guān)系，，y，是A中的任意三個(gè)元素，若Vs，t∈R，且5=，>，扛，若以Y為中間元素，則和t可以形成新的序偶，>，將這一運(yùn)算稱(chēng)為序偶的復(fù)合，記作s。拄，>。定理1閻設(shè)R是集合4上的二元關(guān)系，≠，判斷尺是否具有傳遞性，可以不考慮中的所有序偶。2改進(jìn)的傳遞閉包算法文獻(xiàn)『81提出的傳遞閉包算法思想如下：設(shè)A是一非空集合，尺是集合A中的二元關(guān)系，計(jì)算R：尺一，將和其自身進(jìn)行增量式復(fù)合運(yùn)算，即計(jì)算尺。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。當(dāng)計(jì)算尺。時(shí)，若產(chǎn)生新的序偶，>R且≠，，y>要并人的末尾，如果產(chǎn)生這種類(lèi)型的序偶較少，文獻(xiàn)『8]所提出的傳遞閉包算法優(yōu)越性是很明顯的，但是，如果產(chǎn)生這種類(lèi)型的序偶較多，每個(gè)新產(chǎn)生的序偶都要從的第一個(gè)序偶按照定義5進(jìn)行復(fù)合，計(jì)算量會(huì)增大。為了改進(jìn)文獻(xiàn)『81提出的傳遞閉包算法，降低復(fù)合計(jì)算量．采取記錄集合中每個(gè)元素在R中作為序偶的第一元素第一次出現(xiàn)

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