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

TP18

BWSS: Boolean Algorithm with Suspicious Set Clusters for Calculating Minimal Hitting Sets
Author:
Affiliation:

Fund Project:

• 摘要
• |
• 图/表
• |
• 访问统计
• |
• 参考文献
• |
• 相似文献
• |
• 引证文献
• |
• 资源附件
• |
• 文章评论
摘要:

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

Abstract:

In the field of model-based diagnosis, all minimal hitting sets(MHS) of minimal conflict sets(MCS) 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 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.

参考文献
相似文献
引证文献

• 点击次数:
• 下载次数:
• HTML阅读次数:
##### 历史
• 收稿日期:2022-05-05
• 最后修改日期:2024-01-30
• 录用日期:
• 在线发布日期: 2024-07-03
• 出版日期: