Added to Favorites

Related Searches

The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner after it's been marked unusable.

In graph theory terminology, this is called finding the longest possible induced path in a hypercube; it can be viewed as a special case of the induced subgraph isomorphism problem. There is a similar problem of finding long induced cycles in hypercubes, called the coil-in-the-box problem.

The snake-in-the-box problem was first described by , motivated by the theory of error-correcting codes. The vertices of a solution to the snake or coil in the box problems can be used as a Gray code that can detect single-bit errors. Such codes have applications in electrical engineering, coding theory, and computer network topologies. In these applications, it is important to devise as long a code as is possible for a given dimension of hypercube. The longer the code, the more effective are its capabilities.

Finding the longest snake or coil becomes notoriously difficult as the dimension number increases and the search space suffers a serious combinatorial explosion. Some techniques for determining the upper and lower bounds for the snake-in-the-box problem include proofs using discrete mathematics and graph theory, exhaustive search of the search space, and heuristic search utilizing evolutionary techniques.

The maximum length for the snake-in-the-box problem is known for dimensions one through seven; it is

- 1, 2, 4, 7, 13, 26, 50 .

- 97, 188, 363, 680, 1260.

For cycles (the coil-in-the-box problem), a cycle cannot exist in a hypercube of dimension less than two. Starting at that dimension, the lengths of the longest possible cycles are

- 4, 6, 8, 14, 26, 48 .

- 96, 180, 344, 630, 1238.

For both the snake and the coil in the box problems, it is known that the maximum length is proportional to 2^{n} for an n-dimensional box, asymptotically as n grows large. However the constant of proportionality is not known.

- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- Potter, W. D.; Robinson, R. W.; Miller, J. A.; Kochut, K. J.; Redys, D. Z. "Using the genetic algorithm to find snake in the box codes".
*Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, Austin, Texas*, 421–426. . - .
- (In Russian).
- Tuohy, D.R.; Potter, W.D.; Casella, D.A. "Searching for Snake-in-the-Box Codes with Evolved Pruning Models".
*Proceedings of the 2007 Int. Conf. on Genetic and Evolutionary Methods (GEM'2007), Las Vegas, Nevada*, 3-9. . - .
- Yang, Yuan Sheng; Sun, Fang; Han, Song (2000). "A backward search algorithm for the snake in the box problem".
*J. Dalian Univ. Technol.*40 (5): 509–511. - .
- .

- Yang, Yuan Sheng; Sun, Fang; Han, Song (2000). "A backward search algorithm for the snake in the box problem".

- Tuohy, D.R.; Potter, W.D.; Casella, D.A. "Searching for Snake-in-the-Box Codes with Evolved Pruning Models".

- (In Russian).

- Potter, W. D.; Robinson, R. W.; Miller, J. A.; Kochut, K. J.; Redys, D. Z. "Using the genetic algorithm to find snake in the box codes".

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- .

- Potter, W. D. Current Records for the Snake-in-the-Box Problem. (2006). .

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday June 30, 2008 at 02:08:35 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday June 30, 2008 at 02:08:35 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.