用MDMC-HS-tree方法计算极小碰集

On computing the minimal hitting sets by MDMC-HS-tree

产生待诊断设备冲突集的所有极小碰集是基于模型诊断的一个重要步骤,极小碰集即为该设备的候选诊断.HS-tree算法产生的节点数目较多,效率较低.因此,提出了基于极大度和极小势的MDMC-HS-tree方法.每次选择势最小的集合进行扩展,以便减小树的宽度;并删减包含势最小集合中度最大元素的集合,不断将大问题化简为小问题.实验结果表明:本算法能够产生所有极小碰集,且在计算大规模碰集时产生相对较少的节点,为实际设备故障诊断提供较可行的方法.

Computing minimal hitting-sets （MHSes） based on all conflicts was an important step in model- based diagnosis. Reiter first proposed the HS-tree algorithm for computing MHSes. Generally, a large number of nodes were generated in an HS- tree. In order to improve the algorithm, a method of MDMC-HS- tree（Max- Degree-Min-Cardinality-based Hitting- Sets- tree） was proposed to compute MHSes for all conflict sets. Firstly, the set with minimal cardinality was selected from the current conflict set cluster to be expanded, so as to reduce the width of the tree. Then, the largest degree element in the minimal cardinality set was chosen to reduce current conflict set cluster. Experimental results showed that the algorithm generated all MHSes and produced a smaller number of nodes even for a large number of conflict sets. The algorithm was feasible for computing all MHSes in model-based diagnosis.