Dual Search in Permutation State Spaces
- Uzi Zahavi, Computer Science, Bar-Ilan University, Israel
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Robert Holte, Department of Computing Science, University of Alberta
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
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.
Citation
U. Zahavi, A. Felner, R. Holte, J. Schaeffer. "Dual Search in Permutation State Spaces". National Conference on Artificial Intelligence (AAAI), Boston, Massachusetts, USA, pp 1076-1081, January 2006.| Keywords: | permutation |
| Category: | In Conference |
BibTeX
@incollection{Zahavi+al:AAAI06,
author = {Uzi Zahavi and Ariel Felner and Robert Holte and Jonathan
Schaeffer},
title = {Dual Search in Permutation State Spaces},
Pages = {1076-1081},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2006,
}Last Updated: June 04, 2007Submitted by Staurt H. Johnson
