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

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