ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (3): 588-595.doi: 10.7544/issn1000-1239.2015.20131478

• 人工智能 • 上一篇    下一篇

利用CSP求解极小碰集的方法

王艺源,欧阳丹彤,张立明,张永刚   

  1. (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (yiyuanwangjlu@126.com)
  • 出版日期: 2015-03-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61133011,61272208,61003101,61170092,61402196);吉林省科技发展计划基金项目(20101501,20140520067JH);中国博士后科学基金项目(2013M541302);浙江师范大学计算机软件与理论省级重中之重学科开放基金项目(ZSDZZZZXK12)

A Method of Computing Minimal Hitting Sets Using CSP

Wang Yiyuan, Ouyang Dantong, Zhang Liming, Zhang Yonggang   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
  • Online: 2015-03-01

摘要: 基于模型诊断是人工智能领域中具有挑战性的问题,包含了很多人工智能中的关键问题,其研究对整个人工智能领域起着重要推动作用.在基于模型诊断中,候选诊断结果通常由所有极小冲突集对应的所有极小碰集所描述,求出所有极小碰集是其核心问题之一.提出一种将极小碰集问题转换为约束满足问题的方法,该方法调用成熟的CSP求解器进行求解,扩展了约束可满足问题的应用领域.首次提出hard-冲突集和soft-冲突集的概念,并给出利用所提的方法分别求解具有一些特征的极小碰集:小于固定长度、不含特定元素及包含hard-冲突集和soft-冲突集.实验结果表明,提出的方法易于实现、扩展性强,对于特定类型极小碰集问题的求解效率较高.

关键词: 极小碰集, 约束可满足问题, 基于模型诊断, hard-冲突集, soft-冲突集

Abstract: Model-based diagnosis (MBD) is an important challenge and touchstone for artificial intelligence (AI) and plays an important role on studying the whole field of AI, for revealing a lot of AI technical problems. In MBD, candidate diagnostic results are generally described by all minimal hitting sets from all minimal conflict sets. Computing the minimal hitting sets is one of the core problems in this process. In addition, many practical problems can be converted to minimal hitting sets by some methods, such as the student course selection problem. In this paper, a new method is proposed to convert minimal hitting sets problems into constraint satisfaction problems and then call a state-of-the-art CSP-solver to compute, which extends the application areas of constraint satisfaction problems. Moreover, the concepts of hard-conflict sets and soft-conflict sets are proposed at the first time. Then this paper applies this new method to compute minimal hitting sets which have some features: less than a fixed length, not including specific elements, and including hard-conflict sets and soft-conflict sets. Compared with an effective algorithm, experimental results show that our new proposed method has some advantages: easy to implement, strong scalability and having good efficiency for some types of minimal hitting set.

Key words: minimal conflict sets, constraint satisfaction problem, model-based diagnosis (MBD), hard-conflict set, soft-conflict set

中图分类号: