徐旖旎 欧阳丹彤 刘 梦 张立明 张永刚

(吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (jlxuyini@126.com)

基于模型诊断(model-based diagnosis)一直是人工智能领域中的重要研究方向，对人工智能领域的发展起到了至关重要的作用[1].模型诊断方法包括基于冲突的求诊断方法和直接求诊断方法.基于冲突的求诊断方法主要分为2个步骤:1)求出极小冲突集;2)求解极小冲突集的极小碰集，即为诊断解.直接求诊断方法就是利用SAT(satisfiability)求解器直接求出诊断解，而不需要产生极小冲突集[2].

在基于模型诊断问题中，求解极小冲突集是求诊断解的重要步骤之一.Reiter[3]最早采用冲突部件集的概念来计算极小诊断.早期许多专家使用定理证明器的方法求解极小冲突.Genesereth[4]提出用DART(device-independent diagnostic program)方法进行冲突识别.Haenni[5]在计算冲突集时使用归结的方法.但传统定理证明器效率较低，因此这些方法的实际应用并不广泛.

国内学者也对冲突识别做出相关研究，如栾尚敏等人[6]提出利用系统结构信息求解极小冲突集的方法，方敏[7]提出先离线求冲突然后在线求极小冲突的方法.然而，这些算法效率较低且通用性差，因此没有得到广泛应用.20世纪90年代Hou[8]首次提出了利用枚举树求解极小冲突集的CS-Tree算法，但其算法由于剪枝策略会造成丢失解.2006年和2009年赵相福等人在CS-Tree，Inverse CS-Tree，CS-Tree with Mark Set[9]的基础上分别提出2种改进算法CSSE-Tree[10]和CSISE-Tree[11],并首次使用SAT求解器求解冲突集，使得算法效率大大提高.刘伯文等人[12]在CSISE-Tree算法上进行改进，提出利用集合枚举树SE-Tree反向深度求冲突集的算法CSRDSE.CSISE-Tree算法主要针对非冲突集进行剪枝；……