(PDF)
Jonathan Sillito.
Improvements to and estimating the cost of backtracking
algorithms for constraint satisfaction problems.
MSc thesis,
University of Alberta, Department of Computing Science,
2000.
A constraint satisfaction problem can be solved using a variety of algorithms. An important class of such algorithms are categorized as arc consistency algorithms. General arc consistency (gac) is the most common algorithm in this class. Bessiere and Regin have recently proposed gac as a more sophisticated general arc consistency algorithm. In this thesis an evaluation of gac is presented. In this thesis we also present work in the area of estimating the cost of solving constraint satisfaction problems. Some existing work in this area is evaluated. We also develop an estimation technique, based on statistical sampling algorithms by Knuth and Purdom. Applications for this technique are discussed, and we demonstrate the usefulness of our estimator as a dynamic variable ordering.