ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (11): 2556-2566.doi: 10.7544/issn1000-1239.2016.20150396

• 人工智能 • 上一篇    下一篇

结合SE-Tree结构特征的极小碰集求解算法

刘思光,欧阳丹彤,王艺源,贾凤雨,张立明   

  1. (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (lsgmliss@163.com)
  • 出版日期: 2016-11-01
  • 基金资助: 
    国家自然科学基金项目(61133011,61402196,61272208,61003101,61170092);中国博士后科学基金项目(2013M541302);吉林省科技发展计划基金项目(20140520067JH);浙江师范大学计算机软件与理论省级重中之重学科开放基金项目(ZSDZZZZXK12) This work was supported by the National Natural Science Foundation of China (61133011,61402196,61272208,61003101,61170092), the China Postdoctoral Science Foundation (2013M541302), the Science and Technology Development Program of Jilin Province (20140520067JH), and the Provincial Key Disciplines Foundation of Computer Software and Theory of Zhejiang Normal University (ZSDZZZZXK12).

Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree

Liu Siguang, Ouyang Dantong, Wang Yiyuan, Jia Fengyu, Zhang Liming   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
  • Online: 2016-11-01

摘要: 在结合SE-Tree计算集合簇极小碰集的过程中,现有算法会对大量不会产生碰集的冗余节点进行访问.这无疑将影响算法的效率,冗余节点比例越高,影响越大.通过对SE-Tree中叶节点的特殊性质的分析,并结合现有碰集算法有解空间中冗余节点的特征,提出非解冗余节点概念.在对SE-Tree的结构特征进行深入分析基础上,根据非碰集的子集也不是碰集的特点,提出辅助剪枝的概念,通过在剪枝树上设置剪枝判定节点,减少对极小碰集求解过程中无解空间的访问;针对较大规模问题,还提出结合多级辅助剪枝树的极小碰集求解算法,进而较大程度地减少对非解冗余节点的访问;根据多级辅助剪枝树及SE-Tree的结构特征,给出提前终止算法的判定条件,并证明了此算法的正确性.实验结果表明:与效率较高的Boolean算法相比,该算法高效且易于实现,尤其是对规模较大的问题,效率能提升1个数量级.

关键词: 基于模型诊断, 极小碰集, 集合枚举树, 辅助剪枝树, 无解空间剪枝

Abstract: During the process of computing minimal hitting set (MHS) by SE-Tree, it will generate many redundant nodes that cannot be pruned by current SE-Tree based algorithms, which affects the efficiency of these algorithms, i.e., the higher the ratio of redundant nodes is, the greater likely the impact of algorithms has. In this paper, firstly we introduce the definition of redundant nodes by analyzing the characteristic of leaf-node in SE-Tree and the redundant nodes in solution space in existent algorithms. Secondly, on the basis of analyzing the structural feature of SE-Tree and the theory that the subset of non-hitting set is non-hitting set, we propose the concept of assistant pruning tree. Specially, the decision nodes are added into the assistant pruning tree, which can largely reduce the visit of non-solution space. Furthermore, in order to decrease the visit of non-solution space when computing larger problem as much as possible, the algorithm of computing minimal hitting set combining with multi-level assistant pruning tree is proposed. Finally, we set a reasonable termination condition to make our algorithm stop without losing correct solution as early as possible, and then prove its correctness. Results show that the proposed algorithm is easily implemented and efficient. Moreover, our algorithm significantly outperforms a state-of-the-art minimal hitting set algorithm Boolean, even up to one order of magnitude for some instances.

Key words: model-based diagnosis, minimal hitting set, SE-Tree, assistant pruning tree, non-solution space pruning

中图分类号: