Troubleshooting: NP-hardness and solution methods
Troubleshooting is one of the areas where Bayesian networks are successfully applied [9]. In this paper we show that the generally defined troubleshooting task is NP-hard. We propose a heuristic function that exploits the conditional independence of all actions and questions given the fault of the device. It can be used as a lower bound of the expected cost of repair in heuristic algorithms searching an optimal troubleshooting strategy. In the paper we describe two such algorithms: the depth first search algorithm with pruning and the AO* algorithm.
bayesian networks decision-theoretic troubleshooting computational complexity