结合故障输出结构特征的极小冲突求解算法

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

作者：徐旖旎,欧阳丹彤,刘梦,张立明,张永刚,

摘要：基于模型诊断(model-baseddiagnosis)是人工智能领域中的重要研究方向，而基于极小冲突求诊断是求解诊断问题的经典方法，因此求解极小冲突是诊断中的一个重要步骤.通过对电路模型特征的研究，结合CSRDSE极小冲突集求解算法，提出结合故障输出结构特征的极小冲突求解算法MCS-SFFO：首先对CSRDSE算法的剪枝规则进行了改进，避免对集合枚举树SE-Tree中非冲突集叶节点对应子叶节点的访问；其次，提出故障输出无关元件集与故障输出相关元件集等相关概念，并根据系统描述和观测给出求解故障输出无关元件集的方法；最后，提出非冲突集定理，即故障输出无关元件集的子集不是冲突集，并根据非冲突集定理，给出极小冲突集求解算法MCS-SFFO.MCS-SFFO算法在基于CSRDSE算法求冲突集方法的基础上对无解空间进一步剪枝，减少了调用SAT求解器的次数.实验结果表明：与CSRDSE算法相比，MCS-SFFO算法求解效率明显提升.

关键词：基于模型诊断, 极小冲突集, 集合枚举树, SAT求解器, 故障输出无关元件,