Page 307 - 《软件学报》2025年第7期

3228 软件学报 2025 年第 36 卷第 7 期

[7]
detecting minimization, SSDM) . 该算法用新得到碰集与极小碰集簇中部分甚至全部解进行子集比较, 随着解集规
模的增加, 极小化时间往往占据整体求解的绝大部分. 另一种是独立覆盖检测去超集算法 (independent coverage
checking, ICC) [15] , 其策略是判断碰集 (解) 中是否存在独立覆盖度为 0 的元素, 也就是说, 若碰集中去掉某个或某
些元素后仍是碰集, 则为超集, 反之为极小碰集. ICC 算法因需要判断每一个解的真子集是否为碰集, 也牺牲了部
分空间. 目前, 去超集算法很少考虑碰集算法自身对解集的影响, 只单纯寻找极小化条件, 且在极小化时, 都是考虑
与全局的解集或者问题集合簇操作.
针对以上问题, 本文基于 Boolean 算法生成树规则, 提出一种结合局部问题集合簇去超集的策略. 所提算法对
候选解进行极小化时, 只与部分集合取交集, 减少了对全局的搜索, 并且对已发现是超集的候选解进行删除, 在一
定程度上起到了剪枝作用. 除此之外, 该算法无需额外的空间消耗, 最终结果仅且生成所有的极小碰集.

1 基础知识

1.1 基于模型诊断的相关概念
[1]
定义 1 . 待诊断系统可定义为一个三元组 (D, P, O). 其中, D 为系统描述, 为一阶谓词公式的集合; P 为系统
组成部件的集合, 是一个有限常量集; O 为观测集, 是一阶谓词公式的有限集.
如果系统输出的真实值和理论值不同, 我们称为是不一致的, 反之称为是一致的.
[1]
定义 2 . 称部件集{c 1 , c 2 , …, c n } ⊆ P 是冲突集, 当且仅当 D ∪ O ∪ {¬A(c 1 ), ¬A(c 2 ), …, ¬A(c n )}是不一致的. 其
中, c 正常时 A(c)=0, c 故障时 A(c)=1, c ∈ P . 若冲突集的任意真子集都不是冲突集, 称冲突集是极小冲突集.
[1]
定义 3 . 设 F={S 1 , S 2 , …, S n }为集合簇, 称 H 是 F 的碰集, 如果 H 满足以下两个条件:
∪
(1) H ⊆ S i ;
S i ∈F
(2) 对于任意一个 S i ∈ F, 都有 H ∩ S i , ∅.

如果 H 的任意真子集都不是 F 的碰集, 那么碰集 H 为 F 的一个极小碰集. 其中, 去掉定义 3 中的约束 (2), 则
称 H 为 F 的候选解.
[1]
定义 4 . 给定一个 MBD 问题, 一个诊断被定义为一组组件 ∆ 的集合, 其中 ∆ ∈ P, 当 D ∧ O ∧ {A(c)|c ∈ ∆ ∧

}
{¬A(c)|c ∈ P− ∆ }是一致的.
由定义 2–定义 4 可知, 给定待诊断系统 (D, P, O), ∆ ⊆ P 为该系统的极小诊断, 当且仅当 ∆ 为当前极小冲突集

簇的极小碰集. 其中求解极小碰集的效率将直接影响极小诊断的效率. 因此, 研究高效的极小碰集求解方法对提升
诊断效率具有重要的意义.
定义 5 [15] . 候选解 H={e 1 , e 2 , …, e m }, 冲突集 S j ∈ F, 若 H ∩ S j ={e k }, 则称在 H 中, e k 覆盖了集合 S j . e k 覆盖 F 中
集合的个数称为 e k 的覆盖度. 如果 H 中没有其他元素覆盖 e k 所覆盖的集合, 则称 e k 独立覆盖这些集合, 独立覆盖
集合的个数称为 e k 的独立覆盖度.
由定义 5 知, 若碰集中存在独立覆盖度为 0 的元素, 则该碰集为超集, 否则为极小碰集. 因为独立覆盖为 0 的
元素没有单独覆盖任何集合, 去掉该元素也不影响碰集覆盖集合的个数, 故去掉该元素的碰集也是碰集 [15] . 下面
用例 1 对上面的定义进行详细描述.
例 1: 给定问题集合簇 F={{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {1, 4, 7}}.
集合{1, 5}, {1, 3, 6}, {1, 3, 7}及{3, 4, 6}都是碰集, 也是集合簇 F 的候选解. {1, 3, 6}中的元素 1、3、6 分别独
立覆盖集合{1, 4, 7}, {3, 4, 5}, {5, 6, 7}, 因元素 1、3、6 独立覆盖都大于 0, 故{1, 3, 6}为极小碰集. 对于集合{1, 2,
3}, 因碰集{1, 3, 6}中有两个元素同时覆盖, 故没有任何元素独立覆盖该集合. 换句话说, {1, 3, 6}去掉任何一个元
素都不构成碰集 (或者其子集{1, 3}, {1, 6}, {3, 6}都不是碰集), 故{1, 3, 6}为极小碰集. 而碰集{1, 3, 7}, 因存在子
集{3, 7}为碰集, 故{1, 3, 7}为超集.

1.2 Boolean 算法简介
Boolean 方法将问题集合簇编码为 Boolean 表达式, 然后应用给定的规则对表达式进行计算得到碰集, 再应