用对分hs-树计算最小碰集

在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在reiter的方法中,要用hs-树(图)来计算最小冲突集的最小碰集.hs-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出了用对分hs-树(binaryhittingset-树,简称bhs-树)计算最小碰集的方法.这种方法的优点是:(1)产生的树的节点数明显少于hs-树,因而效率较高;(2)解决了因为剪枝而产生的最小碰集丢失的问题;(3)在新增加冲突集时不必完全重新计算,只需在原bhs-树