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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(12):5537−5553 [doi: 10.13328/j.cnki.jos.007397] [CSTR: 32375.14.jos.007397] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
HSDiag: 变种碰集算法求解诊断

欧阳继红 1,2 , 黄 森 1,2

1
(吉林大学 计算机科学与技术学院, 吉林 长春 130012)
(符号计算与知识工程教育部重点实验室 (吉林大学), 吉林 长春 130012)
2
通信作者: 黄森, E-mail: hs_huangs@163.com

摘 要: 在基于模型诊断领域中, 首先对系统描述进行编码, 利用成熟的 SAT 求解器获得所有极小冲突集, 最后计
算极小冲突集的极小碰集, 即待诊断设备的候选诊断. 然而这种策略花费大量的时间, 相当于计算两个 NP-hard 问
题, 即计算极小冲突集和极小碰集. 对电路系统描述重新编码, 提出一种变种碰集算法 HSDiag, 该算法可以直接对
编码进行计算来获得诊断. 在与目前最先进的求解冲突集再求解碰集的诊断算法相比, 效率最高提升 5–100 倍. 随
着电路组件的增多, 编码子句呈线性增加, 诊断数量呈指数级增加. 因为求解大规模电路 (ISCAS-85) 的所有冲突集
不切实际, 所以在设置相同的截止时间内, 提出的 HSDiag 算法与基于冲突集的诊断算法相比多求出 1 倍以上的解
集. 除此之外, 提出一种专属求解诊断的等价类优化策略, 就算在初始冲突集不可分割的情况下, 利用新提出的集
合分裂规则能够对冲突集进一步分解. 在标准的 Polybox 和 Fulladder 电路中, 使用等价类优化后的 HSDiag 算法,
效率进一步提升 2 倍以上.
关键词: 基于模型诊断; 系统描述; 极小冲突集; 极小碰集; 等价类
中图法分类号: TP181

中文引用格式: 欧阳继红, 黄森. HSDiag: 变种碰集算法求解诊断. 软件学报, 2025, 36(12): 5537–5553. http://www.jos.org.cn/1000-
9825/7397.htm
英文引用格式: Ouyang JH, Huang S. HSDiag: Variant Hitting Set Algorithm for Solving Diagnosis. Ruan Jian Xue Bao/Journal of
Software, 2025, 36(12): 5537–5553 (in Chinese). http://www.jos.org.cn/1000-9825/7397.htm

HSDiag: Variant Hitting Set Algorithm for Solving Diagnosis
1,2
OUYANG Ji-Hong , HUANG Sen 1,2
1
(College of Computer Science and Technology, Jilin University, Changchun 130012, China)
2
(Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education (Jilin University), Changchun 130012,
China)
Abstract: In the field of model-based diagnosis, the system description is first encoded, and all minimal conflict sets are obtained using a
mature SAT solver. Finally, the minimal hitting set of the minimal conflict sets is computed as the candidate diagnosis for the equipment
to be diagnosed. However, this strategy consumes a significant amount of time, as it is equivalent to solving two NP-hard problems:
computing the minimal conflict set and the minimal hitting set. This study re-encodes the description of the circuit system and proposes a
novel variant hitting set algorithm, HSDiag, which can directly compute the diagnosis from the encoding. Compared to state-of-the-art
diagnosis algorithms that first solve conflict sets and then hitting sets, the efficiency improves by a factor of 5 to 100. As the number of
circuit components increases, the encoding clauses increase linearly, while the number of diagnoses increases exponentially. Since solving
all conflict sets of large-scale circuits (ISCAS-85) is impractical, the proposed HSDiag algorithm, within the same cutoff time, yields more
than twice the number of solutions compared to conflict-set-based diagnosis algorithms. In addition, this study proposes an equivalence
class optimization strategy, which further decomposes the conflict set by using the newly proposed set splitting rule, even if the initial

* 基金项目: 吉林省煤炭洁净燃烧技术的环境保护装备项目 (3D516L921421)
收稿时间: 2023-11-06; 修改时间: 2024-05-15; 采用时间: 2025-01-13; jos 在线出版时间: 2025-06-11
CNKI 网络首发时间: 2025-06-11