New lower bounds for the Snake-in-the-Box Problem a Prolog Genetic Algorithm and heuristic search approach /

by (Derrick Scott), 1973- Bitterman

This project establishes new lower bounds (new longest snakes and coils) for the Snake- In-The-Box problem in a hypercube of nine dimensions. The lengths obtained exceed any reported in the current literature. Three important methods or tools were used: the Prolog programming language, a Genetic Algorithm, and traditional search including depth limited and a heuristic search called the Narrowest Path Heuristic. These methods were used in conjunction and expand on others previously tried. The Snake-In-The-Box problem consists of finding the longest simple non-cyclical path (a snake) or the longest simple cyclical path (a coil) in an d-dimensional hypercube without chords. The longer the Snake the better. The Snake-In-The-Box problem has a range of practical applications including error detection in analog-to-digital conversion and encryption technology. Studying computational approaches to this constraint satisfaction problem and attempting to find good solutions (long snakes or coils) has theoretical value as well. The Snake Problem belongs to a set of problems known to be non-deterministically polynomial (NP). Due to exponential and explosive growth in the search space, finding solutions to such problems is notoriously difficult. Attempts to find long snakes in hypercubes of dimensions higher than seven have since required non-traditional or heuristic search. Evaluating new approaches to solving a constraint satisfaction problem in NP has theoretical import to other similar problems, and perhaps all problems that are NP. Index words: Snake-In-The-Box, Evolutionary Programming, Genetic Algorithm, Heuristic Search, Constraint Satisfaction, Prolog, Hypercube, Graph Theory New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach by D. Scott Bitterman B.A., Spring Hill College, 1995 A Thesis Submitted to the Graduate Faculty of The University of Georgia in Partial Fulfillment of the Requirements for the Degree Master of Science Athens, Georgia 2004 c? 2004 D. Scott Bitterman All Rights Reserved New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach by D. Scott Bitterman Approved: Major Professor: Walter D. Potter Committee: Michael A. Covington Charles Cross Electronic Version Approved: Maureen Grasso Dean of the Graduate School The University of Georgia December 2004