ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

### 利用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

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.