Dual Search in Permutation State Spaces

Uzi Zahavi, Ariel Felner, Robert C. Holte, Jonathan Schaeffer

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, em 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.

Subjects: 15.7 Search

Submitted: May 30, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.