电子学报 ›› 2019, Vol. 47 ›› Issue (5): 1101-1110.DOI: 10.3969/j.issn.0372-2112.2019.05.018

• 学术论文 • 上一篇    下一篇

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

何嫱君1, 赵相福1, 欧阳丹彤2, 张立明2   

  1. 1. 浙江师范大学计算机系, 浙江金华 321000;
    2. 吉林大学计算机科学与技术学院, 吉林长春 130012
  • 收稿日期:2018-05-02 修回日期:2018-07-13 出版日期:2019-05-25
    • 通讯作者:
    • 赵相福
    • 作者简介:
    • 何嫱君 女,1992年生于河南三门峡.浙江师范大学软件工程硕士,研究方向为基于模型的故障诊断.E-mail:1002180265@qq.com;欧阳丹彤 女,博士、教授,1968年生于吉林长春.吉林大学教师、博士生导师,研究方向为基于模型的故障诊断、自动推理等.E-mail:ouyd@jlu.edu.cn;张立明 男,博士、高级工程师,1980年生于吉林长春.吉林大学教师,研究方向为基于模型的故障诊断等.E-mail:limingzhang@jlu.edu.cn
    • 基金资助:
    • 浙江省自然科学基金 (No.LY16F020004)

Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets

HE Qiang-jun1, ZHAO Xiang-fu1, OUYANG Dan-tong2, ZHANG Li-ming2   

  1. 1. Department of Computer, Zhejiang Normal University, Jinhua, Zhejiang 321000, China;
    2. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China
  • Received:2018-05-02 Revised:2018-07-13 Online:2019-05-25 Published:2019-05-25

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

关键词: 基于模型的诊断, 碰集, 性能

Abstract: 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.

Key words: model-based diagnosis, hitting set, performance

中图分类号: