基于ISM有向图的求可达矩阵的简洁算法

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

1、摘要目前用于大规模复杂系统辨识的常用方法是解释结构模型技术，即ISM。它是表明系统各要素间相互关系的宏观模型，通常用一种最方便的办法即图形法表示相互关系，如有向图就很方便在工程系统或社会经济系统中被采用。在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。在建立解释结构模型的过程中，对于图论部分，用矩阵表示图时涉及到一类重要的矩阵——可达矩阵，在现代系统工程中，可达矩阵是研究有向连接图节点关系的一种重要手段。有向图的邻接矩阵比较容易建立，但是在建立结构模型时，更有用的是要素间的可达关系。而可达矩阵的传统求法比

2、较复杂，尤其是有向连接图中节点较多的时候，运算量大，不够简便。本文提出了两种算法一改进法与转移法，分别根据邻接矩阵与可达矩阵的性质提出，旨在用于对系统进行结构建模时求取可达矩阵，主要针对在建立结构模型的过程中，求解基于有向图的可达矩阵。它们都是一种开放的代数方法，即在求解过程中加入人的主观信息，来寻找所需要的解。本文的主要结构如下：第一章在介绍模型与算法的基础上提出了本文要解决的问题。第二章介绍了解释结构模型，其国内外相关理论、三要素及建立步骤。第三章介绍了多种有关可达矩阵的算法。第四章是本文的主要部分，提出了改进法与转移法，并将两者与传

3、统算法进行比较，分析了其可行性。第五章是转移算法实现部分。转移算法演示软件的源程序附于全文的最后，以期能帮助感兴趣的读者更容易地了解算法的具体实现。关键词：解释结构模型；有向图；邻接矩阵；可达矩阵；有向无环图AbstractAtpresentthecommonmethodusedinlarge-scaleandcomplexysystemsistheinterpretativestructuralmodeling,namelyISM．Itisamacroscopicmodeltoindicatetheinterrelationbetwee

4、nthesystemfactors，generallyweBsethemostsimplemethodviz．figuretoexpresstheinterrelation,suchasDirectedGraphiswidelyusedintheprojectsystemorinthesocialeconomysystem．Innatureandinthepracticallivesofhumansociety，itissimpleanddirect-viewingusingthefigurestodescribeandexpressth

5、erelationofsomething．Duringcreatingtheinterpretativestructuralmodeling，forthepartoffigure，thereisakindofimportantmatrixwhenshowingthefigurewithmatrix,thatisReachabilityMatrix．Inmodemsystemsengineering，ReachabilityMatrixisallimportantmeanstostudytherelationbetweentheDirect

6、edGraphnodes．TheAdjacencyMatrixoftheDirectedGraphiseasytobuild，butthereach-relationoffactorsismoreusefulwhenbuildingthestnJcturemodel．Howerer,thetraditionalalgorithmofReachabilityMatrixiscomparativecomplicated，especiallywhentherealemorenodesintheDirectedGraph,thearithmeti

7、camountsalebigandnotenoughsimple．Thispaperintroducetwoalgorithms，thataleameliorationalgorithmandtransferalgorithm，theywerementionedapaltlyaccordingtothecharactersofAdjacencyMatrixandReachabilityMatrix．TheyaleusedtocomputetheReachabilityMatrixduringbuildingthestructuremode

8、lingofsystem,mostlyusedtocomputetheReachabilityMatrixofDirectedGraph．Theyaleallakindofexoterical