IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法

IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking

基于模型的诊断推理是人工智能领域的一个重要分支.其中由冲突部件集产生所有极小碰集是基于模型诊断推理的重要一步.根据布尔算法的特征,所有的冲突集可以划分为左右两个子集合簇,且左分支集合簇恰好为右分支集合簇的子集,这为由左分支增量产生右分支极小碰集提供了理论基础;另外,在自底向上增量归并元素的过程中,结合局部独立覆盖策略可以直接增量产生所有的极小碰集,从而避免非极小碰集和相同极小碰集的冗余产生.理论上,右分支解集可由左分支解集增量方法产生,避免了碰集中大量元素的重复计算.大量实验结果表明:本文提出的算法比之前的布尔算法及相关改进算法都具有显著的效率提升,最高可达约5倍.

Model-based diagnostic reasoning is an important research branch in the field of artificial intelligence.Generating all minimal hitting-sets(MHSs)from conflict sets is a crucial step in the process of model-based diagnostic reasoning.To solve this problem,all conflict sets are divided into left and right parts according to the Boolean algorithm,and the left cluster is just a subset of the right one,which provides a theoretical foundation for incrementally generating the right MHSs from the left ones.In addition,in the process of incrementally merging branch elements from bottom to top,with the help of the local independence cover checking strategy,all MHSs can be directly produced without generating any redundant non-MHSs and duplicated MHSs.Theoretically,the right branch solution can be incrementally generated by the left one.Experimental results show that the efficiency of the proposed algorithm is significantly improved by about five times,compared with the classical algorithm based on Boolean algorithm and its related improved algorithms.