Parameter matrix-based approach to computing all minimal hitting sets

Computing all minimal hitting sets is one of the key steps in model-based diagnosis. Because of the limitations of parameterized algorithms and the low capabilities due to the expansion of state space in large-scale system diagnosis, a generalized minimal hitting-set algorithm named matrix-based minimal hitting set (M-MHS) algorithm was proposed. The parameter matrix was used to record the relationships between elements and sets, and the initial problem was broaken into several sub-problems by matrix decomposition. The computation of the sub-problems without solutions was avoided by the efficient prune rules. The simulation results show that all minimal hitting sets can be found. Compared with HSSE(hitting set-set enumeration) and de-parameterized BNB-HSSE(branch and bound-HSSE), the proposed algorithm has advantages in large scale computations and can keep relatively stable when data changes. The algorithm is a feasible means for computing all hitting sets in model-based diagnosis of large-scale systems.