IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking

ZHAO Xiang-fu; HUANG Sen; TONG Xiang-rong; OUYANG Dan-tong; ZHANG Li-ming; ZHANG Xing-lin

doi:10.12263/DZXB.20211356

您当前的位置：

首页 >

文章列表页 >

IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking

PAPERS | 更新时间：2025-12-08

- IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking
- ACTA ELECTRONICA SINICA Vol. 50, Issue 11, Pages: 2722-2729(2022)
- 作者机构：
  
  1.烟台大学计算机与控制工程学院,山东烟台 264005
  2.浙江师范大学计算机系,浙江金华 321000
  3.吉林大学计算机科学与技术学院,吉林长春 130012
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20211356
  CLC： TP306
- Received：08 October 2021，
  
  Revised：2022-01-20，
  
  Published：25 November 2022
- 稿件说明：
移动端阅览
赵相福,黄森,童向荣等.IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J].电子学报,2022,50(11):2722-2729.

ZHAO Xiang-fu,HUANG Sen,TONG Xiang-rong,et al.IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking[J].ACTA ELECTRONICA SINICA,2022,50(11):2722-2729.
赵相福,黄森,童向荣等.IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J].电子学报,2022,50(11):2722-2729. DOI： 10.12263/DZXB.20211356.

ZHAO Xiang-fu,HUANG Sen,TONG Xiang-rong,et al.IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking[J].ACTA ELECTRONICA SINICA,2022,50(11):2722-2729. DOI： 10.12263/DZXB.20211356.

摘要

基于模型的诊断推理是人工智能领域的一个重要分支.其中由冲突部件集产生所有极小碰集是基于模型诊断推理的重要一步.根据布尔算法的特征，所有的冲突集可以划分为左右两个子集合簇，且左分支集合簇恰好为右分支集合簇的子集，这为由左分支增量产生右分支极小碰集提供了理论基础；另外，在自底向上增量归并元素的过程中，结合局部独立覆盖策略可以直接增量产生所有的极小碰集，从而避免非极小碰集和相同极小碰集的冗余产生.理论上，右分支解集可由左分支解集增量方法产生，避免了碰集中大量元素的重复计算.大量实验结果表明：本文提出的算法比之前的布尔算法及相关改进算法都具有显著的效率提升，最高可达约5倍.

Abstract

Model-based diagnostic reasoning is an important research branch in the field of artificial intelligence. Generating all minimal hitting-sets(MHSs) from conflict sets is a crucial step in the process of model-based diagnostic reasoning. To solve this problem

all conflict sets are divided into left and right parts according to the Boolean algorithm

and the left cluster is just a subset of the right one

which provides a theoretical foundation for incrementally generating the right MHSs from the left ones. In addition

in the process of incrementally merging branch elements from bottom to top

with the help of the local independence cover checking strategy

all MHSs can be directly produced without generating any redundant non-MHSs and duplicated MHSs. Theoretically

the right branch solution can be incrementally generated by the left one. Experimental results show that the efficiency of the proposed algorithm is significantly improved by about five times

compared with the classical algorithm based on Boolean algorithm and its related improved algorithms.

关键词

Keywords

references

REITER R . A theory of diagnosis from first principles [J]. Artificial Intelligence , 1987 , 32 ( 1 ): 57 - 95 .

FRIEDRICH G , STUMPTNER M , WOTAWA F . Model-based diagnosis of hardware designs [J]. Artificial Intelligence , 1999 , 111 ( 1-2 ): 3 - 39 .

GREINER R , SMITH B A , WILKERSON R W . A correction to the algorithm in Reiter's theory of diagnosis [J]. Artificial Intelligence , 1989 , 41 ( 1 ): 79 - 88 .

WOTAWA F . A variant of Reiter's hitting-set algorithm [J]. Information Processing Letters , 2001 , 79 ( 1 ): 45 - 51 .

姜云飞 , 林笠 . 用对分HS-树计算最小碰集 [J]. 软件学报 , 2002 , 13 ( 12 ): 2267 - 3374 .

JIANG Yun-fei , LIN Li . Computing the minimal hitting set with binary HS-Tree [J]. Journal of Software , 2002 , 13 ( 12 ): 2267 - 3374 . (in Chinese)

姜云飞 , 林笠 . 用布尔代数方法计算最小碰集 [J]. 计算机学报 , 2003 , 26 ( 8 ): 919 - 924 .

JIANG Yun-fei , LIN Li . The computation of hitting sets with Boolean formulas [J]. Chinese Journal of Computers , 2003 , 26 ( 8 ): 919 - 924 . (in Chinese)

PILL I , QUARITSCH T . Optimizations for the Boolean approach to computing minimal hitting sets [C]// Proceedings of the 20th European Conference on Artificial Intelligence , 2012 : 648 - 653 .

刘思光 , 欧阳丹彤 , 张立明 . 极小碰集求解中候选解极小性判定方法 [J]. 软件学报 , 2018 , 29 ( 12 ): 3733 - 3746 .

LIU Si-guang , OUYANG Dan-tong , ZHANG Li-ming . Minimization of candidate solutions in minimal hitting sets solution [J]. Journal of Software , 2018 , 29 ( 12 ): 3733 - 3746 . (in Chinese)

ZHAO Xiang-fu , OUYANG Dan-tong . Deriving all minimal hitting sets based on join relation [J]. IEEE Transactions on Systems Man Cybernetics System , 2015 , 45 ( 7 ): 1063 - 1076 .

刘娟 , 欧阳丹彤 , 王艺源 , 等 . 结合特征学习的粒子群求解极小碰集方法 [J]. 电子学报 , 2015 , 43 ( 5 ): 841 - 845 .

LIU Juan , OUYANG Dan-tong , WANG Yi-yuan , et al . Computing minimal hitting sets with particle swarm optimization combined characteristics learning [J]. Acta Electronica Sinica , 2015 , 43 ( 5 ): 841 - 845 . (in Chinese)

何嫱君 , 赵相福 , 欧阳丹彤 , 等 . 极小碰集求解算法的性能分析与比较 [J]. 电子学报 , 2019 , 47 ( 5 ): 1101 - 1110 .

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 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy

A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree

A Block-Based Diagnostic Method Combining with the Circuit Structure

Related Author

Sen HUANG

Xiang-rong TONG

Dan-tong OUYANG

Li-ming ZHANG

Xing-lin ZHANG

Xiang-fu ZHAO

HUANG Sen

ZHAO Xiang-fu

Related Institution

Department of Computer， Zhejiang Normal University

College of Computer Science and Technology， Jilin University

School of Computer and Control Engineering， Yantai University

Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University) Ministry of Education Changchun Jilin China

College of Software Jilin University Changchun Jilin China

⁰