A parameter matrix based approach to computing minimal hitting sets

Computing all minimal hitting sets is one of the key steps in model-based diagnosis. Because of the low capabilities due to the expansion of state space in large-scale system diagnosis, more efficient approximation algorithms are in motivation. A matrix-based minimal hitting set (M-MHS) algorithm is proposed in this paper. A parameter matrix records the relationships between elements and sets and the initial problem is divided into several sub-problems by decomposition. The efficient prune rules avoid the computation of the sub-problems without solutions. Parameterized way and de-parameterized way are both given so that the more suitable algorithm could be chosen according to the cases. The simulation results show that, the proposed algorithm outperforms HSSE and BNB-HSSE in large-scale problems and keeps a relatively stable performance when data changes in different regulations. The algorithm provides a valuable tool for computing hitting sets in model-based diagnosis of large-scale systems.