ML Anthology

Dual Search in Permutation State Spaces

Uzi Zahavi, Ariel Felner, Robert Holte, Jonathan Schaeffer
AAAI 2006 pp. 1076-1081
/aaai/2006/zahavi2006aaai-dual/

Abstract

Geometrical symmetries are commonly exploited to improve the efficiency of search algorithms. We introduce a new logical symmetry in permutation state spaces which we call duality. We show that each state has a dual state. Both states share important attributes and these properties can be used to improve search efficiency. We also present a new search algorithm, dual search, which switches between the original state and the dual state when it seems likely that the switch will improve the chances of a cutoff. The decision of when to switch is very important and several policies for doing this are investigated. Experimental results show significant improvements for a number of applications.

PDF AAAI Semantic Scholar

Cite

Text

Zahavi et al. "Dual Search in Permutation State Spaces." AAAI Conference on Artificial Intelligence, 2006.

Markdown

[Zahavi et al. "Dual Search in Permutation State Spaces." AAAI Conference on Artificial Intelligence, 2006.](https://mlanthology.org/aaai/2006/zahavi2006aaai-dual/)

BibTeX

@inproceedings{zahavi2006aaai-dual,
  title     = {{Dual Search in Permutation State Spaces}},
  author    = {Zahavi, Uzi and Felner, Ariel and Holte, Robert and Schaeffer, Jonathan},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2006},
  pages     = {1076-1081},
  url       = {https://mlanthology.org/aaai/2006/zahavi2006aaai-dual/}
}