Page 305 - 《软件学报》2025年第7期

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

*
BWSS: 结合可疑集合簇计算极小碰集的 Boolean 算法

赵相福 1 , 黄 森 2 , 魏 霞 1 , 童向荣 1 , 欧阳丹彤 3 , 张立明 3

1
(烟台大学 计算机与控制工程学院, 山东 烟台 264005)
2
(浙江师范大学 计算机系, 浙江 金华 321004)
3
(吉林大学 计算机科学与技术学院, 吉林 长春 130012)
通信作者: 赵相福, E-mail: xiangfuzhao@163.com

摘 要: 在基于模型的诊断领域中, 因为极小冲突集 (minimal conflict set, MCS) 的极小碰集 (minimal hitting set,
MHS) 即为待诊断设备的候选诊断, 所以计算极小碰集是候选诊断的一个关键步骤. 其中, 极小碰集是一个 NP-
hard 约束求解问题, 随着问题规模增大, 求解难度成指数级增长. Boolean 算法是计算极小碰集的经典算法, 然在求
解过程中, 解集的极小化却占据运算的绝大部分时间. 为了解决该问题并提升计算效率, 提出了结合可疑集合簇计
算极小碰集的 BWSS (Boolean with suspicious sets) 算法, 通过深度分析 Boolean 算法生成树规则, 找到使候选解成
为超集的集合, 在向根节点扩展元素时, 如果候选解与可疑集合簇中至少 1 个集合交集为空, 那么该解为极小候选
解, 否则删除该解, 通过递归的策略保证算法结束时产生且仅产生所有极小碰集. 除此之外, 每个候选解在极小化
时, 至少存在 m (m ⩾ 1) 个元素甚至整个解无须极小化. 理论上, BWSS 算法的复杂度要远低于 Boolean 算法. 通过
随机数据及大量基准电路数据, 实验结果表明, 所提算法与目前最先进的几种算法相比, 运行时间减少了几个数量级.
关键词: 基于模型诊断; 极小碰集; Boolean 算法; 候选解; 冲突集
中图法分类号: TP18

中文引用格式: 赵相福, 黄森, 魏霞, 童向荣, 欧阳丹彤, 张立明. BWSS: 结合可疑集合簇计算极小碰集的Boolean算法. 软件学报,
2025, 36(7): 3226–3238. http://www.jos.org.cn/1000-9825/7227.htm
英文引用格式: Zhao XF, Huang S, Wei X, Tong XR, Ouyang DT, Zhang LM. BWSS: Boolean Algorithm with Suspicious Set Clusters
for Calculating Minimal Hitting Sets. Ruan Jian Xue Bao/Journal of Software, 2025, 36(7): 3226–3238 (in Chinese). http://www.jos.org.
cn/1000-9825/7227.htm

BWSS: Boolean Algorithm with Suspicious Set Clusters for Calculating Minimal Hitting Sets
1
2
3
1
1
ZHAO Xiang-Fu , HUANG Sen , WEI Xia , TONG Xiang-Rong , OUYANG Dan-Tong , ZHANG Li-Ming 3
1
(School of Computer and Control Engineering, Yantai University, Yantai 264005, China)
2
(Department of Computer, Zhejiang Normal University, Jinhua 321004, China)
3
(College of Computer Science and Technology, Jilin University, Changchun 130012, China)
Abstract: In the field of model-based diagnosis, all minimal hitting sets (MHSs) of minimal conflict sets (MCSs) are the candidate
diagnoses of the device to be diagnosed, so the calculation of MHS is a key step for generating candidate diagnoses. MHS is a classic NP-
hard constraint solving problem. The bigger the problems get, the harder it becomes exponentially to solve them. Boolean algorithm is
typical in calculating MHS. However, in the process of solving, most of the runtime is taken up by the minimization of the intermediate
solution sets. This study proposes BWSS (Boolean with suspicious sets) algorithm combined with suspicious set clusters for calculating
MHS. By analyzing the spanning tree rule of Boolean algorithm in depth, the set that causes the candidate solution to become a superset
is found. When extending elements to the root node, the candidate solution, if discovered to share at least one empty set with the
suspicious set cluster, shall be minimal. Otherwise, the solution will be removed. The recursive strategy will be employed to ensure that

* 基金项目: 国家自然科学基金 (61972360, 62076108, 62072392)
收稿时间: 2022-05-05; 修改时间: 2024-01-30; 采用时间: 2024-05-15; jos 在线出版时间: 2024-07-03
CNKI 网络首发时间: 2024-07-12