Domain Filtering can Degrade Intelligent Backtracking Search
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction Problems. Pages 262-266.
Abstract
This paper presents an improved backjumping algorithm for the constraint satisfaction problem, namely conflictdirected backjumping (CBJ). CBJ is then modified such that it can detect infeasible values and removes them from the domains of variables once and for all. A similar modification is then made to Gaschnig's backjumping routine BJ and to Haralick and Elliott's forward checking routine FC. Empirical analysis shows that these modifications tend to result in an improvement in average performance. The existence of a peculiar phenomenon is then shown: the removal of infeasible values may result in a degradation in the performance of intelligent backjumping algorithms, and conversely the addition of infeasible values may lead to an improvement in performance.
@inproceedings{ijcai1993p37,
title = {Domain Filtering can Degrade Intelligent Backtracking Search},
author = {Prosser, Patrick},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {262--266},
year = {1993},
note = {Constraint Satisfaction Problems},
url = {https://ijcai.org/proceedings/1993/37},
}
TY - CPAPER TI - Domain Filtering can Degrade Intelligent Backtracking Search AU - Prosser, Patrick T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 262 EP - 266 UR - https://ijcai.org/proceedings/1993/37 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
