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

5550 软件学报 2025 年第 36 卷第 12 期

20 20
MCS-MHS MCS-MHS
HSDiag 15 HSDiag
诊断解个数 (×10 5 ) 10 5 诊断解个数 (×10 5 ) 10 5
15

0 0
100 200 300 400 500 600 700 800 900 100 200 300 400 500 600 700 800 900
电路截止时间 (s) 电路截止时间 (s)
(a) c499 (b) c1355
20 25
MCS-MHS MCS-MHS
HSDiag 20 HSDiag
诊断解个数 (×10 5 ) 10 5 诊断解个数 (×10 5 ) 15
15

10

0 5 0
100 200 300 400 500 600 700 800 900 100 200 300 400 500 600 700 800 900
电路截止时间 (s) 电路截止时间 (s)
(c) c1908 (d) c880
1.5 50
MCS-MHS MCS-MHS
HSDiag HSDiag
40
诊断解个数 (×10 5 ) 0.5 诊断解个数 (×10 5 ) 30
1.0
20

0 10 0
100 200 300 400 500 600 700 800 900 100 200 300 400 500 600 700 800 900
电路截止时间 (s) 电路截止时间 (s)
(e) c3540 (f) c6288
图 10 HSDiag 与 MCS-MHS 算法在 ISCAS-85 电路实验比较

3.2 等价类优化
在图 7 中, 虚线给出了等价类的切割位置, 对于 Polybox_(n+2)(n–1)/2 电路, 从左往右第 i 列组件个数为 n+1–i,
第 i 列与第 i+1 列之间变量 (导线) 的个数为 n+1–i. 也就是说, 如果从第 i 列和第 i+1 列切割电路, 那么需要选取
n+1–i 个变量. Fulladder_n 电路可以看成是由 n 个 Fulladder_1 组成, 只不过第 i 个电路的输出是第 i+1 个电路其中
的一个输入, 可见分割 Fulladder_n 电路只需要选取中间的连接变量.
图 11 是 HSDiag 算法在 Fulladder_n 电路进行等价分类, 其中|EC|=1 代表没有使用等价类策略, |EC|=8 代表把
电路编码均分成 8 个等价类. Fulladder 电路结构简单, 能够容易的划分等价类, 在每次分割时, 分割后等价类没有
k
交集, 相当于对称分割, 即|EC|=2 时, 只需要选取 k 个传播变量 (从图 7 也可以看出). 在分解等价类时, 需要对选取
的变量进行赋值, 然赋值过程中就已经相当于求解. 我们把分解等价类选取变量阶段放到离线, 即获取分割点是在
对系统编码时获取, 在算法开始阶段, 直接当作参数直接调用. 在 n=1000 时, 编码的变量及诊断解的个数较少, 所
以整体求解效率较快, 平均 0.2 s 内就能够返回所有的解. |EC|=8 时, 比没有调用等价类策略的 HSDiag 算法, 效率
提升约 5 倍. 而 n=16000 时, 编码整体规模较大, 求解时间都在 100 s 以上, 使用等价类策略后, 大幅度缩减编码规