基于ism的可达矩阵的简便算法

《基于ism的可达矩阵的简便算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于ISM的可达矩阵的简便算法　　摘要：解释结构模型化技术是最基本、最具特色的系统结构模型化技术，求可达矩阵又是建立递阶结构模型（ISM）中最重要的一步，本文基于ISM有向图，根据布尔代数运算规则，阐述一种更简便的由邻接矩阵求可达矩阵的新算法。本文与Warshall算法作对比，体现出该新算法的简便之处。该算法以后也可以实现计算机化。Abstract：Interpretativestructuralmodelingtechnologyisthemostbasic，themostuniquesystemstructuremodelingtechnolo

2、gy，andreachabilitymatrixisalsothemostimportantstepofinterpretativestructuralmodeling（ISM），basedonISMdirectedgraphandaccordingtotheoperationrulesofBooleanalgebra，thispaperexpoundedamoresimpleandnewalgorithmbyadjacencymatrixtoreachabilitymatrix.ThispapercomparedwithWarshallalgor

3、ithm，reflectedthesimpleplaceofthenewalgorithm.关键词：解释结构模型;邻接矩阵;可达矩阵;新算法Keywords：interpretativestructuralmodeling;adjacencymatrix;reachabilitymatrix;new7algorithm中图分类号：N945.12文献标识码：A文章编号：1006-4311（2015）04-0213-030引言本文阐述的由邻接矩阵求可达矩阵的新算法，较之以前运用普遍的Warshall算法更简便，计算量大大减小，可以作为以后普遍适用的新算

4、法。该新算法的推广将会使解释结构模型化技术的应用更简便易行。1解释结构模型（ISM）解释结构模型化技术是最基本、最具特色的系统结构模型化技术。其基本思想是：通过各种创造性技术，提取问题的构成要素，利用有向图、矩阵等工具和计算机技术，对要素及其相互关系等信息进行处理，最后用文字加以解释说明，明确问题的层次和整体结构，提高对问题的认识和理解程度。ISM的基本工作原理如图1所示。2常用的Warshall算法2.1邻接矩阵2.2邻接矩阵的特征2.3可达矩阵可达矩阵（M）是表示系统要素之间任意次传递性二元关系或有向图上两个节点之间通过任意长的路径可以到达情况

5、的方阵。若可达矩阵M=（mij）n×n则其定义为：7mij=1Si可达Sj（包括：直接可达、间接可达、自身可达）0否则2.4求可达矩阵的Warshall算法①Warshall算法步骤：可达矩阵与邻接矩阵存在必然的联系。可达矩阵M可用邻接矩阵A加上单位阵I，经过演算后求得。②可达矩阵的运算规则：矩阵运算规则和布尔代数运算规则。布尔代数的运算规则：矩阵A和M的元素均为“1”或“0”，是n*n阶0-1矩阵。0-1矩阵运算时遵循布尔代数的运算规则：0+0=0，0+1=1，1+0=1，1+1=10×0=0，0×1=0，1×0=0，1×1=1③Warshall

6、算法求可达矩阵举例：由邻接矩阵A求可达矩阵M的过程如下：A=0100001000010000A1=A+I=1100011000110001A1描述了各点间经长度不大于1的路径的可达情况。A2=A1×A1=1100011000110001×1100011000110001=1110011100110001　　A2描述了有向图中各点间经长度不大于2的路径的可达情况。A3=A2×A1=1110011100110001×11070011000110001=11110111001100011→2→3→4，“1”经过长度为3的路径到达“4”，即它描述了各点间经

7、长度不大于3的路径的可达情况。A4=A3×A1=1111011100110001×1100011000110001=1111011100110001=A3A4=A3计算结束。Warshall算法适合于由计算机产生可达矩阵。3由邻接矩阵求可达矩阵的简便算法3.1原理此简便方法中的邻接矩阵同Warshall算法中的邻接矩阵，同样采用布尔代数运算规则。原理：∵对邻接矩阵A，如果有aij=1，且ajk=1，则一定有aik=1。∴对邻接矩阵A，如果有aij=1，且对于A的转置矩阵AT有akj=1，则一定有aik=1。所以只要将A和AT对应列的1元素所在的行数

8、列出，并进行排列组合，即可得出所有的aik=1。3.2简便算法的操作步骤①建立邻接矩阵A及其转置矩阵AT;②将A和AT中对