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

三）建立递阶结构模型的规范方法•建立反映系统问题要素间层次关系的递阶结构模型，可在可达矩阵M的基础上进行，一般要经过区域划分、级位划分、骨架矩阵提取和多级递阶有向图绘制等四个阶段这是建立递阶结构模型的基本方法•现以例4-1所示问题为例说明：•与图4-5对应的可达矩阵（其中将Si简记为i）为：9/11/20249/11/20241 1 1 2 3 4 5 6 71234567M =9/11/20249/11/20242 21.区域划分 区域划分即将系统的构成要素集合S，分割成关于给定二元关系R的相互独立的区域的过程 首先以可达矩阵M为基础，划分与要素Si（i = 1，2，…，n）相关联的系统要素的类型，并找出在整个系统（所有要素集合S）中有明显特征的要素 有关要素集合的定义如下：9/11/20249/11/20243 3①可达集可达集R R（（S Si i）系统要素系统要素S Si i的可达集是在可达矩阵或有的可达集是在可达矩阵或有向图中由向图中由S Si i可到达的诸要素所构成的集合，记为可到达的诸要素所构成的集合，记为R R（（S Si i）。

其定义式为：其定义式为： R R（（S Si i））= { S= { Sj j | | S Sj j∈∈S S，，mmij ij = 1 = 1，，j = 1j = 1，，2 2，，……，，n n } } i = 1i = 1，，2 2，，……，，n n②先行集先行集A A（（S Si i）系统要素系统要素S Si i的先行集是在可达矩阵或有的先行集是在可达矩阵或有向图中可到达向图中可到达S Si i的诸要素所构成的集合，记为的诸要素所构成的集合，记为A A（（S Si i）其定义式为：其定义式为： A A（（S Si i））= { S= { Sj j | S| Sj j∈∈S S，，mmji ji = 1 = 1，，j = 1j = 1，，2 2，，……，，n n } } i = 1i = 1，，2 2，，……，，n n③共同集共同集C C （（S Si i）系统要素系统要素S Si i 的共同集是的共同集是S Si i在可达集和先在可达集和先行集的共同部分，即交集，记为行集的共同部分，即交集，记为C C （（S Si i）） 。

其定义式为：其定义式为：C C（（S Si i））= { S= { Sj j | S| Sj j∈∈S S，，mmij ij = 1 = 1，， mmji ji = 1 = 1，， j = 1j = 1，，2 2，，……，，n n } i = 1} i = 1，，2 2，，……，，n n9/11/20249/11/20244 4系统要素系统要素SiSi的可达集的可达集R R（（S Si i）） 、、先行集先行集A A（（S Si i）） 、、共共同集同集C C （（S Si i））之间的关系如图之间的关系如图4-74-7所示：所示：图图4-7 4-7 可达集、先行集、共同集关系示意图可达集、先行集、共同集关系示意图SiA（（Si））C （（Si））R（（Si））9/11/20249/11/20245 5④起始集起始集B B（（S S））和终止集和终止集E E（（S S）系统要素集合系统要素集合S S的起始的起始集是在集是在S S中只影响（到达）其他要素而不受其他要素影中只影响（到达）其他要素而不受其他要素影响（不被其他要素到达）的要素所构成的集合，记为响（不被其他要素到达）的要素所构成的集合，记为B B（（S S）。

B B（（S S））中的要素在有向图中只有箭线流出，中的要素在有向图中只有箭线流出，而无箭线流入，是系统的输入要素其定义式为：而无箭线流入，是系统的输入要素其定义式为： B B（（S S））= { S= { Si i | S| Si i ∈∈S S，， C C（（S Si i））= = B B（（S Si i）） ，， i= 1i= 1，，2 2，，……，，n n } } 如在于如在于图图4-54-5所所对应对应的可达矩的可达矩阵阵中，中， B B（（S S））={S={S3 3，，S S7 7} } 当当S Si i为为S S的起始集（的起始集（终终止集）要素止集）要素时时，相当于使，相当于使图图4-4-7 7中的阴影部分中的阴影部分C C（（S Si i））覆盖到了整个覆盖到了整个 A A（（S Si i）（）（ R R（（S Si i））））区域 这样，要区分系统要素集合这样，要区分系统要素集合S S是否可分割，只要研是否可分割，只要研究系统起始集究系统起始集B B（（S S））中的要素及其可达集（或系统终止中的要素及其可达集（或系统终止集集E E（（S Si i））中的要素及其先行集要素中的要素及其先行集要素 ）能否分割（是否）能否分割（是否相对独立）就行了。

相对独立）就行了9/11/20249/11/20246 6 利用起始集利用起始集B B（（S S））判断区域能否划分的规则如下：判断区域能否划分的规则如下：在在B B（（S S））中任取两个要素中任取两个要素b bu u、、b bv v：：①如果如果R R（（b bu u））∩∩ R R（（b bv v））≠≠ψψ（（ψψ为空集），则为空集），则b bu u、、b bv v及及R R（（b bu u）、）、 R R（（b bv v））中的要素属同一区域若对所有中的要素属同一区域若对所有u u和和v v均有此结果（均不为空集），则区域不可分均有此结果（均不为空集），则区域不可分②如果如果R R（（b bu u））∩∩ R R（（b bv v））= =ψψ，则，则b bu u、、b bv v及及R R（（b bu u）、）、 R R（（b bv v））中的要素不属同一区域，系统要素集合中的要素不属同一区域，系统要素集合S S至少可至少可被划分为两个相对独立的区域被划分为两个相对独立的区域 利用终止集利用终止集E E（（S S））来判断区域能否划分，只要判来判断区域能否划分，只要判定定“ “A A（（e eu u））∩∩ A A（（e ev v））” ” （（e eu u、、e ev v为为E E （（S S））中的任意两中的任意两个要素）是否为空集即可。

个要素）是否为空集即可 区域划分的结果可记为：区域划分的结果可记为： ∏∏（（S S））=P1=P1，，P2P2，，……，，P Pk k，，……，，P Pm m （（其中其中P Pk k为为第第k k个相个相对对独立区域的要素集合）独立区域的要素集合）经过经过区域区域划分后的可达矩划分后的可达矩阵为块对阵为块对角矩角矩阵阵（（记记作作MM（（P P））9/11/20249/11/20247 7 为对给出的与图为对给出的与图4-54-5所对应的可达矩阵进行区域划分，所对应的可达矩阵进行区域划分，可列出任一要素可列出任一要素S Si i（（简记作简记作i i，，i i=1=1，，2 2，，……，，7 7））的可达集的可达集R R（（S Si i）） 、、先行集先行集A A（（S Si i）） 、、共同集共同集C C （（S Si i），），并据此写出系统并据此写出系统要素集合的起始集要素集合的起始集B B（（S S），），如表如表4-14-1所示：所示：表4-1 可达集、先行集、共同集和起始集例表SiSiR R（（S Si i））A A（（S Si i））C C （（S Si i））B B（（S S））1 12 23 34 45 56 67 71 11 1，，2 23 3，，4 4，，5 5，，6 64 4，，5 5，，6 65 54 4，，5 5，，6 61 1，，2 2，，7 71 1，，2 2，，7 72 2，，7 73 33 3，，4 4，，6 63 3，，4 4，，5 5，，6 63 3，，4 4，，6 67 71 12 23 34 4，，6 65 54 4，，6 67 73 37 79/11/20249/11/20248 8 因为因为B B （（S S ）） = {S= {S3 3，，S S7 7} } , ,且有且有R R（（S S3 3））∩∩ R R（（S S7 7）） = {S= {S3 3，， S S4 4，， S S5 5，， S S6 6} } ∩{∩{S S1 1，， S S2 2，， S S7 7} } = =ψψ，所以，所以S S3 3及及S S4 4，， S S5 5，， S S6 6，， S S7 7与与 S S1 1，， S S2 2分属两个分属两个相相对对独立的区域，即有：独立的区域，即有： ∏∏（（S S））=P=P1 1，，P P2 2 = {S= {S3 3，， S S4 4，， S S5 5，， S S6 6} } ∩{∩{S S1 1，， S S2 2，， S S7 7} } 。

这时这时的可达矩的可达矩阵阵MM变为变为如下的如下的块对块对角矩角矩阵阵：：OO 3 4 5 6 1 2 7 3456127M（P）=P1P29/11/20249/11/20249 92.级位划分 区域内的级位划分，即确定某区域内各要素所处区域内的级位划分，即确定某区域内各要素所处层次地位的过程这是建立多级递阶结构模型的层次地位的过程这是建立多级递阶结构模型的关键工作关键工作设设P P是由区域划分得到的某区域要素集合，若用是由区域划分得到的某区域要素集合，若用L L1 1，，L L2 2，，……，，L Ll l表示从高到低的各级要素集合（其中表示从高到低的各级要素集合（其中l l为最大级位数），则级位划分的结果可写出：为最大级位数），则级位划分的结果可写出： ∏∏（（P P））=L=L1 1，，L L2 2 ，，……，，L Ll l 某系某系统统要素集合的最高要素集合的最高级级要素即要素即该该系系统统的的终终止集止集要素级级位划分的基本做法是：找出整个系位划分的基本做法是：找出整个系统统要要素集合的最高素集合的最高级级要素（要素（终终止集要素）后，可将它止集要素）后，可将它们们去掉，再求剩余要素集合（形成部分去掉，再求剩余要素集合（形成部分图图）的最）的最高高级级要素，依次要素，依次类类推，直到确定出最低一推，直到确定出最低一级级要素要素集合（即集合（即L Ll l）。

9/11/20249/11/20241010为此，令为此，令L LO O= =ψψ（最高级要素集合为（最高级要素集合为L L1 1，没有零级要，没有零级要素），则有：素），则有：L L1 1={={S Si i|S|Si i∈∈P-LP-L0 0，，C C0 0（（S Si i））= R= R0 0（（S Si i），），i=1i=1，，2 2，，……，，n n} }L L2 2={={S Si i|S|Si i∈∈P-LP-L0 0-L-L1 1，，C C1 1（（S Si i））= R= R1 1（（S Si i），），i

求得的共同集和可达集 经过级经过级位划分后的可达矩位划分后的可达矩阵变为阵变为区域区域块块三角三角矩矩阵阵，，记为记为M M（（L L）9/11/20249/11/20241111如对例如对例4-14-1中中P P1 1={S={S3 3，，S S4 4，，S S5 5，，S S6 6} }进进行行级级位划分的位划分的过过程示于表程示于表4-24-2中表4-2 级位划分过程表要素集合要素集合S Si iR R（（S S））A A（（S S））C C（（S S））C C（（S S））= = R R（（S S））∏∏（（P P1 1））P P1 1-L-L0 03 34 45 56 63 3，，4 4，，5 5，，6 64 4，，5 5，，6 65 54 4，，5 5，，6 63 33 3，，4 4，，6 63 3，，4 4，，5 5，，6 63 3，，4 4，，6 63 34 4，，6 65 54 4，，6 6√√L L1 1 ={S={S5 5} }P P1 1-L-L0 0-L-L1 13 3，，4 46 63 3，，4 4，，6 64 4，，6 64 4，，6 63 33 3，，4 4，，6 63 3，，4 4，，6 63 34 4，，6 64 4，，6 6√√√√L L1 1 ={S={S4 4，， S S6 6} }P P1 1-L-L0 0-L-L1 1-L-L2 23 33 33 33 3√√L L1 1 ={S={S3 3} }9/11/20249/11/20241212对该区域进行级位划分的结果为：对该区域进行级位划分的结果为： ∏ ∏（（P P1 1））=L=L1 1，，L L2 2 ，，L L3 3={S={S5 5} }，，{S{S4 4，，S S6 6} }，，{S{S3 3} } 同理可得同理可得对对P P2 2={S={S1 1，，S S2 2，， S S7 7} }进进行行级级位划分的位划分的结结果果为为：： ∏ ∏（（P P））=L=L1 1，，L L2 2 ，，L L3 3 = = {S{S1 1} } ，，{S{S2 2} } ，，{S{S7 7} }这时这时的可达矩的可达矩阵为阵为：： 5 4 6 3 1 2 7 5463127M（L）=L1L2L3L1L2L3009/11/20249/11/202413133.提取骨架矩阵• •提取骨架矩阵，是通过对可达矩阵提取骨架矩阵，是通过对可达矩阵MM（（L L））的缩约和检出，建立起的缩约和检出，建立起MM（（L L））的最小实现矩阵，即骨架矩阵的最小实现矩阵，即骨架矩阵A’A’。

这里的骨架矩阵，也即为这里的骨架矩阵，也即为MM的最小实现的最小实现多级递阶结构矩阵对经过区域和级位划分后的可达矩阵多级递阶结构矩阵对经过区域和级位划分后的可达矩阵MM（（L L））的缩检的缩检共分三步，即：共分三步，即：I. I.检查各层次中的强连接要素，建立可达矩阵检查各层次中的强连接要素，建立可达矩阵MM（（L L））的缩减矩阵的缩减矩阵M’M’（（L L）） 如如对对原例原例MM（（L L））中的强连接要素集合中的强连接要素集合{S{S4 4，，S S6 6} }作作缩缩减减处处理（把理（把S S4 4作作为为代表代表要素，去掉要素，去掉S S6 6））后的新的矩后的新的矩阵为阵为：：5 4 3 1 2 7 543127M’（L）=L1L2L3L1L2L3009/11/20249/11/20241414•去掉去掉M’M’（（L L））中已具有邻接二元关系的要素间的超级二中已具有邻接二元关系的要素间的超级二元关系，得到经进一步简化后的新矩阵元关系，得到经进一步简化后的新矩阵M’’M’’（（L L）。

如在原例的如在原例的M’M’（（L L））中，已有第二级要素（中，已有第二级要素（S S4 4，，S S2 2））到第一级要素（到第一级要素（S S5 5，，S S1 1））和第三级要素（和第三级要素（S S3 3，，S S7 7））到第到第二级要素的邻接二元关系，即二级要素的邻接二元关系，即S S4 4RSRS5 5、、 S S2 2RSRS1 1和和S S3 3RSRS4 4、、 S S7 7RSRS2 2，，故可去掉第三级要素到第一级要素的超级二元故可去掉第三级要素到第一级要素的超级二元关系关系“ “S S3 3R R2 2S S5 5” ”和和“ “S S7 7R R2 2S S1 1” ”，，即将即将 M’M’（（L L）中）中3 3→→5 5和和7 7→→1 1的的“ “1”1”改为改为“ “0”0”，得：，得： 5 4 3 1 2 7 543127M’’（L）=L1L2L3L1L2L3009/11/20249/11/20241515•进一步去掉进一步去掉M’’M’’（（L L））中自身到达的二元关系，中自身到达的二元关系，即减去单位矩阵，将即减去单位矩阵，将M’’M’’（（L L））主对角线上的主对角线上的“ “1”1”全变为全变为“ “0”0”，得到经简化后具有最小二，得到经简化后具有最小二元关系个数的骨架矩阵元关系个数的骨架矩阵A’ A’。

如对原例有：如对原例有： 5 4 3 1 2 7 543127A’=M’’（L）- I =L1L2L3L1L2L3009/11/20249/11/202416164.绘制多级递阶有向图D（A’） 根据骨架矩阵A’，绘制出多级递阶有向图D（A’），即建立系统要素的递阶结构模型绘图一般分为如下三步：1.分区域从上到下逐级排列系统构成要素2.同级加入被删除的与某要素（如原例中的S4）有强连接关系的要素（如S6），及表征它们相互关系的有向弧3.按A’所示的邻接二元关系，用级间有向弧连接成有向图D（A’）9/11/20249/11/20241717原例的递阶结构模型：原例的递阶结构模型：以可达矩阵以可达矩阵MM为基础，以矩阵变换为主线的递阶结构模型的建立为基础，以矩阵变换为主线的递阶结构模型的建立过程：过程： M → MM → M（（P P ））→ → MM（（L L））→ → M’M’（（L L）） → → M’’M’’（（L L）） → → A’→ DA’→ D（（A’ A’）） S1S2S7S3S4S5S6第1级第2级第3级区域划分级位划分强连接要素缩减剔出超级关系去掉自身关系绘图（块三角）（区域块三角）（区域下三角）结束9/11/20249/11/20241818•例4-1 某系统由七个要素（S1，S2，…，S7）组成。

经过两两判断认为：S2影响S1、S3影响S4、S4影响S5、S7影响S2、S4和S6相互影响这样，该系统的基本结构可用要素集合S和二元关系集合Rb来表达，其中： S S = {S= {S1 1，，S S2 2，，S S3 3，，S S4 4，，S S5 5，，S S6 6，，S S7 7} } R Rb b = { = {（（S S2 2，，S S1 1），（），（S S3 3，，S S4 4），（），（S S4 4，，S S5 5），）， （（S S7 7，，S S2 2），（），（S S4 4，，S S6 6），（），（S S6 6，，S S4 4））} } 返回返回9/11/20249/11/202419195162374图4-5 例 4-1 有向图返回9/11/20249/11/20242020。