Page 166 - 《软件学报》2025年第12期

欧阳继红 等: HSDiag: 变种碰集算法求解诊断 5547

3 实验分析

在本节中我们对新提出的 HSDiag 算法和使用等价类优化后的 HSD-EC 算法进行实验分析, 对比算法选取目
前求解极小冲突最先进的 MARCO-ABC 算法 [7] 以及求解极小碰集的 LBX 算法, 命名 MCS-MHS 算法. 实验平台
如下: Ubuntu 16.04 Linux Intel Xeon E5-1607@3.00 GHz 16 GB RAM C++, 实验测试用标准的 Polybox, Fulladder
电路和国际基准电路 ISCAS-85 [35,36] .
3.1 HSDiag 算法与 MCS-MHS 算法实验对比
图 7 是 n 个组件的 Polybox_n 型和 n 位全加器 Fulladder_n 型电路示例图, 这两种类型电路数据来自于文
献 [1,8,9], 对于 Polybox_n 电路, 除了第一列组件为与非门, 其余组件都是或非门. 全加器 Fulladder_n 电路是由 n
个 Fulladder_1 电路组成, 其中前一个全加器的输出是后一个的输入. 图 7 还为使用优化等价类策略标记了分割
(选取变量) 位置, 具体信息见第 3.2 节.

i 1+2(n+2)(n−1)/2 i 1+(n+2)(n−1)/2
i n+1+(n+2)(n−1)/2
i 2+2(n+2)(n−1)/2 N 1
i 1+10n
i 1+5n
Z n+1 i 2+5n
Z (n+2)(n−1)/2−1 N 1
i 3+2(n+2)(n−1)/2 N 2
i 4+2(n+2)(n−1)/2 i n+2+(n+2)(n−1)/2 i 2(n+2)(n−1)/2−1 i 2+10n i 12n−1
N 2
i 1+9n
i 2+(n+2)(n−1)/2 i 4+5n i 12n N 5n−4 i 2+9n
Z n+2 ... N 4 N 5n−3
i 1+12n
... ... i 2(n+2)(n−1)/2 i 5+5n ... i 9n
N 5 i 4+9n
N 3 N 5n−1
i 3+5n
i n+(n+2)(n−1)/2 Z 2n−1 i 3+9n i 10n
i 2n−1+2(n+2)(n−1)/2 Z (n+2)(n−1)/2 N 5n
i 2n+2(n+2)(n−1)/2 i 2n−1+(n+2)(n−1)/2 N 5n−2
N n 等价类切割线
等价类切割线
(a) Polybox_(n+2)(n–1)/2 circuit (b) Fulladder_n circuit
图 7 Polybox_n 和 Fulladder_n 电路

表 1 记录了测试数据中电路的基本信息, |Comps|、 |Obs|、|SD|、|VAR|分别代表组件个数、观测个数、子句
个数、变量个数. 其中 Polybox 和 Fulladder 电路随着 n 的变化而变化. 对于 ISCAS-85 电路, 我们随机设置了
20–40 个故障组件, 并使用文献 [28] 中的 3 种故障类型. 每个电路共有 2 |Obs| 种观测值, 我们随机生成 100 组不同观
测变量, 表 1 的右 3 列统计了两种不同算法在 1 000 s 内能够解决的实例数占比 (如第 3 行, HSDiag 算法解决实例
的占比是 1, MCS-MHS 算法解决实例的占比也是 1, 但是在运行时间上来说, HSDiag 算法在能够解决实例的前提
下, 比 MCS-MHS 算法解决实例用时都短). 对于一些规模相对较小的电路 (c499, c1355, c880, c1908), HSDiag 算法
和 MCS-MHS 算法都能很好地解决大部分实例, 其中只有 c1355 电路, MCS-MHS 算法少量数据好于 HSDiag 算
法, 其余数据 HSDiag 算法要更有效.

表 1 电路基本信息及测试用例比较

电路基本信息 解决实例的占比 获胜占比
名称
|Comps| |Obs| |SD| |VAR| HSDiag MCS-MHS HSDiag-WIN
c499 202 73 714 445 1 1 1
c880 383 86 1 112 826 1 0.7 1
c1355 546 73 1 610 1 133 1 1 0.8
c1908 880 58 2 378 1 793 1 1 1
c3540 1 669 72 4 608 3 388 0.8 0.2 0.8
c6288 2 416 64 7 216 4 864 0.5 0 0.5
√ √
Polybox_n n 8n+9+1 3n 2n−1/2+ 2n+9/4 0.9 0.7 0.9
Fulladder_n 5n 3n+3 17n 12n+1 1 0.8 1

图 8 是 Polybox_n 和 Fulladder_n 电路示例图, 电路规模随着 n 的增大而增大. 当 n 增大时, 基本上所有电路
的求解时间都增加. 电路组件少, 生成的变量和子句个数少, HSDiag 和 MCS-MHS 算法基本上都能在 1 s 内返回
所有的解. 对于 Fulladder_6, Fulladder_10, Fulladder_14 电路, 优化效率在 1–3 个数量级之间, 而相对复杂的
Polybox 电路, 平均优化效率也在 5 倍以上.