New Lower Bounds for the Snake-in-the-Box Problem: Using Evolutionary Techniques to Hunt for Snakes

D. A. Casella and W. D. Potter, University of Georgia

The snake-in-the-box problem is a difficult problem in mathematics and computer science that was first described by Kautz in the late 1950’s (Kautz 1958). Snake-in-the-box codes have many applications in electrical engineering, coding theory, and computer network topologies. Generally, the longer the snake for a given dimension, the more useful it is in these applications (Klee 1970). By applying a relatively recent evolutionary search algorithm known as a population-based stochastic hill-climber, new lower bounds were achieved for the longest snake in each of the dimensions nine through twelve and the longest coil in each of the dimensions nine through eleven.


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.