Value Ordering for Finding All Solutions

Smith, Barbara M.; Sturdy, Paula

Value Ordering for Finding All Solutions

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 311-315.

Abstract

In finding all solutions to a constraint satisfaction problem, or proving that there are none, with a search algorithm that backtracks chronologically and forms k-way branches, the order in which the values are assigned is immaterial. However, we show that if the values of a variable are assigned instead via a sequence of binary choice points, and the removal of the value just tried from the domain of the variable is propagated before another value is selected, the value ordering can affect the search effort. We show that this depends on the problem constraints; for some types of constraints, we show that the savings in search effort can be significant, given a good value ordering.

Barbara M. Smith, and Paula Sturdy. 2005. Value Ordering for Finding All Solutions. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 311–315. https://ijcai.org/proceedings/2005/132

@inproceedings{ijcai2005p132,
  title     = {Value Ordering for Finding All Solutions},
  author    = {Smith, Barbara M. and Sturdy, Paula},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {311--315},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/132},
}

TY  - CPAPER
TI  - Value Ordering for Finding All Solutions
AU  - Smith, Barbara M.
AU  - Sturdy, Paula
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 311
EP  - 315
UR  - https://ijcai.org/proceedings/2005/132
ER  -