Deriving all minimal hitting-sets by merging
Xiangfu Zhao, Dantong Ouyang · 2016
Deriving all minimal hitting-sets (MH-Ses), as candidate diagnoses, is an active topic in model-based diagnosis. Based on the “Divide and Conquer” principle, an algorithm for computing all MHSes by recursive merging is proposed. First, each given (large) family of conflict sets is divided into two smaller sub-families, every one of which is used for computing its own MHSes, respectively. Then, the cross-product of the two corresponding sub-families of MHSes is generated. Finally, the family of MHSes for the whole conflict sets is obtained, only with the additional final step: minimizing the product. Detailed theoretical analysis of time complexity is given in different cases. Experimental results show that our approach has better efficiency than other approaches in many cases.