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

技术摘要：新蛇入盒（Snake-in-the-Box）记录普查

问题定义
本文研究了由 Kautz 在 1958 年针对纠错码提出的“蛇入盒”（snake-in-the-box）问题。该问题旨在寻找超立方体图 $Q_n$ 中最长的诱导（无弦）路径，这种路径被称为“蛇”。在 $Q_n$ 中，顶点表示长度为 $n$ 的二进制字符串，边连接仅在一个坐标上不同的字符串。蛇被定义为一个由不同顶点组成的序列，其中相邻顶点相邻，且任何两个非连续顶点之间都不相邻。此类路径的最大长度记作 $a(n)$。

论文还考虑了相关的结构：“线圈”（coils，即 $Q_n$ 中的诱导环），其最大长度为 $b(n)$；以及“对称线圈”（symmetric coils，即通过固定异或运算使环的后半部分镜像前半部分的线圈），其最大长度为 $c(n)$。虽然对于维度 $n \le 8$ 的 $a(n)$ 和 $b(n)$ 以及 $n \le 7$ 的 $c(n)$ 已知精确值，但对于 $n \ge 9$（以及 $n \ge 8$ 的对称线圈）而言，该问题仍未解决，目前仅通过各种计算搜索建立了下界。

方法论与途径
作者通过持续的计算工作，在维度 9 到 13 之间搜索更长的蛇、线圈和对称线圈。文中并未详细介绍特定的创新算法架构，而是将其定位为对以往方法（包括遗传算法、基于种群的进化搜索、基于置换的构造以及蒙特卡洛树搜索）的改进。

作者的方法侧重于生成并验证记录长度的路径。他们使用一种标准记法，将蛇表示为一个转换序列——即沿路径翻转的 0 索引坐标索引的有序列表。为了确保研究结果的有效性，作者提供了一个计算机可验证的数据集。此外，他们还对解空间进行了普查，统计了在记录长度下发现的不等价蛇的数量。等价性由 $Q_n$ 的对称性决定，这些对称性包括 $n!$ 个坐标置换、$2^n$ 个平移（异或运算）以及路径反转。

主要贡献与结果
本文的主要贡献是建立了维度 9 到 13 中 $a(n)$、$b(n)$ 和 $c(n)$ 的新下界，超越了此前所有已知的记录。

• 蛇的长度 ($a(n)$): 作者展示了在维度 9 到 13 中均比此前已知最佳长度更长的蛇。

  • $n=9$: 新长度为 191（优于之前的 190）。作者识别出 1,311 条该长度下的不等价蛇。
  • $n=10$: 新长度为 379（优于之前的 376）。
  • $n=11$: 新长度为 746（优于之前的 737）。
  • $n=12$: 新长度为 1,476（优于之前的 1,465）。
  • $n=13$: 新长度为 2,922 (优于之前的 2,900)。
  • 这些改进幅度在 1 到 22 之间。

• 线圈长度 ($b(n)$): 论文报告了维度 9、10 和 11 中最长线圈的改进下界，新长度分别为 192、374 和 732。

• 对称线圈长度 ($c(n)$): 为维度 10 和 11 提供了改进的下界，新长度分别为 370 和 726。

作者提供了一个 $Q_9$ 中长度为 191 的蛇的具体示例，列出了其完整的转换序列。他们指出，在数百万个采样的长度为 191 的蛇中，对于 $n=9$ 正好发现了 131 个对称类，由此提出了一个猜想，即不存在其他类别，但并未对 $n \ge 10$ 做出类似的完备性声明。

意义与主张
本文的意义主要在于通过在维度 9 到 13 之间实现已知界限的经验性提升。通过提供在维度 9 到 13 中严格长于以往已知记录的蛇，作者收紧了超立方体中最大可能诱导路径长度的下界。

这项工作作为这些新记录的“普查”，提供了一个包含所有发现的不同记录长度蛇的具体转换序列的综合数据集。该数据集以计算机可验证的格式公开，允许进行独立验证。作者将他们的工作视为前人（如 Ace、Echols、Meyerson 等人）所建立的计算谱系的延续，在没有声称解决了这些维度的难题或证明了其新界限的最优性的情况下，推动了这一组合优化问题的计算前沿。