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

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

接下来, 我们深入分析 Boolean 算法生成树及扩展候选解的策略, 给出一种简洁而高效的去超集策略.
碰集 HS={e 1 , e 2 , …, e m }, HS 的中间候选解 H={e 1 , e 2 , …, e k }, H ⊆ HS, 1 ⩽ k<m. 当候选解 H 扩展元素 e k+ 时,
1
若成为超集, 显然, 要么 e i (1 ⩽ ⩽ k) 独立覆盖度为 0, 要么 e k+ 的独立覆盖度为 0.
1
i
命题 1. 当候选解 H 扩展元素 e k+ 时, 元素 e k+ 的独立覆盖度最多为对应可疑问题集合簇中集合的个数.
1
1
证明: 因为 Boolean 算法是深度优先生成树, 元素 e k+ 之前覆盖的集合已经被上面路径的元素 e j (j=k+2, k+3, …,
1
m) 覆盖, 不再独立覆盖这些集合. 显然, 当扩展到元素 e k+ 时, 元素独立覆盖度最多是对应可疑问题集合簇中集合
1
的个数. 证毕.
命题 2. 若扩展完元素 e k+ 使极小候选解成为超集, 则候选解 H 一定与可疑集合簇中的每个集合交集非空.
1
证明: 如果中间问题集合簇得到的解 H 为极小候选解, 显然候选解中的元素独立覆盖度都不为 0. 因为布尔算
法在选取元素 e k+ 后生成的左分支不会含有元素 e k+ 的集合, 所以元素 e k+ 不会覆盖左分支的任何集合, 也不会
1
1
1
影响候选解 H 中元素的独立覆盖度. 当候选解扩展元素 e k+ 时, 只会影响元素 e k+ 的独立覆盖度, 而元素 e k+ 独
1
1
1
立覆盖的集合由命题 1 知, 只独立覆盖可疑集合簇, 因此从叶子节点扩展元素 e k+ 且成为超集必然会使元素 e k+1
1
的独立覆盖度变为 0, 即极小候选解覆盖了可疑集合簇全部集合. 证毕.
基于命题 1、2, 我们可以得到如下结论.
当候选解中的元素只有叶子节点元素时, 候选解定为中间问题集合簇的极小候选解 (此时候选解只有 1 个元
素). 从这一点作为算法递归的开始, 候选解每一次向上扩展元素时, 判断候选解与可疑集合簇是否存在交集为空
的集合, 若存在, 则候选解扩展上层元素也为极小候选解; 反之, 该候选解为超集需要删除. 按照上面的方式递归向
根节点扩展元素, 直到算法结束, 那么求出的解也全为极小碰集, 并且能够求出全部的解. 其中算法的正确性及完
备性由 Boolean 算法和独立覆盖策略保证.
在 Boolean 算法计算时, 我们也得到了额外的去超集优化, 具体见命题 3.
命题 3. 不含可疑集合簇的问题集合簇向根节点归并元素时无须去超集判断.
证明: 在 Boolean 算法中, 对于不含有可疑集合簇的分支, 候选解在选取元素时有 3 种情况. 第一, 叶子节点为
候选解中第 1 个元素, 该元素独立覆盖叶子节点集合, 独立覆盖度至少为 1; 第二, 中间问题集合簇中所有集合都
含有同一种元素, 当选取该元素时不会产生对应的左分支或者左分支为空, 没有子孙节点向该元素归并解, 该元素
即是候选解的第 1 个元素, 独立覆盖度至少为 1; 第三, 集合中只有 1 个元素, 在元素的选取时显然独立覆盖本身
集合, 独立覆盖度也至少为 1. 命题 3 的 3 种情况分别对应算法 1 的前 3 种情况, 也就是说, 只需要对 15 行元素的
扩展进行极小性判定. 证毕.
设 F l ⊂ F, 可疑集合簇 F r = F – F l , x 是 F l 的极小碰集, 元素 e 是 x 要扩展的元素. 我们得到定理 1.
定理 1. 如果 x 与 F r 中的集合都有交集, 该候选解 x 为超集.
证明: 因为 F l ⊂ F, 若 x 与 F r 中的集合都有交集, 则 x 也是 F 的极小碰集, 显然, x 再添加元素 e, 则成为 F 超
集. 接着证明 x 与 F r 中的集合至少有 1 个没有交集, 则 x ∪ {e}是 F 的极小碰集. 反正法, 若 x' ← ∪ {e}是 F 的超
x
集, 则必有 x' 的真子集是 F 的极小碰集. 显然, 元素 e 与 F l 中的任一集合都没有交集, 且 x'去掉任一元素 (除了元
素 e) 都不是 F l 和 F 的碰集, 故结论与假设矛盾. 证毕.
根据定理 1, 结合 Boolean 算法与可疑集合簇, 我们提出了 BWSS (Boolean with suspicious sets) 算法, 仅需修
改 Boolean 算法的第 15 行为如下两行内容, 即为 BWSS 算法的伪代码.
1. LeftMHS ← {lmhs ∪ {e}| ∃ S i ∈ ∧ ∈ S i , s.t., lmhs ∩(S i −{e})== ∅, lmhs ∈ LeftMHS};
e
F
⊎
2. allMHS ← LeftMHS RightMHS;
解释: 若左分支解集存在与可疑集合簇不相交的集合, 则扩展元素 e 后把该左分支解加入极小候选解中, 否则
删除该解. 接下来使用例 3 及图 3 进一步说明 BWSS 算法计算极小碰集.
例 3: 计算冲突集簇 F={{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {1, 4, 7}}的所有极小碰集.
图 3 中字体标红的集合为其对应左分支的可疑集合簇, 其生成解的规则与图 1 类似, 只不过增加了对候选解
极小性的判断. 从左边“▲”标记的叶子集合节点{6, 7}开始, 当叶子集合节点初始归并到候选解时为{{6}, {7}}, 发