极小碰集求解算法的性能分析与比较

Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets

基于模型的诊断为人工智能领域中一个重要的研究分支,极小碰集即候选诊断的求解过程极大影响最终的诊断效率.本文关注当前主要的极小碰集求解算法,简要介绍了它们的基本思想,从算法描述和实例比较了它们的异同和复杂性,并设计实现了一个统一的实验平台,测试并比较了它们的实际执行效率,为实际选择合适的算法提供了重要参考依据.

Model-based diagnosis is an important branch of research in the field of artificial intelligence.The efficiency for generating all minimal hitting sets,i.e.,candidate diagnoses,considerably affects the final diagnostic process.This paper focuses on the current major algorithms for computing minimal hitting sets.First,the basic ideas of algorithms were briefly introduced.Then,the similarities and differences,and complexity of them were compared by simple algorithm description and examples.An integrated experimental platform was implemented for testing and comparing their time efficiency,which provides an important reference for the actual selection of an appropriate algorithm in practice.