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

被引：41

作者：

姜云飞

林笠

机构：

[1] 中山大学软件研究所

[2] 中山大学软件研究所广东广州

[3] 暨南大学数学系

[4] 广东广州

来源：

软件学报 | 2002年 / 12期

基金：

广东省自然科学基金;

关键词：

基于模型诊断; 最小冲突集; 最小碰集; 对分HS-树;

D O I：

10.13328/j.cnki.jos.2002.12.008

中图分类号：

TP181 [自动推理、机器学习];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在Reiter的方法中,要用HS-树(图)来计算最小冲突集的最小碰集.HS-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出了用对分HS-树(binary hitting set-树,简称BHS-树)计算最小碰集的方法.这种方法的优点是:(1)产生的树的节点数明显少于HS-树,因而效率较高;(2)解决了因为剪枝而产生的最小碰集丢失的问题;(3)在新增加冲突集时不必完全重新计算,只需在原BHS-树的基础上增加新的分支即可,这种性质对实际诊断问题是特别有用的.对利用BHS-树的算法从理论上进行了分析和论证,并通过实际编写程序进行了检验.

引用

页码：2267 / 2274

页数：8