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

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

过 99% 以上都是 m 远大于 n (由 m, n 列也可以明显看出), 这对于 BWSS 算法来说无疑是有利的, 其极小化时间
仅占求解碰集时间的 2% 左右, 比图 6 产生的随机数据比值要低. 可见, 在真实环境的电路中, BWSS 算法比其他
算法更加有效.

表 1 BWSS、BWIICC、Boolean 算法在基准电路数据运行时间比较 (s)

BWIICC − BWSS Boolean− BWSS
MCS-family BWSS BWIICC (%) Boolean (%) Min/Bool (%) m, n MHSs
BWIICC Boolean
c880:CS020 0.240 149 － － 4 168.565 116 99.99 2.11 382, 10 189 826
c880:CS033 0.366 817 2.484 514 85.24 2 236.916 721 99.98 2.55 382, 10 137 670
c880:CS034 0.673 964 － － >10 000 － 3.78 382, 11 569 478
c880:CS061 0.122 208 1.279 238 90.45 385.183 549 99.97 7.23 368, 11 60 912
c880:CS065 0.060 907 0.317 447 80.81 7.349 233 99.17 1.61 376, 10 10 368
c880:CS071 0.300 336 1.841 463 83.69 1 345.545 487 99.98 3.14 382, 12 101 952
c880:CS089 1.131 833 － － >10 000 － 2.14 382, 13 311 040
c2670:CS005 0.028 947 0.769 768 96.24 237.833 395 99.99 1.55 1 188, 16 21 229
c2670:CS015 0.065 955 1.010 154 93.47 517.859 494 99.99 1.85 1 188, 19 42 458
c2670:CS021 0.058 306 1.010 154 94.23 83.771 619 99.93 1.24 1 151, 13 17 671
c2670:CS045 0.120 151 1.281 423 90.62 217.226 527 99.94 0.67 1 151, 16 26 768
c2670:CS049 0.352 656 － － 1 675.557 412 99.98 2.51 1 188, 18 86 325
c2670:CS050 0.984 415 － － 9 794.000 254 99.99 3.19 1 180, 11 231 000
c2670:CS063 0.764 386 － － 2 264.540 501 99.97 2.16 1 151, 13 108 780
c2670:CS091 0.585 599 － － 9 982.785 942 99.99 2.57 1 191, 16 235 102
c2670:CS095 0.457 656 － － 1 596.367 891 99.97 1.93 1 095, 15 78 720
c2670:CS100 1.059 034 － － 7 106.983 614 99.99 2.26 1 095, 15 157 440
c5315:CS013 0.321 187 － － 6 539.158 936 99.99 3.44 2 073, 7 134 360
c5315:CS018 0.068 371 1.068 631 93.60 90.578 441 99.92 2.78 2 067, 6 13 025
c5315:CS019 0.048 431 0.631 721 92.33 30.691 244 99.84 3.38 2 070, 7 8 215
c5315:CS021 0.687 751 － － 9 125.169 798 99.99 1.89 2 305, 9 171 264
c5315:CS024 1.789 075 － － 6 897.649 878 99.97 2.03 2 277, 7 137 664
c5315:CS040 0.074 091 0.617 938 88.01 12.250 784 99.40 1.18 2 101, 10 5 670
c5315:CS071 0.338 365 － － 528.165 406 99.94 1.48 2 065, 11 38 610
c5315:CS090 0.674 368 － － 1 740.440 622 99.96 1.87 2 065, 13 77 220
c7552:CS000 0.096 244 0.808 454 88.10 17.174 705 99.44 2.78 3 503, 29 5 143
c7552:CS004 0.071 693 1.241 514 94.23 222.555 819 99.97 1.58 3 503, 13 17 272
c7552:CS013 0.120 988 1.415 478 91.45 45.231 901 99.73 1.06 3 503, 31 10 286

4 总 结

Boolean 算法是计算极小碰集经典的算法, 因该算法可以和大部分极小碰集算法相互转化, 故对该算法提出的
优化策略能够具有一定的通用性. 极小碰集的极小化一直是阻碍算法提升的关键, 其中, 基于独立覆盖度思想的去
超集算法, 剥离了碰集极小性判定效率与极小碰集簇大小的相关性, 转化为碰集与原始问题集合簇取交集操作,
BWIICC、MHS-DMECV 算法在解决高难度问题时比结合 SSDM 去超集的 Boolean 算法节省了 3 个数量级, 是国
内外较快的算法.
本文深入分析 Boolean 算法使候选解成为超集的集合, 提出了可疑集合簇概念及 BWSS 算法, 在候选解极小
性判断时, 只需与可疑集合簇进行取交集, 若存在交集为空的集合, 则为极小候选解, 否则删除该解. 由于 BWSS
算法的叶子集合节点、空叶子节点、单元素集合这 3 种情况的元素无须极小化判断, 求解碰集时间占据算法的主
导, 整体时间效率上比 BWIICC、MHS-DMECV 算法节省 1 个数量级左右. 在解集数量大于 10 万的测试用例中, BWSS
算法仍然可以保持较高的求解效率. 此外, BWSS 算法没有额外的空间消耗, 为求解大规模问题提供了条件.