建立递阶结构模型的规范方法教学课件PPT.ppt

2020年5月7日11时54分,1,（三）建立递阶结构模型的规范方法,建立反映系统问题要素间层次关系的递阶结构模型，可在可达矩阵m的基础上进行，一般要经过区域划分、级位划分、骨架矩阵提取和多级递阶有向图绘制等四个阶段。这是建立递阶结构模型的基本方法。现以例4-1所示问题为例说明：与图4-5对应的可达矩阵（其中将si简记为i）为：,2020年5月7日11时54分,2,1234567,1234567,m=,2020年5月7日11时54分,3,1.区域划分,区域划分即将系统的构成要素集合s，分割成关于给定二元关系r的相互独立的区域的过程。首先以可达矩阵m为基础，划分与要素si（i=1，2，n）相关联的系统要素的类型，并找出在整个系统（所有要素集合s）中有明显特征的要素。有关要素集合的定义如下：,2020年5月7日11时54分,4,可达集r（si）。系统要素si的可达集是在可达矩阵或有向图中由si可到达的诸要素所构成的集合，记为r（si）。其定义式为：r（si）=sj|sjs，mij=1，j=1，2，ni=1，2，n先行集a（si）。系统要素si的先行集是在可达矩阵或有向图中可到达si的诸要素所构成的集合，记为a（si）。其定义式为：a（si）=sj|sjs，mji=1，j=1，2，ni=1，2，n共同集c（si）。系统要素si的共同集是si在可达集和先行集的共同部分，即交集，记为c（si）。其定义式为：c（si）=sj|sjs，mij=1，mji=1，j=1，2，ni=1，2，n,2020年5月7日11时54分,5,系统要素si的可达集r（si）、先行集a（si）、共同集c（si）之间的关系如图4-7所示：,图4-7可达集、先行集、共同集关系示意图,si,a（si）,c（si）,r（si）,2020年5月7日11时54分,6,起始集b（s）和终止集e（s）。系统要素集合s的起始集是在s中只影响（到达）其他要素而不受其他要素影响（不被其他要素到达）的要素所构成的集合，记为b（s）。b（s）中的要素在有向图中只有箭线流出，而无箭线流入，是系统的输入要素。其定义式为：b（s）=si|sis，c（si）=b（si），i=1，2，n如在于图4-5所对应的可达矩阵中，b（s）=s3，s7。当si为s的起始集（终止集）要素时，相当于使图4-7中的阴影部分c（si）覆盖到了整个a（si）（r（si）区域。这样，要区分系统要素集合s是否可分割，只要研究系统起始集b（s）中的要素及其可达集（或系统终止集e（si）中的要素及其先行集要素）能否分割（是否相对独立）就行了。,2020年5月7日11时54分,7,利用起始集b（s）判断区域能否划分的规则如下：在b（s）中任取两个要素bu、bv：如果r（bu）r（bv）（为空集），则bu、bv及r（bu）、r（bv）中的要素属同一区域。若对所有u和v均有此结果（均不为空集），则区域不可分。如果r（bu）r（bv）=，则bu、bv及r（bu）、r（bv）中的要素不属同一区域，系统要素集合s至少可被划分为两个相对独立的区域。利用终止集e（s）来判断区域能否划分，只要判定“a（eu）a（ev）”（eu、ev为e（s）中的任意两个要素）是否为空集即可。区域划分的结果可记为：（s）=p1，p2，pk，pm（其中pk为第k个相对独立区域的要素集合）。经过区域划分后的可达矩阵为块对角矩阵（记作m（p）。,2020年5月7日11时54分,8,为对给出的与图4-5所对应的可达矩阵进行区域划分，可列出任一要素si（简记作i，i=1，2，7）的可达集r（si）、先行集a（si）、共同集c（si），并据此写出系统要素集合的起始集b（s），如表4-1所示：,表4-1可达集、先行集、共同集和起始集例表,2020年5月7日11时54分,9,因为b（s）=s3，s7,且有r（s3）r（s7）=s3，s4，s5，s6s1，s2，s7=，所以s3及s4，s5，s6，s7与s1，s2分属两个相对独立的区域，即有：（s）=p1，p2=s3，s4，s5，s6s1，s2，s7。这时的可达矩阵m变为如下的块对角矩阵：,o,o,2020年5月7日11时54分,10,2.级位划分,区域内的级位划分，即确定某区域内各要素所处层次地位的过程。这是建立多级递阶结构模型的关键工作。设p是由区域划分得到的某区域要素集合，若用l1，l2，ll表示从高到低的各级要素集合（其中l为最大级位数），则级位划分的结果可写出：（p）=l1，l2，ll。某系统要素集合的最高级要素即该系统的终止集要素。级位划分的基本做法是：找出整个系统要素集合的最高级要素（终止集要素）后，可将它们去掉，再求剩余要素集合（形成部分图）的最高级要素，依次类推，直到确定出最低一级要素集合（即ll）。,2020年5月7日11时54分,11,为此，令lo=（最高级要素集合为l1，没有零级要素），则有：l1=si|sip-l0，c0（si）=r0（si），i=1，2，nl2=si|sip-l0-l1，c1（si）=r1（si），inlk=si|sip-l0-l1-lk-1，ck-1（si）=rk-1（si），in（4-3）式（4-3）中的ck-1（si）和rk-1（si）是由集合p-l0-l1-lk-1中的要素形成的子矩阵（部分图）求得的共同集和可达集。经过级位划分后的可达矩阵变为区域块三角矩阵，记为m（l）。,2020年5月7日11时54分,12,如对例4-1中p1=s3，s4，s5，s6进行级位划分的过程示于表4-2中。,表4-2级位划分过程表,2020年5月7日11时54分,13,对该区域进行级位划分的结果为：（p1）=l1，l2，l3=s5，s4，s6，s3同理可得对p2=s1，s2，s7进行级位划分的结果为：（p）=l1，l2，l3=s1，s2，s7这时的可达矩阵为：,2020年5月7日11时54分,14,3.提取骨架矩阵,提取骨架矩阵，是通过对可达矩阵m（l）的缩约和检出，建立起m（l）的最小实现矩阵，即骨架矩阵a。这里的骨架矩阵，也即为m的最小实现多级递阶结构矩阵。对经过区域和级位划分后的可达矩阵m（l）的缩检共分三步，即：检查各层次中的强连接要素，建立可达矩阵m（l）的缩减矩阵m（l）如对原例m（l）中的强连接要素集合s4，s6作缩减处理（把s4作为代表要素，去掉s6）后的新的矩阵为：,543127,543127,m（l）=,l1l2l3,l1l2l3,0,0,2020年5月7日11时54分,15,去掉m（l）中已具有邻接二元关系的要素间的超级二元关系，得到经进一步简化后的新矩阵m（l）。如在原例的m（l）中，已有第二级要素（s4，s2）到第一级要素（s5，s1）和第三级要素（s3，s7）到第二级要素的邻接二元关系，即s4rs5、s2rs1和s3rs4、s7rs2，故可去掉第三级要素到第一级要素的超级二元关系“s3r2s5”和“s7r2s1”，即将m（l）中35和71的“1”改为“0”，得：,2020年5月7日11时54分,16,进一步去掉m（l）中自身到达的二元关系，即减去单位矩阵，将m（l）主对角线上的“1”全变为“0”，得到经简化后具有最小二元关系个数的骨架矩阵a。如对原例有：,2020年5月7日11时54分,17,4.绘制多级递阶有向图d（a）,根据骨架矩阵a，绘制出多级递阶有向图d（a），即建立系统要素的递阶结构模型。绘图一般分为如下三步：分区域从上到下逐级排列系统构成要素。同级加入被删除的与某要素（如原例中的s4）有强连接关系的要素（如s6），及表征它们相互关系的有向弧。按a所示的邻接二元关系，用级间有向弧连接成有向图d（a）。,2020年5月7日11时54分,18,原例的递阶结构模型：以可达矩阵m为基础，以矩阵变换为主线的递阶结构模型的建立过程：mm（p）m（l）m（l）m（l）ad（a）,s1,s2,s7,s3,s4,s5,s6,第1级第2级第3级,区域划分,级位划分,强连接要素缩减,剔出超级关系,去掉自身关系,绘图,（块三角）,（区域块三角）,（区域下三角）,结束,2020年5月7日11时54分,19,例4-1某系统由七个要素（s1，s2，s7）组成。经过两两判断认为：s2影响s1、s3影响s4、s