Research On Several Algorithms For Computing All Minimal Hitting-sets

Model-based diagnosis is an important branch of artificial intelligence,which overcomes the problems of traditional diagnosis.It does not need the experience of experts,nor too much manpower consumption.Its diagnostic process is relatively independent,and its diagnostic efficiency is generally high,which can cope with the increasingly complex status of equipment in emerging industries.At present,the model-based diagnosis method has been widely used in machinery,medical,communication,aerospace and other fields.Model-based diagnosis can be divided into four steps: system modeling,conflict identification,candidate generation,diagnosis and identification.In the four steps,the efficiency of candidate generation will have a great impact on the solution time of the whole problem.Candidate generation is the process of computing minimal hitting-sets according to known collision sets cluster.Therefore,experts and scholars at home and abroad actively study the minimal hitting-sets problem.They constantly put forward new algorithms,optimize known algorithms,meet the actual needs,and improve the efficiency of solving.The main content of this paper is to solve the problem of minimal hitting-sets.The main research contents are as follows:(1)A method is proposed to obtain the minimal hitting sets by matrix multiplication.First,the rules of transforming luster of conflict sets,candidate solutions and minimal hitting sets into different matrices are defined.Then,matrix multiplication can reveal the properties of minimal hitting sets.Finally,the minimal hitting sets can be found from the candidate solutions.The algorithm does not need to generate tree structure.It only needs simple mathematical calculation.So its data structure and solution process are simple.It has high efficiency.(2)A method is proposed to obtain the minimal hitting sets by paradigm shifting.First,it transforms the luster of conflict sets into the conjunction normal form and the minimal hitting sets into the disjunction normal form.Then,the conjunctive normal form is transformed into disjunctive normal form,so that all minimal hitting sets can be found.In each step,idempotent law and absorption law are used to simplify theoperation,which can reduce the redundant term and improve the solution speed.At the same time,it is an incremental algorithm.Therefore,the calculation is continued based on the known results when a conflict set is added.There is no need to recalculate.This is a practical algorithm for model-based diagnosis.(3)A method is proposed to obtain the minimal hitting sets by minimal covers.It uses the principle of minimal covering to solve the problem step by step until all minimal hitting sets are computed.First,it only needs to repeat the recursive operation.The data structure is stable and simple.Then,it does not produce superset in the process of solving,which can reduce the scale of solving and improve the efficiency of solving.Finally,it gets the minimal hitting set directly.There is no need to delete the superset of the result,which reduces the solution time.(4)A method is proposed to obtain the minimal hitting sets by attribute matrix.It converts a cluster of conflict sets into a matrix of conflict sets.Then,the minimal hitting sets can be obtained by computing the queue structure.It simplifies the queue in the operation process,which can reduce the subsequent operation scale and improve the operation efficiency.Moreover,the space complexity of this algorithm is low,so it will not occupy too much memory.To summarize,the problem of solving the minimal hitting set in the process of model-based diagnosis is studied.A variety of new methods for solving the minimal hitting set are proposed,which provides a new idea for computing the minimal hitting set.