用布尔代数方法计算最小碰集  

The Computation of Hitting Sets with Boolean Formulas

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

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

出　　处：《计算机学报》2003年第8期919-924,共6页Chinese Journal of Computers

基　　金：国家自然科学基金 (60 173 0 3 9;60 2 0 3 0 15 );国家教育部博士点基金(2 0 0 10 5 5 80 0 6);广东省自然科学基金 (0 11162 );教育部科学技术研究重点项目;广州市科技计划项目资助

摘　　要：在基于模型的诊断中 ,模型一般都是用布尔代数来表示 ,而计算碰集 (hittingsets)则采用HS 树或图 ,这就使得诊断系统采用多种不同的数据结构 ,给编程实现带来了不便 .本文用布尔代数变量表示待诊断系统的部件 ,并给出了用布尔代数直接计算最小碰集的算法 .数据结构更为简单 ,只需要布尔表达式 ,相当于字符串 ,效率上比其他的一些研究结果也要好 ,同时可克服丢失正确解的问题 。In model-based diagnosis,the system is described by Boolean logic,but the hitting sets are computed with HS-TREE or DAG,so the data structures of diagnosis system were composed of many descriptions. In this paper,both the components and system description are represented as Boolean variables. And the Boolean algebra algorithm is presented to compute hitting sets. The efficiency of this algorithm is better than the other works,data structures are simpler,and the correct answers are not lost. This algorithm could be used more widely.

关 键 词：人工智能 布尔代数方法 计算 最小碰集 模型诊断 最小冲突集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]