Backtracking and random constraint satisfaction |
| |
Authors: | Paul Walton Purdom |
| |
Affiliation: | (1) Computer Science Department, Indiana University, Bloomington, IN 47405, USA |
| |
Abstract: | The average running time used by backtracking on random constraint satisfaction problems is studied. This time is polynomial
when the ratio of constraints to variables is large, and it is exponential when the ratio is small. When the number of variables
goes to infinity, whether the average time is exponential or polynomial depends on the number of variables per constraint,
the number of values per variable, and the probability that a random setting of variables satisfies a constraint. A method
for computing the curve that separates polynomial from exponential time and several methods for approximating the curve are
given. The version of backtracking studied finds all solutions to a problem, so the running time is exponential when the number
of solutions per problem is exponential. For small values of the probability, the curve that separates exponential and polynomial
average running time coincides with the curve that separates an exponential average number of solutions from a polynomial
number. For larger probabilities the two curves diverge. Random problems similar to those that arise in understanding line
drawings with shadows require a time that is mildly exponential when they are solved by simple backtracking. Slightly more
sophisticated algorithms (such as constraint propagation combined with backtracking) should be able to solve these rapidly.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|