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

• 作者: 姜云飞 林笠
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 基于模型诊断 最小冲突集 最小碰集 对分HS-树
• 年，卷（期）: 2002,（12）
• 页码范围: 2267-2274
• 页数: 8页
• 分类号: TP18
• 字数: 5405字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林笠	中山大学软件研究所	13	247	9.0	13.0
3	姜云飞	中山大学软件研究所	84	1013	18.0	28.0