A method of combining SE-tree to compute all minimal hitting sets

被引:21
作者
ZHAO Xiangfu and OUYANG Dantong School of Computer Science and Technology Jilin University Changchun China [130012 ]
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education Changchun China [130012 ]
机构
关键词
model-based diagnosis; conflict set; minimal hitting set; set enumeration tree;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
<正>In model-based diagnosis, the candidate diagnostic results are generally characterized by all minimal hitting sets for the collection of all conflict sets. In this paper, a new method is proposed to judge a hitting set by the number of conflict sets corresponding to components, and the computing procedure is formalized by combining revised SE-tree (set enumeration tree) with closed nodes to generate all minimal hitting sets. Results show that because closed nodes are added into SE-tree, the search efficiency is highly improved. Furthermore, the proposed method is easy to be understood and implemented. Compared with other effective algorithms with completeness in some experimental tests, the diagnosis efficiency of our proposed method is higher, particularly for single- and double-fault diagnosis.
引用
收藏
页码:169 / 174
页数:6
相关论文
共 2 条
[1]  
A variant of Reiter’s hitting-set algorithm. Wotawa F. Information Processing Letters . 2001
[2]  
A theory of diagnosis from first principles. Reiter R. Artificial Intelligence . 1987