Approximate inference for clusters in solution spaces
Lukáš Kroc, Ashish Sabharwal, Bart Selman · National Conference on Artificial Intelligence · 2010
This work proposes new approximate (and exact) inference methods for reasoning about an important and hard-to-compute property of the solution space of combinatorial problems, namely clusters of solutions. Given a constraint satisfaction problem (CSP), we can think of two solutions as being if they differ in the value of only one variable. Clusters of solutions can thus be defined in a natural manner: two solutions s1 and s2 are in the same cluster if and only if there is a path of connected solutions from s1 to s2. The main question we seek to address is, given a CSP, how many solution clusters does it have?.