递归建立HS-树计算最小碰集

Computing minimal hitting set from first principles with RHS-tree

在基于模型的诊断中,广泛地使用冲突集来计算最小碰集的算法诊断。现有的HS-树,HST-树,BHS-树等算法普遍存在实现的困难。文章提出用递归算法建立平衡的二叉HS-树(Recursivehittingset-树,简记为RHS-树)计算最小碰集的方法,在空间复杂性与时间复杂性上能够满足大多数诊断系统中的要求。

In model-based diagnosis,there is widely used to compute the minimal hitting sets of conflict sets. There are HS-tree,HS-DAG,HST-tree,etc. but all of these methods are difficult to be programmed. This paper puts forward a new method to compute the minimal hitting sets by constructing balanced binary tree recursively,in brief,RHS-tree. The improvements of this algorithm are:1)It need recursive algorithm only and is easy to be programmed. 2)As a result of being pruned,the loss of the minimal hitting sets will not produce;3)When the new conflict sets are inserted,it is unnecessary to rebuild RHS-tree,instead,just adding the new branches to the RHS-tree. The comparison between RHS-tree and the others is given also.