ML Anthology

Value Ordering for Finding All Solutions

Barbara M. Smith, Paula Sturdy
IJCAI 2005 pp. 311-316
/ijcai/2005/smith2005ijcai-value/

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. 1

PDF Semantic Scholar

Cite

Text

Smith and Sturdy. "Value Ordering for Finding All Solutions." International Joint Conference on Artificial Intelligence, 2005.

Markdown

[Smith and Sturdy. "Value Ordering for Finding All Solutions." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/smith2005ijcai-value/)

BibTeX

@inproceedings{smith2005ijcai-value,
  title     = {{Value Ordering for Finding All Solutions}},
  author    = {Smith, Barbara M. and Sturdy, Paula},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2005},
  pages     = {311-316},
  url       = {https://mlanthology.org/ijcai/2005/smith2005ijcai-value/}
}