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

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

现对应的可疑集合簇为{{4}}, 候选解{{6}, {7}}与可疑集合簇交集为空, 则为极小候选解, 可以归并元素 3. 对于中
间集合簇{{3, 4, 5}, {5, 6, 7}}在求解的过程中只有 1 个可疑集合{4}, 我们已经计算完毕, 其余节点按照原始
Boolean 算法计算即可, 得到的所有极小候选解为{5}, {3, 6}, {3, 7}, {4, 6}, {4, 7}, 对这些解再次归并元素 1 时, 因
为对应的可疑集合簇不为空, 需要对解的极小性进行判断. 其中, 只有极小候选解{3, 7}与可疑集合簇{{2, 3}, {4,
7}}都有非空交集, 因而需要去掉. 其余解归并元素 1, 左分支共得到 4 个极小碰集解{1, 5}, {1, 3, 6}, {1, 4, 6}, {1,
4, 7}. 同理, 右分支没有任何极小候选解全部覆盖对应的可疑集合簇, 最终得到 7 个极小碰集解{3, 7}, {3, 4, 5}, {3,
4, 6}, {2, 4, 5}, {2, 5, 7}, {2, 4, 6}, {2, 4, 7}, 加上左分支的极小碰集解, 共得到 11 个极小碰集解.

{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {1, 4, 7}
1
{3, 4, 5}, {5, 6, 7} {2, 3}, {3, 4, 5}, {5, 6, 7}, {4, 7}
5 3
{3, 4}, {6, 7} {5, 6, 7}, {4, 7} {2}, {4, 5}, {5, 6, 7}, {4, 7}
3 7 2
{6, 7} {4}, {6, 7} {5, 6}, {4} {4, 5}, {5, 6, 7}, {4, 7}
4 4 5
{6, 7} {5, 6} {4, 7} {4}, {6, 7}, {4, 7}
4
{6, 7}
图 3 使用 BWSS 算法对可疑集合簇标记

该算法充分结合了独立覆盖思想及 Boolean 算法计算碰集的规则, 提出了一种更简便、高效的计算方法. 由
命题 3 我们可以知道, 当 Boolean 算法递归进入到左、右分支时我们才考虑候选解的极小性判断, 因为其他情况
不含有可疑集合簇, 所以无须极小化判断, 这也为算法去超集减少了大量判断.
时间复杂度: 设 n, m, k, t 变量与 Boolean 算法时间复杂度分析相同. BWSS 算法与 Boolean 算法的不同点在于
去超集上, BWSS 算法对每一候选解在极小化过程中发现与可疑集合簇没有交集的集合时直接结束判断, 去超集
时取决于候选解与集合取交集的次数.
含有 t 个元素的集合取交集的时间为 O(t), 最坏情况下, 候选解每次扩展元素时都需要与可疑集合簇的所有
kt(1+t) n 2
集合取交集. 从叶子节点扩展元素, 候选解对集合取交集的次数为 1 × k+2 × k+…+t × k= ≈ , 所以总体
2 2k
( 2 ) 2
n n
2
t+1
去超集的时间复杂度为 O m t . 布尔算法的时间复杂度为 O(km ), 若 <km, 即 n <2mk , 则极小化时间将低
2
2k 2k
于求解时间. 除此之外, 叶子集合节点、空叶子节点、单元素集合这 3 种情况的元素不必去超集判断, 因而总体去
( )
n 2
超集时间远小于 O m t .
2k
3 实验分析
在本节中我们对 BWSS 算法进行实验分析 (https://github.com/helong0102/hittingset-BWSS), 选取目前效率较
快的 MHS-DMECV、BWIICC、Boolean、STACCATO 这 4 种算法作为比较对象. 平台如下: Windows 10 操作系
统, CPU Intel Core i7-1065G7 1.30 GHz 16 GB 4 核 RAM C++, 实验测试用例分为人工随机数据与 ISCAS-85 基准
电路数据 (基准电路冲突集压缩包获取地址: http://www.fe.up.pt/~rma/benchmarks2.zip).

3.1 随机数据
本节采用文献 [7,14,15] 的伪随机数据, 共有 3 个输入参数: 问题集合簇内集合的个数 n、集合簇内元素的最
大种类数 m、每一位元素出现的概率 p (在同一组测试数据中, 所有元素的 p 均相等). 图 4 中, 参数设计: n 取值
为 200, m 取值为 15、20、25、30, p 取值为 0.15–0.85 (间隔 0.05). 每一组数据随机测试 3 次, 取其平均执行时间
作为实验结果.