Zusammenfassung
Generating minimal hitting sets of a collection of sets is known to be NPhard,
necessitating heuristic approaches to handle large problems. In this paper a low-cost,
approximate minimal hitting set (MHS) algorithm, coined Staccato, is presented. Staccato
uses a heuristic function, borrowed from a lightweight, statistics-based software fault localization
approach, to guide the MHS search. Given the nature of the heuristic function, Staccato is
specially tailored to model-based diagnosis problems (where each MHS solution is a diagnosis to
the problem), although well-suited for other application domains as well. We apply Staccato
in the context of model-based diagnosis and show that even for small problems our approach
is orders of magnitude faster than the brute-force approach, while still capturing all important
solutions. Furthermore, due to its low cost complexity, we also show that Staccato is amenable
to large problems including millions of variables.
Nutzer