A Census of New Snake-in-the-Box Records

Résumé Technique : Un Recensement de Nouveaux Records de « Snake-in-the-Box »

Définition du Problème
Le document traite du problème « snake-in-the-box », formulé à l'origine par Kautz en 1958 dans le contexte des codes de détection d'erreurs. Le problème recherche le plus long chemin induit (sans corde) — appelé « snake » (serpent) — au sein du graphe hypercube $Q_n$. Dans $Q_n$, les sommets représentent des chaînes binaires de longueur $n$, et les arêtes relient les chaînes ne différant que d'une seule coordonnée. Un serpent est défini comme une séquence de sommets distincts où les sommets consécutifs sont adjacents, et où aucun par deux sommets non consécutifs n'est adjacent. La longueur maximale d'un tel chemin est notée $a(n)$.

Le document considère également des structures connexes : les « coils » (spirales ou bobines — cycles induits dans $Q_n$) avec une longueur maximale $b(n)$, et les « symmetric coils » (spirales symétriques — spirales dont la seconde moitié du cycle est le miroir de la première via une opération XOR fixe), avec une longueur maximale $c(n)$. Bien que les valeurs exactes pour $a(n)$ et $b(n)$ soient connues pour les dimensions $n \le 8$, et que $c(n)$ soit connue pour $n \le 7$, le problème reste non résolu pour $n \ge 9$ (et $n \ge 8$ pour les spirales symétriques), où seules des bornes inférieures ont été établies par diverses recherches computationnelles.

Méthodologie et Approche
Les auteurs emploient des efforts computationnels soutenus pour rechercher des serpents, des spirales et des spirales symétriques plus longs dans les dimensions 9 à 13. Le texte fourni ne détaille pas d'architecture algorithmique spécifiquement nouvelle, mais positionne leur travail comme une avancée par rapport aux méthodes précédentes, qui incluaient des algorithmes génétiques, des recherches évolutives basées sur des populations, des constructions basées sur des permutations et des recherches d'arbre de Monte-Carlo.

L'approche des auteurs se concentre sur la génération et la vérification de chemins de longueur record. Ils utilisent une notation standard où un serpent est représenté par une séquence de transition — la liste ordonnée des indices de coordonnées (indexés à partir de 0) inversées le long du chemin. Pour garantir la validité de leurs découvertes, les auteurs fournissent un ensemble de données vérifiable par ordinateur. Ils effectuent également un recensement de l'espace des solutions, comptant le nombre de serpents inéquivalents trouvés aux longueurs records. L'équivalence est déterminée par les symétries de $Q_n$, qui incluent les $n!$ permutations de coordonnées, les $2^n$ translations (XOR) et l'inversion du chemin.

Contributions Clés et Résultats
La contribution principale du document est l'établissement de nouvelles bornes inférieures pour $a(n)$, $b(n)$ et $c(n)$ dans les dimensions 9 à 13, dépassant tous les records précédemment connus.

• Longueurs de Serpents ($a(n)$) : Les auteurs présentent des serpents plus longs que les meilleurs records connus dans chaque dimension de 9 à 13.

  • $n=9$ : Une nouvelle longueur de 191 (améliorant le précédent 190). Les auteurs ont identifié 1 311 serpents inéquivalents de cette longueur.
  • $n=10$ : Une nouvelle longueur de 379 (améliorant le précédent 376).
  • $n=11$ : Une nouvelle longueur de 746 (améliorant le précédent 737).
  • $n=12$ : Une nouvelle longueur de 1 476 (améliorant le précédent 1 465).
  • $n=13$ : Une nouvelle longueur de 2 922 (améliorant le précédent 2 900).
  • Les améliorations varient de +1 à +22 par rapport aux records précédents.

• Longueurs de Spirales ($b(n)$) : Le document rapporte des bornes inférieures améliorées pour les plus longues spirales dans les dimensions 9, 10 et 11, avec de nouvelles longueurs respectives de 192, 374 et 732.

• Longueurs de Spirales Symétriques ($c(n)$) : Des bornes inférieures améliorées sont fournies pour les dimensions 10 et 11, avec de nouvelles longueurs de 370 et 726.

Les auteurs fournissent un exemple concret d'un serpent de longueur 191 dans $Q_9$, en listant sa séquence de transition complète. Ils notent que parmi des millions de serpents échantillonnés de longueur 191, exactement 131 classes de symétrie ont été trouvées pour $n=9$, ce qui les amène à conjecturer qu'aucune autre classe n'existe, bien qu'ils ne fassent aucune affirmation de complétude pour $n \ge 10$.

Signification et Revendications
Le document revendique sa signification principalement par l'avancement empirique des bornes connues pour le problème « snake-in-the-box ». En fournissant des serpents strictement plus longs que tout ce qui était connu auparavant dans les dimensions 9 à 13, les auteurs ont resserré les bornes inférieures de la longueur maximale possible des chemins induits dans les hypercubes.

Leur travail sert de « recensement » de ces nouveaux records, offrant un ensemble de données complet comprenant les séquences de transition spécifiques pour tous les serpents de longueur record trouvés. Cet ensemble de données est rendu public dans un format vérifiable par ordinateur, permettant une vérification indépendante des résultats. Les auteurs présentent leur travail comme une continuation de la lignée computationnelle établie par des chercheurs précédents (tels qu'Ace, Echols, Meyerson et d'autres), repoussant la frontière de ce qui est computationnellement réalisable dans ce problème d'optimisation combinatoire, sans prétendre avoir résolu le problème pour ces dimensions ou avoir prouvé l'optimalité de leurs nouvelles bornes.