求模糊相似矩阵的传递闭包的简捷算法

李秀格　朱红宁

摘要：模糊相似矩阵传递闭包的计算在模糊聚类及语法分析等领域应用广泛. 从最大树出发论述并实现了一种求模糊相似矩阵传递闭包的简捷算法. 与经典的求模糊相似矩阵传递闭包的算法—平方法比较, 该算法简捷, 运算量小。

关键词：模糊数学；相似矩阵；传递闭包

中图分类号：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] 王秋萍,张道宏.从 Warshall 算法到求模糊矩阵传递闭包的一个简捷算法[J].西安理工大学学报,2006, 22(3):274-277.

[3] 梁保松,曹殿立.模糊数学及其应用[M].北京:科学出版社,2007.

[4] 严蔚敏,吴伟民.数据结构(C语言版 )[M].北京:清华大学出版社,1997.