Increasing Tree Search Efficiency for Constraint Satisfaction Problems
Abstract
In this paper we explore the number of tree search operations required to solve binary constraint satisfaction problems. We show analytically and experimentally that the two principles of first trying the places most likely to fail and remembering what has been done to avoid repeating the same mistake twice improve the standard backtracking search. We experimentally show that a lookahead procedure called forward checking (to anticipate the future) which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.
Cite
Text
Haralick and Elliott. "Increasing Tree Search Efficiency for Constraint Satisfaction Problems." International Joint Conference on Artificial Intelligence, 1979. doi:10.1016/0004-3702(80)90051-XMarkdown
[Haralick and Elliott. "Increasing Tree Search Efficiency for Constraint Satisfaction Problems." International Joint Conference on Artificial Intelligence, 1979.](https://mlanthology.org/ijcai/1979/haralick1979ijcai-increasing/) doi:10.1016/0004-3702(80)90051-XBibTeX
@inproceedings{haralick1979ijcai-increasing,
title = {{Increasing Tree Search Efficiency for Constraint Satisfaction Problems}},
author = {Haralick, Robert M. and Elliott, Gordon L.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1979},
pages = {356-364},
doi = {10.1016/0004-3702(80)90051-X},
url = {https://mlanthology.org/ijcai/1979/haralick1979ijcai-increasing/}
}