Research On Algorithms For Computing All Minimal Hitting Sets With Parameter Matrices And Incremental Strategies

Model-based diagnosis(MBD)is a very important research part of artificial intelligence.As a newly intelligent diagnosis reasoning technology based on deep knowledge,it can effectively overcome the limitations of expert system,which made it has been widely used in many fields.In the process of MBD,calculating all minimal hitting sets is a key step,which has greatly impact on the performance of MBD.At the moment,experts and scholars both at home and abroad are still actively studying the efficient minimal hitting set solving algorithms,striving to accomplish the solution in a shorter time.In addition,many non-minimal hitting set problems,such as industry and theory,can be transformed into minimal hitting set problems for solving,in order to meet the increasingly complex production needs.In this thesis,an efficient complete minimal hitting set solving algorithm is proposed by the depth study of the problem,and the corresponding minimization strategy is added according to the problem characteristics of minimal hitting sets.Besides,aiming at the defects of solving in increment algorithm,a more efficient increment optimization strategy is suggested.The main research contributions are as follows:(1)Minimal Hitting Sets Based on Dynamic Minimal Cardinality Parameter Matrix.The main idea is to obtain all minimal hitting sets by using a dynamic minimum cardinality parameter matrix.The parameter matrix was constructed to store the correlation information of minimal conflict sets,and the minimal cardinality was considered to decompose the problem gradually into smaller subproblems.The search space can be considerably reduced by introducing the effective pruning strategy and heuristic information into the process of generating hitting sets.Besides,combining with the characteristics of the original parameter matrix,we can check the obtained hitting sets efficiently.Experimental results show that the proposed algorithm has higher computational efficiency than many other well-known approaches,not only on regular synthetic data,but also on many circuits in the widely used ISCAS-85 benchmark circuits.(2)CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy.In order to shorten the time costs of minimization and decrease the redundant nodes in the solving process of increment algorithm,a novel optimization strategy for incremental diagnosis is proposed.When a new conflict set is added,the relationship between the original minimal hitting sets and the newly added conflict set will be explored thoroughly.The time cost can be greatly reduced by joining the corresponding heuristic strategy to select the specific sets in the course of minimality checking.The computing performance can be improved considerably by introducing the optimized incremental strategy to update the final results.Furthermore,in order to obtain the higher efficiency,an algorithm named Complete Increment Minimal Hitting Set based on optimized incremental strategy is presented.The proposed algorithm processes set incrementally in turn according to the ascending order of the cardinality of set.Experimental results show that the proposed algorithm has more efficient than many other state-of-the-art methods,with a reduction of several orders of magnitude runtime.The JMatrix and CIMHS algorithm have optimized and improved the existing complete minimal hitting set solving method in different ways.The JMatrix algorithm reduces the scale of the parameter matrix by introducing minimum cardinality and minimizes the hitting sets according to parameter matrix.The CIMHS reduces the computation time of minimization and processes set incrementally,thus improving the whole efficiency in the solving procedure.