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

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

Computing Minimal Hitting Set from First Principles with RHS -tree

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.