ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (3): 588-595.doi: 10.7544/issn1000-1239.2015.20131478

Previous Articles     Next Articles

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.

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

CLC Number: