Font Size: a A A

Research On Method For Computing All Minimal Hitting Set

Posted on:2018-12-31Degree:MasterType:Thesis
Country:ChinaCandidate:S G LiuFull Text:PDF
GTID:2348330515474047Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Model Based Diagnosis(MBD)as a new Artificial Intelligence(AI)diagnosis technology,overcomes the disadvantages of the traditional diagnosis method,such as hardly obtaining domain knowledge and strongly depending on the domain experts.As a recently hot topic in the development of AI,MBD has many very prominent and outstanding achievements,leading to more attentions on the field of academics and industry.Computing minimal hitting set is a key step in the process of solving MBD,which has greatly impact on the performance of MBD.In 1972,Richard firstly proposes a hitting set problem.Then,in 1987,Reiter designs a method to solve this problem.In the past decade,more and more researchers develop various strategies,resulting in many methods,which further improves the performance of solving MBD.Solving minimal hitting set is a classical combination optimization problem with extensive applications,including scheduling problem,distribution problem,and some other applications.There exists a lot of methods for solving minimal hitting set.However,the efficiency of the current methods is also not enough.If we can improve the performance of the current methods,then it still has great theoretical and realistic significance.This paper improves the method called HSSE-Tree,using a novel idea,i.e.that is,making use of the structure property of SE-Tree.Additional,this paper develops an efficient method for minimality-checking of candidate solution,which speeds up to judge whether the current candidate solution is minimal:1)Method for Computing Minimal Hitting Set Based on the Structural Feature of SE-TREE: During the process of computing minimal hitting set by SE-Tree,it would 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.Firstly,we introduce the definition of redundant node by IV 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 method 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.2)Method of Minimality-checking of Candidate Solution for Minimal Hitting Set Algorithm: Most of exhaustive MHS algorithms ensure the minimality of results by using subset checking method,which effectiveness is mainly relevant to the scale of minimal hitting sets,i.e.,the larger scale the MHSs is,the lower effectiveness this method has.As a consequence,when coming to solve the massive cases,the effectiveness of these algorithms is not high.To overcome this problem,we propose independent coverage checking(ICC)and then develop it into an incremental method named IICC.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 IICC,it can incrementally test the minimality of candidate solutions,resulting in cutting down many unnecessary non-minimal hitting sets.Finally,we make use of IICC to optimize the Boolean algorithm which is an incremental MHS algorithm using subset checking.The results show that our IICC method significantly outperforms the subset checking methods in terms of running time.Both of these above methods achieves great results in different ways.The former one explores the structure property of SE-Tree and the combination of each subset,which can provide the pruning information to the depth priority search algorithms.On the other hand,the latter one uses the element independent coverage information as the judge foundation of the hitting set minimality-checking.Moreover,after generating the candidate solution each time,this novel judge process will work,leading to pruning some extra unnecessary nodes.
Keywords/Search Tags:Minimal hitting set, Model-based diagnosis, SE-Tree, Minimality-checking of hitting set, Complete method
PDF Full Text Request
Related items