arXiv：cs.LG（机器学习，全量分类）· Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov·· 14 小时前AI 评分32
通过 Snakepit Surgery 与学习式构造刷新 Snake-in-the-Box 记录
New Snake-in-the-Box Records via Snakepit Surgery and Learned Construction
AI 导读
研究者找到 n=9 维超立方体 Q_n 中长度为 191 的蛇形路径，打破保持 14 年的 190 旧纪录，并在 10-13 维给出新下界。方法上提出 snakepits（不相交蛇形路径集合）扩展搜索空间，并给出新基准 Snakepit-in-the-Box；同时提出搜索监督的学习式构造算法 Beam Anchor，在 9 维找到 100 条不等价的长度 190 蛇形路径。
正文
Abstract:The snake-in-the-box problem asks for a longest induced path in the hypercube graph $Q_n$. We find a length-191 snake in dimension $n=9$, the lowest dimension where the maximum is unknown, improving the previous record of 190 that had stood for 14 years. We also establish new lower bounds in dimensions 10-13. To find these records, we introduce snakepits, collections of disjoint snakes, to expand the search space and open new routes between snakes. This motivates our new Snakepit-in-the-Box benchmark, which seeks maximal edge counts when allowing multiple components. Finally, we introduce Beam Anchor, a search-supervised learned constructor algorithm that finds 100 inequivalent length-190 snakes in dimension 9.
| Comments: | Updated to include detailed information about methods. 23 pages, 4 figures |
| Subjects: | Discrete Mathematics (cs.DM); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Combinatorics (math.CO) |
| Cite as: | arXiv:2607.15270 [cs.DM] |
| (or arXiv:2607.15270v3 [cs.DM] for this version) | |
| https://doi.org/10.48550/arXiv.2607.15270 arXiv-issued DOI via DataCite |
Submission history
From: Lucas Fagan [view email]
[v1]
Thu, 16 Jul 2026 17:57:52 UTC (7 KB)
[v2]
Mon, 20 Jul 2026 21:53:42 UTC (7 KB)
[v3]
Wed, 30 Sep 2026 14:53:18 UTC (349 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org