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

李秀格　朱紅寧

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

關鍵詞：模糊數學；相似矩陣；傳遞閉包

中圖分類號：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 概述

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

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

3 結束語

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

參考文獻：

[1] 汪培莊.模糊集合論及應用[M].上海:上海科學技術出版社,1983.

[2] 王秋萍,張……