| 摘要: |
| 在基于模型的诊断领域中, 因为极小冲突集 (minimal conflict set, MCS) 的极小碰集 (minimal hitting set, MHS) 即为待诊断设备的候选诊断, 所以计算极小碰集是候选诊断的一个关键步骤. 其中, 极小碰集是一个NP-hard约束求解问题, 随着问题规模增大, 求解难度成指数级增长. Boolean算法是计算极小碰集的经典算法, 然在求解过程中, 解集的极小化却占据运算的绝大部分时间. 为了解决该问题并提升计算效率, 提出了结合可疑集合簇计算极小碰集的BWSS (Boolean with suspicious sets) 算法, 通过深度分析Boolean算法生成树规则, 找到使候选解成为超集的集合, 在向根节点扩展元素时, 如果候选解与可疑集合簇中至少1个集合交集为空, 那么该解为极小候选解, 否则删除该解, 通过递归的策略保证算法结束时产生且仅产生所有极小碰集. 除此之外, 每个候选解在极小化时, 至少存在m (m$ \geqslant $1)个元素甚至整个解无须极小化. 理论上, BWSS算法的复杂度要远低于Boolean算法. 通过随机数据及大量基准电路数据, 实验结果表明, 所提算法与目前最先进的几种算法相比, 运行时间减少了几个数量级. |
| 关键词: 基于模型诊断 极小碰集 Boolean算法 候选解 冲突集 |
| DOI：10.13328/j.cnki.jos.007227 |
| 分类号:TP18 |
| 基金项目:国家自然科学基金(61972360, 62076108, 62072392) |
|
| BWSS: Boolean Algorithm with Suspicious Set Clusters for Calculating Minimal Hitting Sets |
|
ZHAO Xiang-Fu1, HUANG Sen2, WEI Xia1, TONG Xiang-Rong1, OUYANG Dan-Tong3, ZHANG Li-Ming3
|
|
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 all and only MHS are generated at the end of the algorithm. In addition, each candidate solution has at least m (m≥1) elements or even the entire solution in no need of complex minimization. Theoretically, BWSS algorithm is far less complex than Boolean algorithm. According to random data and mass reference circuit data, experimental results show that compared with many other state-of-the-art methods, the proposed algorithm reduces several orders of magnitude in runtime. |
| Key words: model-based diagnosis minimal hitting set Boolean algorithm candidate solution conflict set |
