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

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

模, 效率最高提升 40 倍.
图 12 显示在复杂电路 Polybox 中生成两个等价类, k 代表选取变量的个数, 等于 0 时表示没有使用等价类策
略. 在分割小规模的电路时, 虽然使用等价类策略对电路进行缩减, 但是也分成了 2 个集合簇, 而每个集合簇的求
k
解时间相似, 当等价类获得收益较小时, 即部分集合簇解集较少甚至无解, k 值越大反而求解的时间不一定越小.
在 Polybox_54 中, k=6 时整体求解效率要好于 k=5, 7, 比 k=0 时平均提升一个数量级. 在 Polybox_90 电路中, 使用
等价类策略的 HSDiag 算法求解时间都明显缩减, 因随着 k 的增大等价类分解的组件个数也逐渐均衡, 故求解时
间也随着降低. 特别是对于第 7–15 个实例, k=8 比 k=0 平均提升一个数量级以上. 同样的, 在第 1–4 个实例中并不
是 k=8 最好, 一些系统观测值大部分满足了理论值, 使得生成的解集较少, 甚至大量子句集产生的解都是冗余的,
整体求解时间相对较慢.

0.20 1 000
|EC|=1 |EC|=4
|EC|=8 |EC|=2
0.15 |EC|=1 |EC|=4 100
运行时间 (s) 0.10 |EC|=8 |EC|=2 运行时间 (s)

0.05 10

0 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
等价类分类 等价类分类
(a) Fulladder_1000 (b) Fulladder_16000
图 11 在 Fulladder 电路中的等价类比较

10 1 000
k=0 k=0
k=7 k=8
k=6 800
1 k=7
k=5 600 k=6
运行时间 (s) 0.1 运行时间 (s) 400

0.01
200
0.001 0
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
等价类分类 等价类分类
(a) Polybox_54 选取 k 个变量分成等价类 (b) Polybox_90 选取 k 个变量分成等价类
图 12 在 Polybox 电路中的等价类比较

4 总 结

基于模型诊断是根据待诊断的系统的内部结构编码成 CNF 子句, 通过一致性检测来确定故障组件的位置. 利
用 SAT 求解器先求出极小冲突集再求出极小碰集. 这种策略虽然可以获得诊断, 但是耗时严重, 并且因求出所有
极小冲突集是不切实际的, 故获得的诊断并不精确. 本文利用极大可满足子集与极小修正集的互补性, 提出一种变
种碰集算法 HSDiag. 该算法能够直接获得候选诊断, 和目前性能最优间接求诊断的算法相比, 在求解效率及诊断
的数量上都有明显的优化, 运行时间有 5–100 倍的提升, 诊断数量能多获得 1 倍以上. 为了在更大规模的电路上有
效, 本文又提出一种用于求解候选诊断的等价类策略, 它能够大幅度缩减编码子句的数量, 在本文所提算法的基础
上, 运行时间进一步提升 2 倍以上.