文献类型：期刊文章

作　　者：姜云飞[1] 林笠[1,2]

机构地区：[1]中山大学软件研究所 [2]暨南大学数学系,广东广州510632

出　　处：《软件学报》

基　　金：国家自然科学基金资助项目(69873047;60173039);广东省自然科学基金资助项目(980260)

年　　份：2002

卷　　号：13

期　　号：12

起止页码：2267-2274

语　　种：中文

收录情况：AJ、BDHX、BDHX2000、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI(收录号：2003187454097)、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

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

关 键 词：模型诊断  最小冲突集 最小碰集 对分HS-树  人工智能 推理理论  

分 类 号：TP18]