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

doi:10.3969/j.issn.0372-2112.2019.05.018

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

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

何嫱君¹, 赵相福¹, 欧阳丹彤², 张立明²

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-jun¹, ZHAO Xiang-fu¹, OUYANG Dan-tong², ZHANG Li-ming²

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

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

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

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

中图分类号:

TP18

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

HE Qiang-jun, ZHAO Xiang-fu, OUYANG Dan-tong, ZHANG Li-ming. Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets[J]. Acta Electronica Sinica, 2019, 47(5): 1101-1110.

参考文献

[1] Zhao X,Ouyang D,Zhang L.Computing all minimal hitting sets by subset recombination[J].Applied Intelligence,2018,48(2):257-270.
[2] Zhao X,Ouyang D.Deriving all minimal hitting sets based on join relation[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(7):1063-1076.
[3] 赵相福,欧阳丹彤.使用SAT求解器产生所有极小冲突部件集[J].电子学报,2009,37(4):804-810. ZHAO Xiang-fu,OUYANG Dan-tong.Deriving all minimal conflict sets using satisfiability algorithms[J].Acta Electronica Sinica,2009,37(4):804-810.(in Chinese)
[4] 欧阳丹彤,刘伯文,周建华,张立明.结合问题特征利用SE-Tree反向深度求解冲突集的方法[J].电子学报,2017,45(5):1175-1181. OUYANG Dan-tong,LIU Bo-wen,ZHOU Jian-hua,ZHANG Li-ming.A method ofcomputing minimal conflict sets combining the structure property with the anti-depth SE-tree[J].Acta Electronica Sinica,2017,45(5):1175-1181.(in Chinese)
[5] 刘梦,欧阳丹彤,刘伯文,张立明,张永刚.结合问题特征的分组式诊断方法[J].电子学报,2018,46(3):589-594. LIU Meng,OUYANG Dan-tong,LIU Bo-wen,ZHANG Li-ming,ZHANG Yong-gang.Grouped diagnosis approach using the feature of problem[J].Acta Electronica Sinica,2018,46(3):589-594.(in Chinese)
[6] Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-95.
[7] Wotawa F.A variant of Reiter's hitting-set algorithm[J].Information Processing Letters,2001,(79):45-51.
[8] 王肖,赵相福.用CHS-tree基于集合势的方法计算极小碰集[J].计算机集成制造系统,2014,20(2):401-406. Wang Xiao,Zhao Xiangfu.Computing minimal hitting sets with CHS-tree method[J].Computer Integrated Manufacturing Systems.2014,20(2):401-406.(in Chinese)
[9] 姜云飞,林笠.用对分HS-树计算最小碰集[J].软件学报,2002,13(12):2267-2274. Jiang Yunfei,Lin Li.Computing the minimal hitting sets with binary HS-tree[J].Journal of Software,2002,13(12):2267-2274.(in Chinese)
[10] 姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924. Jiang Yunfei,Lin Li.The computation of hitting sets with Boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924.(in Chinese)
[11] Zhao X F,Ouyang D T.A method of combining SE-tree to compute all minimal hitting sets[J].Progress in Natural Science,2006,16(2):169-174.
[12] Han,B,Lee,S J.Deriving minimal conflict sets by CS-trees with mark set in diagnosis from first principles[J].IEEE Transactions on Systems,Man,and Cybernetics,1999,29(2):281-286.
[13] Zhao X F,Ouyang D T.Improved algorithms for deriving all minimal conflict sets in model-based diagnosis[A].Lecture Notes in Computer Science[C].springer.2007,4681:157-166.

[1]	王鼎, 尹洁昕, 郑娜娥, 聂福全. 信号传播速度未知下基于运动单站到达频率的定位新方法[J]. 电子学报, 2022, 50(5): 1181-1191.
[2]	闫晓东, 周公博. 中间梁方式下压电式能量采集器发电性能研究[J]. 电子学报, 2022, 50(2): 404-414.
[3]	黎赛, 陈生海, 杨亮, 胡彦彬. 解码转发方案下混合RF-UWOC传输系统的性能分析[J]. 电子学报, 2022, 50(2): 391-395.
[4]	赵相福, 黄森, 童向荣, 欧阳丹彤, 张立明, 章星林. IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J]. 电子学报, 2022, 50(11): 2722-2729.
[5]	邹军华, 段晔鑫, 任传伦, 邱俊洋, 周星宇, 潘志松. 基于噪声初始化、Adam-Nesterov方法和准双曲动量方法的对抗样本生成方法[J]. 电子学报, 2022, 50(1): 207-216.
[6]	廖彬, 黄静莱, 王鑫, 孙瑞娜, 葛晓燕, 国冰磊. SCEA:一种适应高维海量数据的并行聚类集成算法[J]. 电子学报, 2021, 49(6): 1077-1087.
[7]	车向北, 康文倩, 邓彬, 杨柯涵, 李剑. 一种基于图神经网络的SDN路由性能预测模型[J]. 电子学报, 2021, 49(3): 484-491.
[8]	罗阳锦, 张升伟, 陆浩. 高光谱微波辐射计宽带高速数字系统设计[J]. 电子学报, 2021, 49(2): 380-386.
[9]	俞加平, 陈华辉, 钱江波, 董一鸿. LSM树中基于热度预测的异构布隆过滤器方案[J]. 电子学报, 2021, 49(11): 2090-2095.
[10]	郭广颂, 陈良骥, 文振华, 张勇. 求解高维混合指标优化问题的交互式进化计算[J]. 电子学报, 2020, 48(7): 1361-1368.
[11]	陆佳炜, 吴涵, 陈烘, 张元鸣, 梁倩卉, 肖刚. 一种基于动态拓扑的流计算性能优化方法及其在Storm中的实现[J]. 电子学报, 2020, 48(5): 878-890.
[12]	曲海成, 于思淼, 刘万军, 王鑫源. 面向CUDA程序的性能预测框架[J]. 电子学报, 2020, 48(4): 654-661.
[13]	饶永南, 王萌, 康立, 杨德进, 卢晓春, 王雪. GPS III首星空间信号质量监测评估[J]. 电子学报, 2020, 48(2): 407-411.
[14]	李明, 沈廷鳌, 毛育文. 频率失配条件的自适应相位差无偏估计方法及性能分析[J]. 电子学报, 2019, 47(9): 1905-1912.
[15]	康立, 饶永南, 宿晨庚, 石慧慧, 杨德进, 贺成艳, 王萌. 基于高增益接收系统的Galileo E1信号质量评估方法研究[J]. 电子学报, 2019, 47(8): 1685-1691.

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

Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics