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

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

为了清楚地分析动态问题集合簇及候选解的生成, 把选取的元素放在路径上, 中间问题集合簇放到了节点上,
在候选解生成时, 只有路径上的元素和叶子节点为候选解元素, 其余节点不是候选解部分. 用 F 1 、F 2 表示由 F 生
成的左、右节点 (根节点用 F 表示), 以“1”结尾表示左节点, “2”结尾表示右节点, 如: F 11 、F 1 是 2 F 1 的左、右节点.
可疑集合簇是动态变化的, 对于 F 1 与 F 2 来说, F 2 比 F 1 多的集合簇为可疑集合簇, 由图 2 可以看出可疑集合簇 F 21 =
{{2, 3}, {7}}.

F {1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {1, 7}
1
F 1
F 2
{3, 4, 5}, {5, 6, 7} {2, 3}, {3, 4, 5}, {5, 6, 7}, {7}
5 7
F 11 F 12
{3, 4}, {6, 7} {2, 3}, {3, 4, 5}
F 21
3 3
F 121 F 122
{6, 7} {4}, {6, 7} {2}, {4, 5} F 212
4 F 211 2

{6, 7}
F 1221 {4, 5} F 2121
图 2 Boolean 算法计算极小碰集

根节点 F, 首先选取重复度最高 (若有多个则按字典排序) 的元素 1, 生成左分支 F 1 ={{3, 4, 5}, {5, 6, 7}}, 右分
支 F 2 ={{2, 3}, {3, 4, 5}, {5, 6, 7}, {7}}. 对于 F 1 , 因为元素 5 覆盖了 F 1 的所有集合 (7 行), 则左分支 F 1 为空, 右分
1
支 F 12 ={{3, 4}, {6, 7}}. 对于 F 1 选取元素 3, 则左分支 F 121 ={{6, 7}}, 右分支 F 122 ={{4}, {6, 7}}. 因为左分支 F 121
2
只有 1 个集合不再进行分支 (2 行), 右分支 F 12 存在单元素集合的情况 (3–6 行), 没有右分支只有左分支, 得到 F 1221 =
2
{{6, 7}}, 不再递归分支且在算法第 2 行结束. 同理, 右分支 F 2 和 F 1 处理方式一样, 这里不再赘述.
按照上述描述, 布尔算法根据深度优先的规则生成了一棵树, 接下来从叶子节点求解这棵树. 从空叶子节点
F 1 扩展元素 5, {{5}}为 F 1 的左分支候选解; F 12 含有两个元素, 候选解为{{6}, {7}}, 扩展元素 3, {{3, 6}, {3, 7}}
1
1
为 F 1 的左分支候选解; F 122 含有两个元素, 候选解为{{6}, {7}}, 扩展元素 4, {4, 6}, {4, 7}为 F 12 的候选解. 因为
2
1
2
F 12 的候选解是 F 1 的右分支候选解, F 1 的候选解是 F 1 的右分支候选解, 所以左、右两部分解集合并即是 F 1 的
2
2
2
所有候选解. F 1 的所有候选解再扩展元素 1, 就得到了 F 的左分支候选解, 同理可以得到 F 2 的右分支候选解.
下面对 Boolean 算法及两种极小化策略的时间复杂度做简要分析.
设冲突集有 n 个集合, 每个集合有 m 个元素, 每次选取元素的重复度为 k. 令 t=(n/k), 可近似看作候选解中元
素的个数. 算法每次递归时, 左分支减少 k 个集合, 右分支由上层中间问题集合簇继承并减少一种元素. 计算碰集
( t−1 ) ( )
2
t
∑ m (m −1)
t+1
的时间复杂度为 O m (n−ik) =O k ≈ O(km ).
i+1
m−1
i=0
共求出 m 个碰集解, SSDM 算法需要比较所有解的包含关系, 因每个碰集含有 t 个元素, 取包含关系时间复
t
杂度为 O(t), 去超集的时间复杂度为 O(tm ).
2t
ICC 算法需要判断每个候选解的真子集是否为碰集, 其中每个候选解需要判断 t 个子集, 每个子集判断为碰
集的时间复杂度为 O(nt), 去超集的时间复杂度为 O(nt m ).
t
2
由此可见, 无论取以上哪种极小化策略, 去超集时间都占据整体求解时间的较大比重.

2 结合可疑集合簇去超集的 Boolean 算法
由例 2 可知, 布尔算法在生成解集时, 每次先得到节点 F 1 , F 2 的碰集, F 1 再扩展上层元素, 合并这两部分解就
能够得到节点 F 的所有碰集. 如果我们能够保证每次所求局部问题集合簇 F 1 , F 2 的碰集都是极小的, 且 F 1 扩展上
层元素后得到的解也是极小的, 通过递归的策略, 能够得到且仅得到 F 所有的极小碰集.