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

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

句规模, 求解时间将大幅度缩减. 原始冲突集要是能够分成若干个互不相交的子句集, 利用等价类策略只需要求解
每个子集的诊断, 最好的情况下能使求解时间成指数级下降. 不幸的是, 因电路的每一个组件都有输入和输出, 导
致整个电路的组件通过传播变量连接在一起, 故无法进行分割. 现有的等价类策略无法对电路的 CNF 编码进行分
类, 但是考虑到诊断中只存在组件变量, 则可以进一步地分解. 接下来介绍等价类策略, 再提出一种专属求解诊断
的优化等价类策略.
定义 11. 冲突集等价类 (equivalence class, EC) [19] . 如果冲突集 F 能够分成 k 个没有交集的子句集, 则称每个子
∪
,
句集为冲突集等价类, 其中满足 F = EC i MHS(F) = & MHS(EC i ).
1⩽i⩽k 1⩽i⩽k
例 5: 利用等价类求解冲突集 F={{1, 2}, {2, 3}, {4, 5, 6}, {6, 7}, {8, 9}}.
等价类策略可以把 F 分成不相交的 3 个等价类, EC 1 ={{1, 2}, {2, 3}}, EC 2 ={{4, 5, 6}, {6, 7}}, EC 3 ={{8, 9}}.
分别计算每个等价类的极小碰集 MHS(EC 1 )={{2}, {1, 3}}, MHS(EC 2 )={{6}, {4, 7}, {5, 7}}, MHS(EC 3 )={{8}, {9}}.
MHS(F)={{2, 6, 8}, {2, 6, 9}, {2, 4, 7, 8}, {2, 4, 7, 9}, {2, 5, 7, 8}, {2, 5, 7, 9}, {1, 3, 6, 8}, {1, 3, 6, 9}, {1, 3, 4, 7, 8},
{1, 3, 4, 7, 9}, {1, 3, 5, 7, 8}, {1, 3, 5, 7, 9}}. 从而能够得到这样一个关系式 MHS(F)=MHS(EC 1 ) & MHS(EC 2 ) &
MHS(EC 3 ).
其中符号& 是笛卡尔乘积. 把问题集合簇分成等价类可以减少解集的生成, 最好情况下可以使问题的复杂度
从 2 降低到 2 k/n 次方, n 是等价类的个数.
k
在计算一个冲突集合簇的所有极小碰集时, 若一个冲突集合簇可以分成若干个等价类, 则只需计算每个等价
类的所有极小碰集. 当子句集不可分成等价类时, 对于计算碰集而言是无法继续使用等价类策略的, 而对于计算诊
断却是可以的. 这是由于编码子句集是通过传播变量 e p 进行连接 (交集), 若我们对 e p 调用分裂规则后, 剩余的编
码子句则没有任何交集, 生成的诊断解又无需扩展 e p , 可以对初始不能分等价类的编码子句间接调用等价类策略.
推论 1. 诊断等价类. 若诊断编码 F 通过选取 e p 后生成 m 个节点, 每个节点有 k j ( 1 ⩽ j ⩽ m) 个互相没有交集
的子句集 EC i (1 ⩽ i ⩽ k j ), 则称每个子句集为诊断等价类, 其中满足 HSDiag(F) = ∪ & HSDiag(EC i ).
1⩽j⩽m 1⩽i⩽k i
下面用例 6 进一步解释在诊断编码初始不可分成等价类时, 通过选取传播变量间接调用等价类策略.
例 6: 基本电路 Polybox_5 诊断编码间接调用等价类策略.
图 6 是 Polybox_5 电路示例图, 该电路转化成 CNF 编码子句时, 子句 F 是无法分成若干等价类, 但是可以通
过选取变量对子句集 F 进行分裂. 在进行分割子句集之间的连接关系时, 每个组件是由传播变量 (在电路里面充
当导线) 连接, 并且传播变量不会出现在诊断解中, 这里优先选取传播变量.

{1,−11,−12,−6},{1,11,6},{1,12,6},{2,−13,−14,−7},{2,13,7},{2,14,7},{3,−15,−16,−8},

{3,−15,8},{3,−16,8},{4,6,7,9},{4,−6,−9},{4,−7,−9},{5,7,8,10},{5,−7,−10},{5,−8,−10} F
i 11 i 6
N 1 i 9 7 −7
i 12 N 4
F 2
F 1
i 13 i 7
N 2 {1,−11,−12,−6},{1,11,6},{1,12,6},{2,−13,−14},{3,−15,−16,−8}, {1,−11,−12,−6},{1,11,6},{1,12,6},{2,13},{2,14},{3,−15,−16,−8},
i 14
{3,−15,8},{3,−16,8},{4,−6,−9},{4,−9},{5,−10},{5,−8,−10} {3,−15,8},{3,−16,8},{4,6,9},{4,−6,−9},{5,8,10},{5,−8,−10}
i 10
i 15 i 8
N 5 等价类分解 等价类分解
N 3
i 16
{1,−11,−12,−6},{1,11,6},{1,12,6},{4,−6,−9},{4,−9} {1,−11,−12,−6},{1,11,6},{1,12,6},{4,6,9},{4,−6,−9}
EC 1 EC 4
电路 Polybox_5 EC 2 {2,−13,−14} {2,13},{2,14} EC 5
EC 3 {3,−15,−16,−8},{3,−15,8},{3,−16,8},{5,−10},{5,−8,−10} {3,−15,−16,−8},{3,−15,8},{3,−16,8},{5,8,10},{5,−8,−10} EC 6
图 6 Polybox_5 电路示例图

当一个组件被设计出来时, 内部结构是已知的, MBD 编码的过程及如何把编码子句集合理分割是可以离线获
得的. 对于图 5, 显然选取 i 7 (相当于切断 i 7 这根导线) 是一个合理的选择. 根据分裂规则, 选取传播变量 7 和−7 后,
∪ ∪
左分支 F 1 = EC i , 右分支 F 2 = EC i , 每个 EC i 分别调用 HSDiag 算法, 可以间接获得所有解, 根据推论 1 得
1⩽i⩽3 4⩽i⩽6
∪
HSDiag(F) = & HSDiag(EC i ), 即 HSDiag(F) = & HSDiag(EC i )∪ & HSDiag(EC i ). 而碰集算法需要归并所
1⩽j⩽m 1⩽i⩽k i 1⩽i⩽3 4⩽i⩽6
有的变量, 并且合并的解集需要复杂的极小化, 即 MHS( f) = min{7∪ & MHS(EC i )}∪{−7∪ & MHS(EC i )}}.
1⩽i⩽3 4⩽i⩽6
可见优化的变种碰集算法在原始问题子句集不可分的情况下, 对传播变量进行分裂仍然可以使用等价类策