求模糊相似矩陣的傳遞閉包的簡捷算法

李秀格　朱紅寧

摘要：模糊相似矩陣傳遞閉包的計算在模糊聚類及語法分析等領(lǐng)域應(yīng)用廣泛. 從最大樹出發(fā)論述并實現(xiàn)了一種求模糊相似矩陣傳遞閉包的簡捷算法. 與經(jīng)典的求模糊相似矩陣傳遞閉包的算法—平方法比較, 該算法簡捷, 運算量小。

關(guān)鍵詞：模糊數(shù)學(xué)；相似矩陣；傳遞閉包

中圖分類號：O159 文獻標識碼：A 文章編號：1009-3044(2014)26-6161-04

Abstract: The computing transitive closure of fuzzy similar matrix widely used in many fields such as fuzzy clustering and Syntax analysis. From the largest tree , we deal with and accomplish a kind of simple and direct method to derive the transitive closure of fuzzy similar matrix. In comparison with the classical algorithm to derive the transitive closure of fuzzy similar matrix—the square algorithm, this algorithm is characterized by simplicity, agility and small calculation quantity.

Key words: fuzzy mathematics; similar matrix; transitive closure

1 概述

模糊聚類在預(yù)測與決策以及經(jīng)濟、生物、化學(xué)、環(huán)境科學(xué)等學(xué)科得到了廣泛的應(yīng)用, 而模糊相似矩陣傳遞閉包的計算在模糊聚類中起著關(guān)鍵的作用. 另外傳遞閉包的計算在語法分析中也有很多應(yīng)用。

對模糊相似矩陣傳遞閉包的計算, 人們普遍采用平方法, 其時間復(fù)雜度為O( n3log2n ); 文獻[1]中提到童增祥等人給出的求傳遞閉包的一種簡捷算法—輪流做媒法, 文獻[2]對該簡捷算法進行了進一步的討論, 該算法與平方法相比, 降低了O( log2n )時間因子. 本文從最大樹出發(fā), 實現(xiàn)并證明了一種求模糊相似矩陣的傳遞閉包的簡捷算法, 該算法進一步減少了計算量, 將時間復(fù)雜度降低到O( n2 )。

3 結(jié)束語

模糊相似矩陣傳遞閉包的計算廣泛的應(yīng)用于模糊聚類及語法分析等各個應(yīng)用領(lǐng)域。本文從最大樹出發(fā)論述并實現(xiàn)了一種求模糊相似矩陣傳遞閉包的簡捷算法, 該算法不論是在時間復(fù)雜性上還是空間復(fù)雜度上都有了明顯改進, 并容易在計算機上實現(xiàn)該方法。

參考文獻：

[1] 汪培莊.模糊集合論及應(yīng)用[M].上海:上海科學(xué)技術(shù)出版社,1983.

[2] 王秋萍,張道宏.從 Warshall 算法到求模糊矩陣傳遞閉包的一個簡捷算法[J].西安理工大學(xué)學(xué)報,2006, 22(3):274-277.

[3] 梁保松,曹殿立.模糊數(shù)學(xué)及其應(yīng)用[M].北京:科學(xué)出版社,2007.

[4] 嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版 )[M].北京:清華大學(xué)出版社,1997.