AbstractA class of search algorithms for problems with symmetries is discussed. The algorithms take as input a symmetry group (in the form of a permutation group) and use it to avoid repeated search of equivalent portions of the search space. The symmetry checking algorithms are variations on a color automorphism algorithm and make use of recent advances in computational group theory to achieve efficient performance. In particular, this paper gives the first algorithm that combines search rearrangement with an arbitrary symmetry group. Experimental results confirm that the algorithms save a considerable amount of time on symmetric search problems.
Categories and Subject Descriptors: G.2.1 [Discrete Mathematics]: Combinatorics; I.1.2 [Algebraic Manipulation]: Algorithms; I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search
Additional Key Words and Phrases: backtracking, symmetry group, search rearrangement backtracking
Selected references
- Cynthia A. Brown, Larry Finkelstein, and Paul W. Purdom, Jr. A new base change algorithm for permutation groups. SIAM Journal on Computing, 18(5):1037-1047, October 1989.
- G. Butler and C. W. H. Lam. A general backtrack algorithm for the isomorphism problem of combinatorial objects. Journal of Symbolic Computation, 1(4):363-382, December 1985.
- Martin Davis and Hilary Putnam. A computing procedure for quantification theory. Journal of the ACM, 7(3):201-215, July 1960.
- Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 59-68, Berkeley, California, 28-30 May 1986.
- J. Hopcroft and J. Musinski. Duality applied to the complexity of matrix multiplication and other bilinear forms. SIAM Journal on Computing, 2(3):159-173, September 1973.
- Mark Jerrum. A compact representation for permutation groups. Journal of Algorithms, 7(1):60-78, March 1986.
- Rodney W. Johnson and Aileen M. McLoughlin. Noncommutative bilinear algorithms for 3 x 3 matrix multiplication. SIAM Journal on Computing, 15(2):595-603, May 1986.
- Eugene M. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42-65, August 1982.
- Paul W. Purdom. Tree size by partial backtracking. SIAM Journal on Computing, 7(4):481-491, November 1978.
- Paul Walton Purdom Jr., Cynthia A. Brown, and Edward L. Robertson. Backtracking with multi-level dynamic search rearrangement. Acta Informatica, 15:99-113, 1981.