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

来源：计算机研究与发展杂志2015年第3期北京时间：

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

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

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