微信服务号

微信订阅号

2025-4-24- 9
Home > Archive>Volume 29, Issue 12, 2018 >3733-3746. DOI:10.13328/j.cnki.jos.005311
PDF HTML XML Export Cite reminder
Method of Minimality-Checking of Candidate Solution for Minimal Hitting Set Algorithm
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61133011, 61402196, 61272208, 61003101, 61170092); ChinaPostdoctoral Science Foundation (2013M541302); Jilin Province Science and Technology Development Plan (20140520067JH);Provincial Key Disciplines Foundation of Computer Software and Theory of Zhejiang Normal University (ZSDZZZZXK12)

  • Article
    • | |
  • Metrics
    • |
  • Reference [33]
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Minimal hitting set (MHS) problem is an important problem with widely applications in artificial intelligence. During computing all minimal hitting set, how to check the minimality of hitting sets is a key issue. Most of exhaustive MHS algorithms ensure the minimality of results by using subset checking method where its effectiveness is mainly relevant to the scale of minimal hitting sets, i.e., the larger the scale of the MHSs is, the lower the effectiveness of this method has. Consequently, when coming to solve the massive cases, the effectiveness of these algorithms is not high. To overcome this problem, this paper proposes independent coverage checking (ICC) and then develops it into an incremental method named ⅡCC. The effectiveness of this method is irrelevant to the scale of minimal hitting sets. Moreover, when computing all MHS by the incremental MHS algorithm with ⅡCC, it can incrementally test the minimality of candidate solutions, resulting in cutting down many unnecessary non-minimal hitting sets. ⅡCC is used to optimize the Boolean algorithm which is an incremental MHS algorithm using subset checking. The results show that ⅡCC method significantly outperforms the subset checking methods in terms of running time.

    Reference
    [1] Reiter R. A theory of diagnosis from first principles. Artificial Intelligence, 1987,32(1):57-95.
    [2] Yu Q, Li CQ, Shen YM, Wang J. Method of solving abductive reasoning problem via hitting set. Ruan Jian Xue Bao/Journal of Software, 2015,26(8):1937-1945(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4694.htm[doi:10.13328/j. cnki.jos.004694]
    [3] Bonet B, Helmert M. Strengthening landmark heuristics via hitting sets. In:Proc. of the 19th European Conf. on Artificial Intelligence. Amsterdam:IOS Press, 2010. 329-334.
    [4] Wotawa F. On the relationship between model-based debugging and program slicing. Artificial Intelligence, 2002,135(1):125-143.
    [5] Greiner R, Smith BA, Wilkerson RW. A correction to the algorithm in Reiter's theory of diagnosis. Artificial Intelligence, 1989, 41(1):79-88.
    [6] Wotawa F. A variant of Reiter's hitting-set algorithm. Information Processing Letters, 2001,79(1):45-51.
    [7] Jiang YF, Lin L. Computing the minimal hitting set with binary HS-tree. Ruan Jian Xue Bao/Journal of Software, 2002,13(12):2267-2274(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/2267.htm
    [8] Jiang YF, Lin L. The computation of hitting sets with Boolean formulas. Chinese Journal of Computers, 2003,26(8):919-924(in Chinese with English abstract).
    [9] Ouyang DT, Ouyang JH, Cheng XC, Liu J. A method of computing hitting set in model-based diagnosis. Chinese Journal of Science Instrument, 2004,25(4):605-608(in Chinese with English abstract).
    [10] Zhao XF, Ouyang DT. A method of combing SE-tree to compute all minimal hitting sets. Progress in Natural Science, 2006,16(2):169-174.
    [11] Chen XM, Meng XF, Qiao RX. Method of computing all minimal hitting set based on BNB-HSSE. Chinese Journal of Science Instrument, 2010,31(1):61-67(in Chinese with English abstract).
    [12] Zhang LM, Ouyang DT, Zeng HL. Computing the minimal hitting set based on dynamic maximum degree. Journal of Computer Reach and Development, 2011,48(2):209-215(in Chinese with English abstract).
    [13] Pill I, Quaritsch T. Optimizations for the Boolean approach to computing minimal hitting sets. In:Proc. of the 20th European Conf. on Artificial Intelligence. Amsterdam:IOS Press, 2012. 648-653.
    [14] Pill I, Quaritsch T. RC-Tree:A variant avoiding all the redundancy in Reiter's minimal hitting set algorithm. In:Proc. of the 2015 IEEE Int'l Symp. on Software Reliability Engineering Workshops. 2015. 78-84.
    [15] Wang YY, Ouyang DT, Zhang LM, Zhang YG. A method of computing minimal hitting sets using CSP. Journal of Computer Reach and Development, 2015,52(3):588-595(in Chinese with English abstract).
    [16] Lin L, Jiang YF. Computing minimal hitting sets with genetic algorithm. In:Proc. of the 13th Int'l Workshop on Principles of Diagnosis. 2002. 77-80.
    [17] Cincotti A, Cutello V, Pappalardo F. An ant-algorithm for the weighted minimum hitting set problem. In:Proc. of the 2003 IEEE Symp. on Swarm Intelligence. Piscataway:IEEE, 2003. 1-5.
    [18] Huang J, Chen L, Zou P. Computing minimal diagnosis by compounded genetic and simulated annealing algorithm. Ruan Jian Xue Bao/Journal of Software, 2004,15(9):1345-1350(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/1345.htm
    [19] Abreu R, Gemund AJCV. A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. In:Proc. of the 8th Symp. on Abstraction, Reformulation, and Approximation, Vol.9. Menlo Park:AAAI, 2009. 2-9.
    [20] Zhou G, Feng WQ, Jiang BF, et al. Computing minimal hitting set based on immune genetic algorithm. Int'l Journal of Modelling, Identification and Control, 2014,21(1):93-100.
    [21] Jannach D, Schmitz T, Shchekotykhin K. Parallelized hitting set computation for model-based diagnosis. In:Proc. of the 29th AAAI Conf. on Artificial Intelligence. Menlo Park:AAAI, 2015. 1503-1510.
    [22] Zhao XF, Ouyang DT. Deriving all minimal hitting sets based on join relation. IEEE Trans. on Systems, Man, and Cybernetics:Systems, 2015,45(7):1063-1076.
    [23] Pill I, Quaritsch T, Wotawa F. From conflicts to diagnoses:An empirical evaluation of minimal hitting set algorithms. In:Proc. of the 22nd Int'l Workshop on the Principles of Diagnosis. 2011. 203-210.
    [24] Han B, Lee SJ. Deriving minimal conflict sets by CS-tree with mark set in diagnosis from first principles. IEEE Trans. on Systems, Man, and Cybernetics:Cybernetics, 1999,29(2):281-286.
    附中文参考文献:
    [2] 余泉,李承乾,申宇铭,王驹.溯因推理问题的碰集求解方法.软件学报,2015,26(8):1937-1945. http://www.jos.org.cn/1000-9825/4694.htm[doi:10.13328/j.cnki.jos.004694]
    [7] 姜云飞,林笠.用对分HS-树计算最小碰集.软件学报,2002,13(12):2267-2274. http://www.jos.org.cn/1000-9825/13/2267.htm
    [8] 姜云飞,林笠.用布尔代数方法计算最小碰集.计算机学报,2003,26(8):919-924.
    [9] 欧阳丹彤,欧阳继红,程晓春,刘杰.基于模型诊断中计算碰集的方法.仪器仪表学报,2004,25(4):605-608.
    [11] 陈晓梅,孟晓风,乔仁晓.基于BNB-HSSE计算全体碰集的方法.仪器仪表学报,2010,31(1):61-67.
    [12] 张立明,欧阳丹彤,曾海林.基于动态极大度的极小碰集求解方法.计算机研究与发展,2011,48(2):209-215.
    [15] 王艺源,欧阳丹彤,张立明,张永刚.利用CSP求解极小碰集的方法.计算机研究与发展,2015,52(3):588-595.
    [18] 黄杰,陈琳,邹鹏.一种求解极小诊断的遗传模拟退火算法.软件学报,2004,15(9):1345-1350. http://www.jos.org.cn/1000-9825/15/1345.htm
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 17,2016
  • Revised:November 06,2016
  • Online: December 05,2018
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063