An analysis of hypercube space for solving the snake-in-the-box problem
MetadataShow full item record
Finding the longest snakes and coils in a hypercube is a difficult and computationally complicated problem to solve. As higher dimension hypercubes are explored, the problem quickly grows beyond the capabilities of exhaustive search techniques. Previous research has attempted to maximize the length of snakes and coils (open and closed paths, respectively) with Artificial Intelligence (AI) techniques, especially the Genetic Algorithm (GA). Using the GA, researchers have generally represented the individual solutions (i.e. paths) as sequences of nodes visited in the hypercube, or as transitions. However, it appears that current methods are approaching their limits. Therefore, this thesis explores characteristics of n-dimensional hypercubes and properties of longest maximal snakes as they pass through hypercubes in order to facilitate discovery of new search methods through a better understanding of hypercube space. This thesis also introduces a new search scheme that separates the hypercube nodes into various levels based on Pascal's triangle.