模糊关系矩阵传递闭包的warshall算法

《模糊关系矩阵传递闭包的warshall算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第17卷第1期模糊系统与数学Vol.17,No.12003年3月FuzzySystemsandMathematicsMar.,2003文章编号:1001-7402(2003)01-0059-03
模糊关系矩阵传递闭包的Warshall算法刘贵龙(北京语言大学计算机科学与技术系,北京100083)摘要:通过对照关系的传递闭包和模糊关系的传递闭包,把求关系矩阵的传递闭包的算法完整地推广到模糊关系矩阵上。关键词:传递闭包;模糊关系矩阵;算法中图分类号:O159文献标识码:A在人们的日常生活中,常需把所处理的事物按照特征分为若干类,数学上,把按一定要求和规律对事物进行分类的方法称为聚类分析,用模糊理

2、论进行的聚类分析称为模糊聚类分析。在模糊聚类分析中常需计算模糊关系矩阵的三种闭包,即自反闭包、对称闭包及传递闭包,前两种闭包的计算过于简单,算法早已解决,计算量也不大;传递闭包的计算在理论上已经解决,它是通过计算矩阵的方幂来实现的,但计算量很大,因此我们有必要寻找计算量较小的算法。在求通常的关系矩阵的传递闭包时,有计算量少、较为简单的方法,即Warshall算法;本文的目的就是要把求关系矩阵的传递闭包的Warshall算法完整地推广到模糊关系矩阵上。这样,通常的关系矩阵的Warshall算法是推广后的模糊关系矩阵的Warshall算法的特例。设U={x1,x2,⋯,xn}是有限论域,R为U上

3、的二元关系,MR为相应的关系矩阵,求传递闭包的Warshall算法是通过递归的办法构造n+1个矩阵W0,W1,W2,⋯,Wn;W0为R的关系矩阵,Wn即为关系R的传递闭包t(R)的相应矩阵。计算步骤如下:
令W0=MR.
设Wi-1已求出,现求Wi.考虑Wi-1的第i列,设该列中不为0的元素分别位于p1,p2,⋯行。同时考虑Wi-1的第i行,设该行中不为0的元素分别位于q1,q2,⋯列,Wi在Wi-1的基础上作如下改造:若Wi-1的第ps行qt列的元素为0,则把该元素改为1;若Wi-1的第ps行qt列的元素为1,则该元素不作变动;Wi-1的其他位置的元素不动;改造后的矩阵就是Wi.
重复
的

4、过程,直到求出Wn.
根据Wn写出关系R的传递闭包t(R),算法结束。1模糊关系矩阵的传递闭包的Warshall算法现在我们来考虑有限论域U={x1,x2,⋯,xn}上的模糊关系,设R为U上的模糊关系,MR为
收稿日期:2002-01-15基金项目:教育部留学归国人员专项研究项目(010201);教育部科学技术重点项目(01043)作者简介:刘贵龙(1962-),男,北京语言大学计算机科学与技术系教授,博士,研究方向:数学,计算机应用。60模糊系统与数学2003年相应的模糊关系矩阵,R的传递闭包记为t(R),若R具有自反性,R的传递闭包可通过平方法R→242kk-1kR→R→⋯→R=t(R)

5、(2

6、s-1已求出,现求Ws,记Ws=(aij),aij=aij∨(ais∧asj,∨、∧分别表示取大、取小;
重复
的过程,直到求出Wn;
根据Wn写出模糊关系R的传递闭包t(R),算法结束。我们给出一个用Warshall算法求模糊矩阵(或模糊关系)传递闭包的例子。00.30.10.20.50.60.30.1例设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即为所求的模糊矩阵的传递闭包。从我们给出的算法看出:当模糊关系矩阵MR退化为布尔矩阵时,该算法就是通常的Warshall算法。2Warshall算法的证明下面我们给出模糊关系矩阵的传递闭包的Warshall算法的理论证明。第1期刘贵龙:模糊