软件学报

作者：赵相福，黄森，魏霞，童向荣，欧阳丹彤，张立明

单位：赵相福，烟台大学 计算机与控制工程学院, 山东 烟台 26400511,黄森，浙江师范大学 计算机系, 浙江 金华 32100402,魏霞，烟台大学 计算机与控制工程学院, 山东 烟台 26400503,童向荣，烟台大学 计算机与控制工程学院, 山东 烟台 26400504,欧阳丹彤，吉林大学 计算机科学与技术学院, 吉林 长春 13001205,张立明，吉林大学 计算机科学与技术学院, 吉林 长春 13001206

关键词：基于模型诊断;极小碰集;Boolean算法;候选解;冲突集

基金：国家自然科学基金(61972360, 62076108, 62072392)

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

来源：2025年第7期

《软件学报》期刊编辑部

查看软件学报杂志2025年第7期