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

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

A Method of Computing Minimal Hitting Sets Using CSP

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.