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

赵相福 等: BWSS: 结合可疑集合簇计算极小碰集的 Boolean 算法 3229

用 Boolean 中的吸收律得到所有极小碰集. 具体规则和 Boolean 表达式计算原理见文献 [6], 其算法实现可递归表
示为算法 1.

算法 1. Boolean(F, allMHS).
输入: 问题集合簇 F={S 1 , S 2 , …, S n }, 候选解 allMHS;
中间变量: LeftMHS 和 RightMHS 分别存储左右分支两个冲突集的极小碰集;
输出: 极小碰集簇 allMHS.
Begin
, ∅){
1. IF (F
2. IF (F=={S}) return {{e i }|e i ∈ S, S ∈ F};
3. ELSE IF ( ∃ e({e} ∈ F)){ //存在单元素集合
4. Boolean({S i |S i ∈ ∧ < S i }, allMHS);
e
F
5. allMHS ← {mhs ∪ {e}|mhs ∈ allMHS};
6. }
7. ELSE IF ( ∃ ∀ S i (S i ∈ → ∈ S i )){ //所有集合都含有同一种元素
e
e
F
8. Boolean({S i −{e}|S i ∈ ∧ ∈ S i }, RightMHS); //右分支, 左分支为空
e
F
⊎
9. allMHS ← {{e}} RightMHS;
10. }
11. ELSE {
12. e ← Select_element( ∪ S i ); //从中间问题集合簇中选取元素
S i ∈F
13. Boolean({S i |S i ∈ ∧ < S i }, LeftMHS); //左分支
F
e
14. Boolean({S i |S i ∈ ∧ < S i } ∪ {S i −{e}|S i ∈ ∧ ∈ S i }, RightMHS); //右分支
F
e
F
e
⊎
15. allMHS ← {lmhs ∪ {e}|lmhs ∈ LeftMHS} RightMHS;
16. }
17. }
allMHS←Min(allMHS); //极小化处理
End
注: 第 9、15 行, 符号 ⊎ 代表两个解集直接合并. 在中间问题集合簇进行左、右分支时, 右分支问题集合簇不
含有元素 e, 在求出的候选解中不会含有元素 e. 而左分支解集需要归并元素 e, 所以左分支解集与右分支解集中的
元素 (候选解) 不相同, 故用直接合并符号, 以降低操作的时间复杂度.
这里我们把解的生成放在算法递归后 (第 2、5、9、15 行), 也就是说, 解的生成是自叶子节点到根节点扩展
的过程, 与文献 [15] 中的自根节点到叶子节点生成解在时间及空间复杂度上一致. Boolean 算法在求解的过程中
可能会产生超集, 最终求解后需要去超集检测.
为了描述方便, 在 Boolean 算法运行时, 我们给出如下定义.
定义 6. Boolean 算法生成树中, 称没有子节点的为叶子节点, 其中含有 0 个元素的叶子节点为空叶子节点, 含
有 m (m ⩾ 1) 个元素的叶子节点为叶子集合节点.
定义 7. 在 Boolean 算法求解过程中, 当前所关注的问题集合簇称为中间问题集合簇; 称去掉含有元素 e 集合
的集合簇为左分支集合簇 (第 13 行); 称只去掉元素 e 的集合簇为右分支集合簇 (第 14 行); 仅在右分支而不在左
分支的集合构成的簇称为可疑集合簇.
下面通过实例 2 进一步说明 Boolean 算法深度优先生成一棵树的过程以及对上面定义的一些具体描述.
例 2: 计算问题集合簇 F={{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {1, 7}}的所有极小碰集.