| publications

R161a
Approximate Solution Sampling (and Counting) on AND/OR spaces

Vibhav Gogate and Rina Dechter

Abstract
In this paper, we describe a new algorithm for sampling solutions from a uniform distribution over the solutions of a constraint network. Our new algorithm improves upon the Sampling/Importance Resampling (SIR) component of our previous scheme of SampleSearch-SIR by taking advantage of the decomposition implied by the network’s AND/OR search space.We also describe how our new scheme can approximately count and lower bound the number of solutions of a constraint network. We demonstrate both theoretically and empirically that our new algorithm yields far better performance than competing approaches.

[pdf]