Performance Analysis and Comparison of Algorithms for Generating Minimal Hitting Sets
HE Qiang-jun1, ZHAO Xiang-fu1, OUYANG Dan-tong2, ZHANG Li-ming2
1. Department of Computer, Zhejiang Normal University, Jinhua, Zhejiang 321000, China;
2. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China
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.
[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.
2019, Vol. 47 
