Increasing Tree Search Efficiency for Constraint Satisfaction Problems
Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .
Abstract
In this paper we explore the number of consistency checks made by a tree sear c h in o rder t o solve binary constraint satisfaction problems. l~e show analytically and experimentally that the two principles of first trying the pla c es most likely to fail and remembering wh a t ha s be en done to avoid repeating the same mistake twice improve the standard backtrac k ing sear c h. We experimentally show that a lookahead pro c edure called forward c hecking (to remember the future) which employs the most likely to fail principle performs better than standard b ac ktracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all c ases t e sted, and better than Gaschnigs backmarking in the larger problems.
@inproceedings{ijcai1979p78,
title = {Increasing Tree Search Efficiency for Constraint Satisfaction Problems},
author = {Haralick, Robert M. and Elliott, Gordon L.},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/78},
}
TY - CPAPER TI - Increasing Tree Search Efficiency for Constraint Satisfaction Problems AU - Haralick, Robert M. AU - Elliott, Gordon L. T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/78 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
