Bayes Networks for Estimating the Number of Solutions to a CSP

Amnon Meisels, Solomon Eyal Shimony, Gadi Solotorevsky

The problem of counting the number of solutions to a constraint satisfaction problem (CSP) is rephrased in terms of probability updating in Bayes networks. Approximating the probabilities in Bayes networks is a problem which has been studied for a while, and may well provide a good approximation to counting the number of solutions. We use a simple approximation based on independence, and show that it is correct for tree-structured CSPs. For other CSPs, it is a less optimistic approximation than those suggested in prior work, and experiments show that it is more accurate on the average. We present empirical evidence that our approximation is a useful search heuristic for finding a single solution to a CSP.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.