A sufficient condition for backtrack-bounded search
1985; Association for Computing Machinery; Volume: 32; Issue: 4 Linguagem: Inglês
10.1145/4221.4225
ISSN1557-735X
Autores Tópico(s)AI-based Problem Solving and Planning
ResumoBacktrack search is often used to solve constraint satisfaction problems. A relationship involving the structure of the constraints is described that provides a bound on the backtracking required to advance deeper into the backtrack tree. This analysis leads to upper bounds on the effort required for solution of a class of constraint satisfaction problems. The solutions involve a combination of relaxation preprocessing and backtrack search. The bounds are expressed in terms of the structure of the constraint connections. Specifically, the effort is shown to have a bound exponential in the size of the largest biconnected component of the constraint graph, as opposed to the size of the graph as a whole.
Referência(s)