A method of combining HSSE-tree and binary label to compute all minimal hitting sets

摘要：

Computing all minimal hitting sets (MHSs) is a key step of model-based diagnosis. A novel method to compute all MHSs called Binary-label HSSE is put forward, which combines HSSE-tree and binary label. In the method, binary digits is used to mark the real elements of the nodes, and effective pruning and expanding strategies are used to avoid the main problem of HSSE-tree, the explosive growth of the expanded nodes and supersets of MHSs along with the dimension of the problems. Additionally, computing between binary digits can avoid the traverse of every element in a node when judging whether the node is a MHS, which also contributes to the significant decrease of the run time. At last, the data structure of Binary-label HSSE is changed to dynamic array from dynamic linked list, which further decreases the run time of the method. Simulation results show that Binary-label HSSE method costs much less space and time than HSSE-tree method.

关键词： Binary label Minimal hitting set Model-based diagnosis

作者: Wenquan Feng Min Du Qi Zhao Dong Wang

作者单位: School of Electronic and Information Engineering Beihang University Beijing, China

会议类型: 国际会议

会议名称: 2011 Fourth International Symposium on Computational Interlligence and Design 第四届计算智能与设计国际会议 ISCID 2011

会议地点: 杭州

会议语种:英文

页码: 403-406

在线出版日期: 2011-10-28（万方平台首次上网日期，不代表论文的发表时间）