|
|
A099155
|
|
Maximum length of a simple path with no chords in the n-dimensional hypercube, also known as snake-in-the-box problem.
|
|
9
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Some confusion seems to exist in the distinction between n-snakes and n-coils. Earlier papers and also A000937 used "snake" to mean a closed path, which is called n-coil in newer notation, see Harary et al. a(8) is conjectured to be 97 by Rajan and Shende. [The true value, however, is 98. See Ostergard and Ville, 2014. - N. J. A. Sloane, Apr 06 2014]
Longest open achordal path in n-dimensional hypercube.
After 50, lower bounds on the next terms are 97, 186, 358, 680, 1260. - Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005
The length of the longest known snake (open path) in dimension 8 (as of December, 2009) is 98. It was found by B. Carlson (confirmed by W. D. Potter) and soon to be reported in the literature. Numerous 97-length snakes are currently published. - W. D. Potter (potter(AT)uga.edu), Feb 24 2009
|
|
REFERENCES
|
B. P. Carlson, D. F. Hougen: Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes. In: Proc. 12th Annu. Conf. Genetic and Evolutionary Computation, pp. 791-798 (2010). [Shows a(8) >= 98. - N. J. A. Sloane, Apr 06 2014]
D. Casella and W. D. Potter, "New Lower Bounds for the Snake-in-the-box Problem: Using Evolutionary Techniques to Hunt for Coils". Submitted to IEEE Conference on Evolutionary Computing, 2005.
|
|
LINKS
|
Potter, W. D., R. W. Robinson, J. A. Miller, K. J. Kochut and D. Z. Redys, 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, pp. 421-426, Austin, Texas, 1994.
|
|
EXAMPLE
|
a(3)=4: Path of a longest 3-snake starts at 000 and then visits 100 101 111 011.
a(4)=7: Path of a longest 4-snake: 0000 1000 1010 1110 0110 0111 0101 1101.
See figures 1 and 2 in Rajan-Shende.
|
|
CROSSREFS
|
Cf. A000937 = length of maximum n-coil.
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(8) from Patric R. J. Östergård and V. H. Pettersson (2014). - N. J. A. Sloane, Apr 06 2014
|
|
STATUS
|
approved
|
|
|
|