基于模型诊断是一项新型智能诊断推理技术,旨在解决第一代专家系统中知识不易获取、对领域专家依赖性过强等严重缺陷。基于模型诊断被人工智能领域专家称为诊断理论和技术上的革命,对整个人工智能领域的研究起着非常重要的推动作用。基于模型诊断的主要工作原理是根据系统的描述和观测进行逻辑推理得到冲突部件集,再通过冲突部件集计算极小碰集,即得到诊断结果。经过几十年的发展,关于基于模型诊断的研究取得了丰硕的成果,并在航天系统、工业系统和网络系统的故障处理领域得到了广泛的应用。极小碰集求解是基于模型诊断过程中的关键步骤,因此极小碰集求解效率会对诊断整体求解时间产生重要影响。极小碰集问题最早是由计算机专家Karp在1972年提出,随后基于模型诊断专家Reiter于1987年首次提出了一种极小碰集方法HS-TREE。对于极小碰集问题,求解方法主要分为两大类,即基于枚举的完备求解方法和基于随机搜索的非完备求解方法。完备求解方法要求极小碰集方法结束时能给出所有解,而非完备求解方法只要求给出部分解,非完备求解方法相对完备求解方法在问题规模较大时能更快给出结果。本文通过对极小碰集问题特征的深入研究,提出了一种效率优良的极小碰集完备求解方法;除此之外,在极小碰集求解过程中,提出了一种效率更高的碰集极小性判定方法:1)结合动态极大覆盖值的极小碰集求解方法:针对DMDSE-Tree方法存在冗余分支未能剪掉的情况,提出了此方法,基本思想是通过对元素的元素覆盖值进行预排序,使得选取的元素组成的集合若是碰集,则该集合是较早地得到碰集的集合,因此避免了很多无用的搜索;求解过程中添加了启发式策略和剪枝策略,使得搜索空间极大减小,且剪枝策略不会导致丢解;使用邻接表作为存储结构,邻接表相对传统的矩阵表示法能更快地找到元素能够覆盖的集合簇中的集合。实验结果表明,与效率较高的Boolean方法、DMDSE-Tree方法和最近提出的SAT-MHS方法相比,此方法高效且容易实现,对于规模较大的问题,求解效率有明显提升。2)结合碰集的子集检测的极小性判定方法:现有碰集极小性判定方法需与其它候选碰集进行子集检测,针对此方法在问题规模较大时效率低下的问题,提出了对碰集的子集进行检测的极小性判定方法,当去除一个元素的所有子集都不是碰集时,此碰集是极小碰集。此方法优点是求解复杂性不会随着极小碰集问题规模的增大而导致极小性判定时间急剧增加,而是只与被检测碰集的大小相关,因此能极大提高碰集极小性的判定效率,进而提升诊断求解效率。以上1)和2)从不同方面对极小碰集完备求解方法进行了改进,理论和实验表明取得了较好的求解效率。前者从极小碰集问题整体出发缩小求解空间,优化存储结构,这是宏观层面的优化;后者通过对碰集的子集进行检测减少碰集极小性判定时间,从而在微观上优化了极小碰集方法的求解效率。