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

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

略. 而传统的碰集算法在对不可分的子句集使用等价类策略时, 会额外增加对全集解集的极小化时间.
算法 2 是 HSDiag 算法结合等价类策略求解诊断, 初始时利用待诊断组件结构得到要分割子句的所有变量集
合 E. 根据系统描述对观测进行单元传播, 生成的子句集做一个整体存入 CluseF 中, 此时大小为 1 (第 1 行).
CluseF 对选取的变量进行集合分裂, 生成子句集 F l , F r 存入临时变量 Temp_F 中, 继续集合分裂 (第 2–10 行). CluseF
中所有的子句集进行等价类分解存入 EC_Arr 中 (第 12, 13 行), 其中等价类分解采用文献 [15] 中 Distribution
算法. 接着对每一个等价类调用 HSDiag 算法, 并对等价类生成的解集笛卡尔乘积 (第 14, 15 行), 最后合并每一个
子句集中的解集 (第 16 行).
算法 2. HSDiag with equivalence class.

输入: 系统描述 SD, 系统观测 Obs, 组件 Comps, 变量集合 E={e 1 , e 2 ,…, e m };
输出: 诊断 D.
← SD. 单元传播 (Obs);
1. CluseF
2. FOR (i=1; i ⩽ m; ++i){
⩽ CluseF.size; ++j){
3. FOR (j=1; j
4. IF ( ∃ e i ∈ F j , F j ∈ CluseF){ //如果子句集中含有该变量, 调用集合分裂规则
5. F l ← {S i −{–e i }|S i ∈ F j ∧ e i < S i };
6. F r ← {S i −{e i }|S i ∈ F j ∧ −e i < S i };
7. Temp_F ← Temp_F ∪ F l ∪ F r ; //Temp_F 是一个临时变量
8. }
9. }
10. CluseF.clear; CluseF ← Temp_F; Temp_F.clear;
11. }
12. FOR ( ∃ F j , F j ∈ CluseF){
13. EC_Arr ← Distribution(F j ); //等价类分解
14. FOR ( ∃ EC i , EC i ∈ EC_Arr) //对等价类进行笛卡尔乘积
15. D_Arr ← D_Arr & HSDiag(EC i );
16. D ← D ∪ D_Arr;
17. }

在分成等价类的过程中, 合理的分断点能够快速提升优化效率. 而在分割电路时, 若选取的传播变量较多, 那
么相当于枚举大部分的解集, 反而牺牲了碰集算法本身的启发式策略带来的优化. 对待诊断组件进行诊断编码是
已知组件内部结构, 先合理的离线分割等价类是可行的. 算法 2 的第 14, 15 行时间复杂度分析如下.
n
设 n 代表编码子句中集合的个数, 没有使用等价类策略时生成诊断解 O(2 ). 等价类分解时需要选取 m 个变
m
量, 最坏情况下生成 2 个子句集, 每个子句集分成 k 个等价类. 则通过等价类分解需要求出诊断解为 O(2 m+(n−m)/k ).
n
最坏情况下 2 /2 m+(n−m)/k ⩽ 1, 得出 (n–m)(1/k–1) ⩾ 0, 当 k=1 时, 选取 m 个变量没有分割成等价类, 时间复杂度
n
T=O(2 ); 最好情况下 m=0, k=n, 子句集中所有子句都可以独立为等价类, T=O(n). 一些其他情况:
n/2
m=2, k=2, T=O(2×2 );
3
n/4
m=4, k=4, T=O(2 ×2 );
n/6
5
m=6, k=6, T=O(2 ×2 );
…
m
n
由时间复杂度分析, 当解集 2 ≫ 2 时, 选取变量越少, 分成的等价类越多, 则优化越明显; 反之, 选取变量越
多, 分成的等价类越少, 则等价类带来的收益就越小.