用CHS-tree基于集合势的方法计算极小碰集  

Computing minimal hitting sets with CHS-tree method

作　　者：王肖[1] 赵相福[1] 

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

出　　处：《计算机集成制造系统》2014年第2期401-406,共6页Computer Integrated Manufacturing Systems

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

摘　　要：在基于模型的故障诊断理论中,为了根据所有冲突部件集计算全体极小碰集,提出基于集合势的方法,每次选择当前集合簇中势最小的集合进行扩展,并借助集合簇中元素出现的频率作为辅助判断,不断将大问题逐渐分解成子问题,然后依次求出不包含该扩展集合中各元素的集合簇的所有极小碰集。实验结果表明,CHStree方法生成树的过程较简单,能产生较少的节点,比经典的碰集树方法、二分法和集合枚举法等具有更高的求解效率。在某些情况下,其效率也高于当前效率最高的Boolean方法。In model-based diagnosis theory, a Cardinality-based Hitting Set-tree （CHS-tree） method was put forward to compute the whole Minimal Hitting-Sets （MHSs） according to all conflicts. The smallest cardinality set was se- lected from the current conflict set cluster to be expanded, and the frequency of the element occurrence was consid- ered as an auxiliary condition to decompose the big problem into some sub-problems. All the MHSs of the set cluster which did not contain any element in the expansion set were computed as well. Experimental results showed that the proposed method had easier process and fewer nodes. Compared with the classical HS-tree method, BHS-tree and HSSE-tree method, this method had higher efficiency. In some cases, its efficiency was higher than the current most efficient Boolean method.

关 键 词：基于模型的诊断 极小冲突集 极小碰集 碰撞树 

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