Snake-in-the-box

From Wikipedia, the free encyclopedia

Drawing of a snake in a three-dimensional hypercube.

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. Start at one corner and travel along the edges to as many corners as you can. After you get to a new corner, you must mark the corner you just came from and all of its neighbors as unusable. Never travel to a corner after you've marked it unusable.

In graph theory terminology, this is called finding the longest possible induced path in a hypercube. There is a similar problems of finding long induced cycles in hypercubes is called the coil-in-the-box problem.

The snake-in-the-box problem was first described by W. H. Kautz (1958), 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 that is as possible for a given dimension of hypercube.

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.

[edit] Known lengths and bounds

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 (sequence A099155 in OEIS).

Beyond that length, the exact length of the longest snake is not known; the best lengths found so far for dimensions eight through twelve are

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 (sequence A000937 in OEIS).

Beyond that length, the exact length of the longest cycle is not known; the best lengths found so far for dimensions eight through twelve are

96, 180, 344, 630, 1238.

Many of the best-known lower bounds for dimensions nine through twelve for both problems were found using a hybrid genetic algorithm developed by Darren Casella at the University of Georgia's Artificial Intelligence Center.

[edit] References

Abbott, H. L.; Katchalski, M. (1988). "On the snake in the box problem". Journal of Combinatorial Theory, Series B 44: 12–24.

Abbott, H. L.; Katchalski, M. (1991). "On the construction of snake-in-the-box codes". Utilitas Mathematica 40: 97–116.

Bitterman, D. S. (2004). "New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach". MSAI thesis. Univ. of Georgia.

Blaum, Mario; Etzion, Tuvi (2002). "Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive". U.S. Patent 6,496,312 .

Casella, D. A.; Potter, W. D. (2005). "Using Evolutionary Techniques to Hunt for Snakes and Coils". 2005 IEEE Congress on Evolutionary Computation (CEC2005) 3: 2499–2504.

Casella, D. A. (2005). "New Lower Bounds for the Snake-in-the-Box and the Coil-in-the-Box Problems". MSAI thesis. Univ. of Georgia.

Danzer, L.; Klee, V. (1967). "Length of snakes in boxes". Journal of Combinatorial Theory 2: 258–265.

Davies, D. W. (1965). "Longest 'separated' paths and loops in an N-cube". IEEE Trans. Electron. Comput. EC-14: 261.

Evdokimov, A. A. (1969). "Maximal length of a chain in a unit n-dimensional cube". Mat. Zametki 6: 309–319.

Kautz, W. H. (1958). "Unit-distance error-checking codes". IRE Trans. Elect. Comput. 7: 177–180.

Kim, S.; Neuhoff, D.L. (2000). "Snake-in-the-box codes as robust quantizer index assignments". Proceedings of the IEEE International Symposium on Information Theory: 402. DOI:10.1109/ISIT.2000.866700.

Klee, V. (1970). "What is the maximum length of a d-dimensional snake?". American Mathematical Monthly 77: 63–65.

Kochut, K. J. (1996). "Snake-in-the-box codes for dimension 7". Journal of Combinatorial Mathematics and Combinatorial Computing 20: 175–185.

Lukito, A.; van Zanten, A. J. (2001). "A new non-asymptotic upper bound for snake-in-the-box codes". Journal of Combinatorial Mathematics and Combinatorial Computing 39: 147–156.

Paterson, Kenneth G.; Tuliani, Jonathan (1998). "Some new circuit codes". IEEE Trans. Inform. Theory 44 (3): 1305–1309.

Potter, W. D.; Robinson, R. W.; Miller, J. A.; Kochut, K. J.; Redys, D. Z. (1994). "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.

Snevily, H. S. (1994). "The snake-in-the-box problem: a new upper bound". Discrete Mathematics 133: 307–314.

Solovćeva, F. I. (1987). "An upper bound on the length of a cycle in an n-dimensional unit cube" (Russian). Metody Diskret. Analiz. 45: 71–76 and 96–97.

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.