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

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

0.1 10
MCS-MHS MCS-MHS
HSDiag HSDiag
1
0.01 0.1
运行时间 (s) 0.001 运行时间 (s) 0.01

0.001

0.000 1 0.000 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
组件数 n 组件数 n
(a) Fulladder_6 电路 (b) Fulladder_10 电路
1 0.100
MCS-MHS
HSDiag
0.1
运行时间 (s) 0.01 MCS-MHS 运行时间 (s) 0.010

0.001 HSDiag

0.000 1 0.001
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
组件数 n 组件数 n
(c) Fulladder_14 电路 (d) Polybox_6 电路
10 100
MCS-MHS MCS-MHS
HSDiag 10 HSDiag
1 1
运行时间 (s) 0.01 运行时间 (s) 0.1
0.1

0.001 0.01
0.001
0.000 1 0.000 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
组件数 n 组件数 n
(e) Polybox_8 电路 (f) Polybox_10 电路
图 8 HSDiag 与 MCS-MHS 算法在 Polybox, Fulladder 电路实验比较

图 9 是在国际基准 ISCAS-85 电路 [24,28,29] 进行求解, 对于该大规模电路, 因在有限的时间内很难求出所有的解,
故算法截止时间设计为 1 000 s, 横坐标表示电路实例数, 纵坐标表示求解的诊断数. 在所有的电路中, HSDiag 算法
求解诊断个数明显多于 MCS-MHS 算法, 对于更大的电路 c880, c3540, c6288, 基于冲突集计算所有诊断的 MCS-
MHS 算法在某些情况下求出的解集更少, 甚至求不出来任何解. 这是求解大规模电路的所有极小冲突集是耗时严
重的, 而计算出部分冲突集的极小碰集不一定能够满足多故障系统观测. 除了 c6288 电路外, 基本上所有的电路都
6
求到 2×10 左右个解. c6288 电路中 88.1% 的组件都是异或门, 在对系统进行编码时, 每个电路门都会生成 4 个子
句, 并且该电路的输入输出也较少, 对观测进行单元传播时, 删除的子句少, 剩余的子句多, 导致整体求解困难, 仅
4
求出约 3.5×10 个解.