Computing All Minimal Hitting Sets Based On Dynamic Maximum Coverage Value And Self-subset Detection

Model-based diagnosis(MBD)is a new intelligent diagnostic reasoning technology,which aims to solve the serious shortcomings of the first generation expert system,such as the difficulty of acquiring knowledge and the strong dependence on domain experts.MBD is called a revolution in diagnosis theory and technology by experts in the field of artificial intelligence(AI).It plays a very important role in promoting the research of the whole field of AI.The main principle of MBD is to get the set of conflicting parts by logical reasoning based on the description and observation of the system,and then calculate the minimal hitting set through the set of conflicting parts.That is to say,the diagnostic results are obtained.After decades of development,the research on MBD has achieved fruitful results.MBD has been widely used in the field of fault handling of space systems,industrial systems and network systems.Minimal hitting set solving is a key step in the process of MBD,so the efficiency of minimal hitting set solving will have a significant impact on the overall solution time of diagnosis.In 1972,minimal hitting set problem was first proposed by Karp,a computer expert at the University of California,Berkeley.Then,in 1987,Reiter proposed the first minimal hitting set method which called HS-TREE.For the minimal hitting set problem,the methods are mainly divided into two categories: enumeration-based complete method and random search-based incomplete method.Complete method requires that all solutions can be given at the end of the minimal hitting set method,while incomplete method only requires partial solutions.The incomplete method can give results faster than the complete method when the scale of the problem is very large.In this paper,a complete minimal hitting set method with good efficiency is proposed.The method is mainly based on the in-depth study of the characteristics of minimal hitting set problem.In addition,in the process of minimal hitting set solving,a more efficient minimal hitting set decision method is proposed.1)Computing minimal hitting sets based on dynamic maximum coverage value(MHS-DMCV): Aiming at the situation that the redundant branches of DMDSE-Tree method can not be cut off,this method is proposed.The key idea of MHS-DMCV method is as follows.Firstly,selecting elements according to the order of element coverage value from large to small.If the selected elements can form a hitting set,then these elements are the fastest set of elements to form a hitting set,thus avoiding many useless searches.Secondly,the heuristic strategy and pruning strategy are added to the MHS-DMCV method to reduce the search space greatly,and the pruning strategy will not lead to the loss of solution.Finally,adjacent list is used to store the minimal conflict set cluster in the method.Among the basic storage structures,adjacency list has better space cost than matrix.Besides,the adjacent pointer can quickly find the sets in the minimal conflict set cluster which can be covered by an element.Experimental results show that the MHS-DMCV method is more efficient and easy to implement than the Boolean method,DMDSE-Tree method and the recently proposed SAT-MHS method.For large-scale problems,the efficiency of solution has been improved obviously.2)Minimality determination method based on subset detection of hitting set(MD-SDHS): Existing minimality determination methods need subset detection with other candidate hitting sets.The larger scale the minimal hitting set problem is,the lower effectiveness these methods have.Aiming at the inefficiency of these methods,MD-SDHS method is proposed.When all subsets of an element removed are not hitting set,the hitting set is minimal.The efficiency and complexity of MD-SDHS method will not increase dramatically with the increase of the number of hitting sets,but will only related to the size of the detected hitting set.Therefore,MD-SDHS method can greatly improve the efficiency of decision and diagnosis.The MHS-DMCV and MD-SDHS method have improved the complete minimal hitting set method from different aspects.MHS-DMCV method reduces the solution space and optimizes the storage structure from the whole minimal hitting set problem,which is the optimization at the macro level.MD-SDHS method optimizes the decision time of minimal hitting set based on subset detection of hitting set,thus optimizing the overall efficiency of minimal hitting set in micro.