Look-Ahead Value Ordering for Constraint Satisfaction Problems
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 572-577.
Abstract
Looking ahead during search is often useful when solving constraint satisfaction problems. Previous studies have shown that looking ahead helps by causing dead-ends to occur earlier in the search, and by providing information that is useful for dynamic variable ordering. In this paper, we show that another benefit of lo?king ahead is a useful domain value ordermg heuristic, which we call look-ahead value ordering or LVO. LVO counts the number of times each value of the current variable conflicts with some value of a future variable, and the value with the lowest number of conflicts is chosen first. Our experiments show that look-ahead value ordering can be of substantial benefit, especially on hard constraint satisfaction problems.
@inproceedings{ijcai1995p75,
title = {Look-Ahead Value Ordering for Constraint Satisfaction Problems},
author = {Frost, Daniel and Dechter, Rina},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {572--577},
year = {1995},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1995/75},
}
TY - CPAPER TI - Look-Ahead Value Ordering for Constraint Satisfaction Problems AU - Frost, Daniel AU - Dechter, Rina T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 572 EP - 577 UR - https://ijcai.org/proceedings/1995/75 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
