Snake-in-the-Box 数据集

Name: Snake-in-the-Box 数据集
Creator: 加州理工学院; 苏黎世大学; 帝国理工学院; 剑桥大学·计算机科学与技术系; 伦敦数学科学研究所
Published: 2026-07-17T01:57:52+08:00

arXiv2026-07-17 更新2026-07-18 收录

超立方体路径优化

错误检测编码

数据链接：

https://github.com/Math-AI-Caltech/Snake-in-the-Box 数据链接链接失效反馈

官方服务：

资源简介：

该数据集由加州理工学院等研究机构创建，专注于超立方体图中最长诱导路径（即“蛇”）问题的计算记录。数据集包含了在维度9至13中打破先前记录的最长蛇路径、线圈及对称线圈的转移序列，具体数据量未明确说明，但提供了例如在Q9维度中的131条独特蛇路径实例。数据通过计算搜索与优化算法生成，旨在为组合数学、图论及错误检测编码领域提供基准参考，推动超立方体结构中最长路径问题的理论边界与算法研究。

This dataset was developed by research institutions including the California Institute of Technology (Caltech), focusing on computational records of the longest induced path problem, also known as the "snake" problem, in hypercube graphs. It includes transition sequences of the longest snake paths, cycles, and symmetric cycles that broke prior records across dimensions 9 to 13. The exact scale of the dataset is not specified, but it provides, for example, 131 unique snake path instances for the 9-dimensional hypercube (Q9). The data was generated using computational search and optimization algorithms, with the goal of providing benchmark references for the fields of combinatorial mathematics, graph theory, and error-detection coding, as well as advancing research on the theoretical limits and algorithmic aspects of the longest path problem in hypercube structures.

提供机构：

加州理工学院; 苏黎世大学; 帝国理工学院; 剑桥大学·计算机科学与技术系; 伦敦数学科学研究所

创建时间：

2026-07-17

原始信息汇总

数据集概述

本数据集对应论文《A Census of New Snake-in-the-Box Records》，旨在记录超立方体图（hypercube graph）中新的蛇形路径（Snake）和线圈（Coil）记录。蛇形路径问题是Kautz于1958年提出的，要求在超立方体图 $Q_n$ 中找到最长的诱导路径（无弦路径），其最大长度 $a(n)$ 仅对 $n leq 8$ 已知。本数据集在维度9至13中给出了比以往最佳结果更长的蛇形路径，以及最长的线圈（诱导环）。每条记录均为机器可验证的 $Q_n$ 顶点列表。

数据集内容

数据集包含三个CSV文件：

1. 蛇形路径（Snakes）：`record_snakes.csv`

n	新长度 a(n)	先前最佳	增量 Δ	记录长度的不同类数量
9	191	190	+1	131
10	379	376	+3	≥ 12
11	746	737	+9	≥ 72
12	1476	1465	+11	≥ 34,688
13	2924	2900	+24	≥ 30

注：维度9的131个类基于数百万次抽样，被认为构成完整普查；对于 $n geq 10$，不做完整性声明。

2. 线圈（Coils）：`record_coils.csv`

n	新长度	先前最佳	增量 Δ	记录长度的不同类数量
9	192	188	+4	≥ 1
10	374	370	+4	≥ 12
11	732	728	+4	≥ 2
12	1466	1442	+24	≥ 5

3. 对称线圈（Symmetric coils）：`record_symmetric_coils.csv`

n	新长度	先前最佳	增量 Δ	记录长度的不同类数量
10	370	362	+8	≥ 2
11	726	718	+8	≥ 1

“不同类”计数指在 $Q_n$ 的全对称群（包括平移、轴排列、反转以及线圈的旋转）下的不同等价类。维度9的131个类被认为是完整普查；其他蛇形路径计数为迄今发现的不同类（下界）。

文件格式

所有CSV文件包含以下列：

n：超立方体维度。
length：对于蛇形路径，为边数（等于行动序列长度）；对于线圈，为顶点数（等于边数）。
actions：转换序列：从原点开始，依次翻转指定坐标。
vertices：顶点列表（整数），被归一化为从0开始，因此从0应用actions序列可精确复现vertices。

搜集汇总

数据集介绍

构建方式

Snake-in-the-Box 数据集由 Paul Orland 等人基于超立方体图 Q_n 中诱导路径的搜索构建而成。研究者采用计算机搜索方法，在维度 n=9 至 13 范围内系统性地枚举并验证了长度超过已知记录的蛇形路径。每个路径以坐标翻转的转移序列形式记录，例如 Q_9 中长度为191的蛇形路径包含191个转移。数据集通过对称性约简确保路径的独特性，最终收录了各维度下达到新下界的所有不等价蛇形路径、线圈和对称线圈。

特点

该数据集的核心特点在于其记录的蛇形路径长度超越了当前所有已知的最佳下界，从而显著提升了超立方体图中蛇形问题在维度9至13的理论下界。数据集内包含大量不等价路径，例如在 Q_9 中发现了131条长度为191的独特蛇形路径，在 Q_{12} 中则超过3.1万条。此外，数据集还收录了长度超越前记录的线圈和对称线圈，为相关理论研究提供了丰富的验证样本。

使用方法

使用者可通过公开的 GitHub 仓库获取数据集，仓库内含三个文件，分别对应蛇形路径、线圈和对称线圈的转移序列。每一条路径均以标准化的坐标翻转序列表示，可直接用于算法验证或作为进一步搜索的初始种子。研究者可基于这些记录设计新的启发式搜索策略，或利用其进行超立方体图结构性质的深入分析。数据集的计算机可验证格式确保了其在科研中的复现性和可扩展性。

背景与挑战

背景概述

蛇形路径问题（Snake-in-the-Box）由Kautz于1958年提出，源于单元距离错误检测编码的研究，旨在寻找超立方体图Qn中最长的诱导无弦路径，其最大长度a(n)仅在n≤8时精确已知。该数据集由加州理工学院等机构的研究人员于2026年构建，核心研究问题是通过计算搜索提升n≥9维度上a(n)的下界。数据集记录了从9维到13维中所有超越此前纪录的蛇形路径，其中在9维发现了131条长度为191的互不等价路径，显著推动了该组合优化问题的发展。该工作不仅深化了对超立方体图拓扑结构的理解，也为编码理论、并行计算互连网络设计提供了重要基准。

当前挑战

蛇形路径问题的核心挑战在于搜索空间的指数爆炸：超立方体Qn的顶点数随维度n指数增长，而诱导路径约束（禁止非相邻顶点相连）使暴力枚举在n≥9时完全不可行。构建过程中，研究人员需在无理论最优解的情况下设计启发式策略，需平衡搜索深度与广泛性——例如利用遗传算法、蒙特卡洛树搜索及排列构造等方法，但往往陷入局部最优或产生大量伪候选，需对称性约简与大规模并行计算（如云TPU）才能验证新记录。此外，线圈与对称线圈的构建要求更高，因循环结构需额外满足全局一致性约束，进一步加剧了计算复杂性。

常用场景

经典使用场景

在超立方体图的理论与计算研究中，Snake-in-the-Box 数据集被广泛用于探索最长无弦路径（snake）的构造与下界改进。该数据集提供了从9维到13维超立方体中优于此前已知结果的新纪录蛇形路径，为验证超立方体诱导路径的极值性质提供了可靠基准。研究者常利用该数据集进行枚举计数与对称性分析，例如在9维中发现131条不等价且长度达191的蛇形路径，从而深入理解高维超立方体中的组合结构。该数据集的经典使用场景集中在利用遍历搜索或启发式算法验证理论下界，以及作为评估新算法性能的测试平台。

衍生相关工作

该数据集的出现引发了多项衍生性研究工作。基于数据集中新记录路径的统计特征，研究者进一步开发了针对超立方体图结构的新型蒙特卡洛树搜索算法，以求解更高维度中的路径极值。同时，数据集中的131条9维等价类蛇形路径被用于训练图神经网络模型，探索诱导路径的几何对称性规律。在组合优化领域，数据集的公开促使了针对对称线圈问题的进化算法改进，并在12维超立方体中验证了新的构造策略。这些工作不仅延续了关于超立方体基础性质的理论讨论，也促进了计算数学与人工智能方法的交叉融合。

数据集最近研究