Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets

HE Qiang-jun; ZHAO Xiang-fu; OUYANG Dan-tong; ZHANG Li-ming

doi:10.3969/j.issn.0372-2112.2019.05.018

您当前的位置：

首页 >

文章列表页 >

Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets

更新时间：2025-07-16

- Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets
- Acta Electronica Sinica Vol. 47, Issue 5, Pages: 1101-1110(2019)
- 作者机构：
  
  1. 浙江师范大学计算机系,浙江,金华,321000
  2. 吉林大学计算机科学与技术学院,吉林,长春,130012
  3. 浙江师范大学计算机系,浙江,金华,321000
  4. 吉林大学计算机科学与技术学院,吉林,长春,130012
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2019.05.018
  CLC： TP18
- Published Online：25 May 2019，
  
  Published：2019
- 稿件说明：
移动端阅览
HE Qiang-jun, ZHAO Xiang-fu, OUYANG Dan-tong, et al. Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets[J]. Acta Electronica Sinica, 2019, 47(5): 1101-1110.
DOI：

HE Qiang-jun, ZHAO Xiang-fu, OUYANG Dan-tong, et al. Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets[J]. Acta Electronica Sinica, 2019, 47(5): 1101-1110. DOI： 10.3969/j.issn.0372-2112.2019.05.018.

摘要

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

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.

关键词

Keywords

references

Views

307

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

GOSBMB:Dynamic Memory Balancing Based on Guest Operating System Behaviors for Virtual Machines

A Cross-Layered Scheduling and Resource Allocation Algorithm in OFDMA Systems

An Approach to Performance Assessment of Interoperability Protocols

Towards Evaluating the Performance of Network Management Strategies Based on Mobile Code

Related Author

OUYANG Dan-tong

ZHAO Xiang-fu

CHENG Xu

YANG Chun

ZHENG Yan-song

NIU Yan

CHENG Shi-duan

ZOU Shi-hong

Related Institution

Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education Jilin UniversityChangchunJilin130012China

School of Computer Science and TechnologyJilin UniversityChangchunJilin 130012China

Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University

School of Computer Science and Technology, Jilin University

School of EECS,Peking University

⁰