Consistent-Labeling Problems and Their Algorithms

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 2

Problem Solving and Search

Two new classes of theories have been developed giving the expected complexities of three Consistent-Labeling Problem (CLP), or Constraint-Satisfaction, algorithms: Backtracking, Forward Checking and Word-wise Forward Checking. Apart from giving the exact expected complexity for these algorithms for the underlying CLP distribution and domain, these theories provide useful approximations for the complexity of solving essentially any individual CLP. Given this, and the fact that the theories can reflect changes in complexity due to changes in the ordering of variables used in the search, these theories have the potential to afford significant savings for any individual CLP, by predicting, prior to search, good orderings for use in solving that CLP. We are concurrently developing improved CLP algorithms based on this and similar ordering effects.