模糊關(guān)系矩陣傳遞閉包的warshall算法

《模糊關(guān)系矩陣傳遞閉包的warshall算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、第17卷第1期模糊系統(tǒng)與數(shù)學(xué)Vol.17,No.12003年3月FuzzySystemsandMathematicsMar.,2003文章編號(hào):1001-7402(2003)01-0059-03
模糊關(guān)系矩陣傳遞閉包的Warshall算法劉貴龍(北京語言大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,北京100083)摘要:通過對(duì)照關(guān)系的傳遞閉包和模糊關(guān)系的傳遞閉包,把求關(guān)系矩陣的傳遞閉包的算法完整地推廣到模糊關(guān)系矩陣上。關(guān)鍵詞:傳遞閉包;模糊關(guān)系矩陣;算法中圖分類號(hào):O159文獻(xiàn)標(biāo)識(shí)碼:A在人們的日常生活中,常需把所處理的事物按照特征分為若干類,數(shù)學(xué)上,把按一定要求和規(guī)律對(duì)事物進(jìn)行分類的方法稱為聚類分析,用模糊理

2、論進(jìn)行的聚類分析稱為模糊聚類分析。在模糊聚類分析中常需計(jì)算模糊關(guān)系矩陣的三種閉包,即自反閉包、對(duì)稱閉包及傳遞閉包,前兩種閉包的計(jì)算過于簡單,算法早已解決,計(jì)算量也不大;傳遞閉包的計(jì)算在理論上已經(jīng)解決,它是通過計(jì)算矩陣的方冪來實(shí)現(xiàn)的,但計(jì)算量很大,因此我們有必要尋找計(jì)算量較小的算法。在求通常的關(guān)系矩陣的傳遞閉包時(shí),有計(jì)算量少、較為簡單的方法,即Warshall算法;本文的目的就是要把求關(guān)系矩陣的傳遞閉包的Warshall算法完整地推廣到模糊關(guān)系矩陣上。這樣,通常的關(guān)系矩陣的Warshall算法是推廣后的模糊關(guān)系矩陣的Warshall算法的特例。設(shè)U={x1,x2,?,xn}是有限論域,R為U上

3、的二元關(guān)系,MR為相應(yīng)的關(guān)系矩陣,求傳遞閉包的Warshall算法是通過遞歸的辦法構(gòu)造n+1個(gè)矩陣W0,W1,W2,?,Wn;W0為R的關(guān)系矩陣,Wn即為關(guān)系R的傳遞閉包t(R)的相應(yīng)矩陣。計(jì)算步驟如下:
令W0=MR.
設(shè)Wi-1已求出,現(xiàn)求Wi.考慮Wi-1的第i列,設(shè)該列中不為0的元素分別位于p1,p2,?行。同時(shí)考慮Wi-1的第i行,設(shè)該行中不為0的元素分別位于q1,q2,?列,Wi在Wi-1的基礎(chǔ)上作如下改造:若Wi-1的第ps行qt列的元素為0,則把該元素改為1;若Wi-1的第ps行qt列的元素為1,則該元素不作變動(dòng);Wi-1的其他位置的元素不動(dòng);改造后的矩陣就是Wi.
重復(fù)
的

4、過程,直到求出Wn.
根據(jù)Wn寫出關(guān)系R的傳遞閉包t(R),算法結(jié)束。1模糊關(guān)系矩陣的傳遞閉包的Warshall算法現(xiàn)在我們來考慮有限論域U={x1,x2,?,xn}上的模糊關(guān)系,設(shè)R為U上的模糊關(guān)系,MR為
收稿日期:2002-01-15基金項(xiàng)目:教育部留學(xué)歸國人員專項(xiàng)研究項(xiàng)目(010201);教育部科學(xué)技術(shù)重點(diǎn)項(xiàng)目(01043)作者簡介:劉貴龍(1962-),男,北京語言大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系教授,博士,研究方向:數(shù)學(xué),計(jì)算機(jī)應(yīng)用。60模糊系統(tǒng)與數(shù)學(xué)2003年相應(yīng)的模糊關(guān)系矩陣,R的傳遞閉包記為t(R),若R具有自反性,R的傳遞閉包可通過平方法R→242kk-1kR→R→?→R=t(R)

5、(2

6、s-1已求出,現(xiàn)求Ws,記Ws=(aij),aij=aij∨(ais∧asj,∨、∧分別表示取大、取小;
重復(fù)
的過程,直到求出Wn;
根據(jù)Wn寫出模糊關(guān)系R的傳遞閉包t(R),算法結(jié)束。我們給出一個(gè)用Warshall算法求模糊矩陣(或模糊關(guān)系)傳遞閉包的例子。00.30.10.20.50.60.30.1例設(shè)MR=,則0.10.40.60.300.10.30W0=MR00.30.10.20.50.60.30.1W1=0.10.40.60.300.10.300.30.30.30.20.50.60.30.2W2=0.40.40.60.30.10.10.30.10.30.30.30.30.50.6

7、0.30.3W3=0.40.40.60.30.30.30.30.30.30.30.30.30.50.60.30.3W4=0.40.40.60.30.30.30.30.3W4即為所求的模糊矩陣的傳遞閉包。從我們給出的算法看出:當(dāng)模糊關(guān)系矩陣MR退化為布爾矩陣時(shí),該算法就是通常的Warshall算法。2Warshall算法的證明下面我們給出模糊關(guān)系矩陣的傳遞閉包的Warshall算法的理論證明。第1期劉貴龍:模糊