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

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

作　　者：佘晓娓 赵相福[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《浙江师范大学学报（自然科学版）》2016年第4期399-405,共7页Journal of Zhejiang Normal University:Natural Sciences

基　　金：国家自然科学基金资助项目(61003101);浙江省自然科学基金资助项目(LY16F020004;Y1100191)

摘　　要：产生待诊断设备冲突集的所有极小碰集是基于模型诊断的一个重要步骤,极小碰集即为该设备的候选诊断.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.

关 键 词：极小碰集 基于模型诊断 极大度 极小势 碰集树 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]