🔢 mathematics

Generation of maximal snake polyominoes using a deep neural network

本文提出了一种名为“结构化像素空间扩散”（SPS Diffusion）的深度学习模型，通过数据驱动方式学习最大蛇形多联骨牌的生成规律，成功将生成能力从网格扩展至 28x28 规模，尽管存在分支、循环等错误，但证明了神经网络在理解和生成复杂组合对象方面的潜力。

原作者： Benjamin Gauthier, Alain Goupil, Fadel Toure

发布于 2026-03-16

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Benjamin Gauthier, Alain Goupil, Fadel Toure

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个非常有趣的故事：研究人员试图用**人工智能（AI）**来解决一个困扰数学界几十年的难题——如何在巨大的网格中画出最长的“贪吃蛇”（数学上称为“蛇形多联骨牌”）。

为了让你轻松理解，我们可以把这项研究想象成教一个 AI 玩“贪吃蛇”游戏，但不是教它怎么玩游戏，而是教它怎么“画”出完美的蛇。

以下是用通俗语言和比喻对这篇论文的解读：

1. 背景：为什么这个问题很难？

想象一下，你有一个巨大的棋盘（比如 50x50 的格子）。你的任务是画一条蛇，这条蛇必须：

不能交叉（不能自己咬到自己）。
不能分叉（不能长出两个头或两个尾巴）。
要尽可能长，填满棋盘的大部分空间。

传统的做法（笨办法）：
以前的数学家像是一个不知疲倦的工兵。他们试图用电脑把棋盘上所有可能的画法都试一遍。

问题： 棋盘稍微大一点，可能的画法数量就会像滚雪球一样爆炸式增长。
结果： 即使是最快的超级计算机，算到 20x20 的棋盘就会累死，更别提更大的了。这就像试图数清大海里所有的沙粒，根本数不完。

2. 新方案：AI 的“直觉”

研究人员想：“既然数不过来，不如我们教 AI 去猜。”
他们开发了一种叫 SPS Diffusion（结构化像素扩散） 的模型。

这个模型是怎么工作的？（核心比喻：去噪绘画）
想象你在一张画满杂乱的雪花点（噪音）的纸上画画。

开始： 给 AI 一张全是随机杂点的白纸（就像电视没信号时的雪花屏）。
过程： AI 看着这些杂点，思考：“如果我要画一条蛇，这里应该去掉多少杂点，那里应该保留多少？”
迭代： 它一遍遍地擦除杂点，慢慢让蛇的轮廓显现出来。
训练： 在训练阶段，研究人员给 AI 看很多已经画好的完美蛇（作为标准答案），然后故意把蛇弄脏（加噪音），让 AI 练习如何把脏东西擦掉，还原出那条完美的蛇。

关键点： AI 并没有被明确告诉“蛇不能分叉”或“蛇不能打结”这种死板的规则。它是通过看大量的例子，自己“悟”出了蛇的结构规律。

3. 实验结果：AI 表现如何？

研究人员让 AI 在两种情况下画画：

情况 A：它见过的棋盘（比如 10x10）
- 结果： 完美！AI 画出的蛇几乎和训练数据一样好，非常流畅。
情况 B：它没见过的超大棋盘（比如 28x28 甚至 50x50）
- 结果： 令人惊讶！虽然它没练过这么大的棋盘，但它举一反三了。它画出了很长的蛇，长度甚至超过了以前人类手工计算出的最佳记录。
- 比喻： 就像你教一个孩子画 5 厘米的蛇，结果他拿起笔在 50 厘米的纸上也能画出一条很棒的蛇，虽然有点歪歪扭扭，但大体结构是对的。

4. 存在的问题：AI 也会“犯傻”

虽然 AI 很聪明，但它不是神，它也会犯错。

分叉（Branching）： 蛇长出了两个头或两个尾巴（就像树杈一样）。
打结（Cycles）： 蛇自己咬住了尾巴，形成了一个圈，没有头也没有尾。
森林（Forests）： 画出来的不是一条蛇，而是一群互不相连的小蛇。

比喻： 这就像让 AI 画人。它通常能画出人，但偶尔会画出“三只手”或者“没有腿”的人。在数学上，这些就是“无效”的蛇。而且，棋盘越大，AI 犯错的可能性就越高。在 29x29 的棋盘上，它目前还画不出完美的蛇，只能画出一些“蛇的森林”。

5. 这项研究的意义是什么？

这篇论文不仅仅是在“画蛇”，它揭示了更深层的道理：

AI 能理解复杂的数学结构： 即使没有把数学公式硬塞给 AI，AI 也能通过观察数据，学会复杂的组合规则（比如蛇不能交叉）。
打破计算瓶颈： 对于传统计算机算不出来的超大网格，AI 提供了一种新的“猜测”工具。虽然它不能保证 100% 正确，但它能给出极好的候选答案，帮助数学家发现新的规律。
未来的方向： 现在的 AI 就像个天才但有点粗心的画家。未来的工作就是教它更细心，减少“三只手”和“打结”的情况，让它能画出更大、更完美的蛇。

总结

这就好比数学家们以前只能靠数手指来数数，数到 100 就晕了。现在，他们造了一个超级计算器（AI），虽然这个计算器偶尔会按错键，但它能瞬间算出 10000 以内的数，并且给出了很多以前没人知道的答案。

这篇论文证明了：人工智能不仅是用来聊天或画图的，它还能成为探索深奥数学难题的强力助手。

论文技术总结：基于深度神经网络的极大蛇形多联骨牌生成

1. 研究背景与问题定义

问题背景：
极大蛇形多联骨牌（Maximal Snake Polyominoes）是指在给定矩形网格中，由度数为 2 的单元格（蛇身）和两个度数为 1 的单元格（蛇头/蛇尾）组成的连通路径，且无法再延伸。寻找任意矩形中极大蛇的长度是一个未解决的组合数学难题。

现有挑战：

计算复杂度：传统的求解方法依赖于暴力枚举（Brute-force），即枚举所有可能的蛇形结构并筛选出极大者。由于蛇形多联骨牌的数量随网格大小呈指数级增长（增长常数约为 2.6），这种方法在较大网格（如超过 20x20）中计算上不可行。
数据局限性：现有的可枚举蛇形数据主要集中在小网格中，导致难以研究大网格下的宏观模式和结构特征。
理论局限：虽然存在如 2/3 定理等理论上限，但它们无法直接帮助生成具体的极大蛇形结构。

研究目标：
利用深度神经网络（DNN）的数据驱动能力，绕过指数级复杂度，从训练数据中学习蛇形的结构约束（如连通性、无环、度数为 2 等），从而生成大网格下的极大蛇形候选者，辅助理论猜想。

2. 方法论：结构化像素空间扩散模型 (SPS Diffusion)

作者提出了一种名为**结构化像素空间扩散（Structured Pixel Space Diffusion, SPS Diffusion）**的生成模型，这是一种去噪扩散概率模型（DDPM）的变体。

2.1 核心架构设计

与标准的 Stable Diffusion 相比，SPS Diffusion 针对二值化、小尺寸的蛇形网格进行了简化：

输入/输出：输入为纯噪声图像，输出为去噪后的蛇形矩阵（0 代表空，1 代表蛇身）。
模型结构：仅包含一个Mini U-Net。
- 去除了 CLIP 编码器：因为生成过程不需要文本提示（Prompt）。
- 去除了 VAE（变分自编码器）：蛇形网格通常小于 64x64，直接在像素空间操作即可，无需压缩到潜在空间。
- 下采样层级限制：标准 Stable Diffusion 通常有 5-6 级下采样，而 SPS Diffusion 仅保留3 级，以防止在小尺寸网格中过度下采样导致结构信息丢失。
注意力机制：在 U-Net 的每个层级中集成了自注意力机制（Self-Attention），并使用了2D 旋转位置编码（RoPE-2D），以捕捉网格中的长距离依赖和全局结构关系。

2.2 训练与生成流程

训练数据：使用已知的小网格（最大 50x10 和 14x14）中的极大蛇形真值（Ground Truth）。
前向扩散（训练）：向已知蛇形 $x_0$ 添加高斯噪声得到 $x_t$ 。
反向扩散（生成）：模型预测噪声 $\epsilon_\theta(x_t, t)$ ，通过迭代去噪从纯噪声 $x_T$ 恢复出蛇形 $x_0$ 。
损失函数：使用均方误差（MSE）。实验表明，MSE 在生成蛇状结构方面表现最佳，而其他损失函数容易产生分支、循环等错误结构。

3. 关键贡献

隐式约束学习：证明了深度神经网络可以在不显式编码图论约束（如“度数为 2"、“无环”）的情况下，仅通过数据训练学习并生成符合这些复杂组合约束的结构。
SPS Diffusion 模型：提出了一种针对离散组合对象优化的轻量级扩散模型架构，去除了不必要的模块（VAE, CLIP），专注于像素空间的直接生成。
泛化能力验证：展示了模型具有显著的**零样本泛化（Zero-shot Generalization）**能力，即在小网格上训练，却能在未见过的更大网格中生成合理的蛇形结构。

4. 实验结果

训练集表现：在训练过的网格尺寸（如 10x50, 13x13）上，模型能轻松生成完美的极大蛇形。
泛化表现：
- 正方形网格：模型成功生成了高达 28x28 的蛇形结构（训练数据中最大正方形仅为 14x14）。
- 矩形网格：在 10x60 等长条形网格中也能生成蛇形。
- 突破现有界限：在 17x17 网格上，生成的蛇形长度超过了当前计算极限下的已知下界（部分配置下超出 1 个单元格）。
局限性：
- 错误类型：随着网格增大，错误率上升。常见错误包括：分支（度数为 3）、闭环（无头尾）、多连通分量（森林状结构）。
- 尺寸限制：在 29x29 网格上，经过 25,000 次尝试仍未生成有效蛇形，仅生成蛇的森林或多联骨牌森林。
- 位置编码失效：在超大网格中，基于小网格训练的 RoPE-2D 位置编码可能不再有效，且固定的 3 级下采样可能无法捕捉大网格的全局上下文。

5. 意义与展望

方法论意义：该研究证明了深度扩散模型能够理解并生成复杂的离散组合对象，为研究那些传统枚举算法无法触及的大规模组合结构提供了新的数值工具。
科学价值：生成的候选蛇形结构（即使不完美）包含的宏观模式（如“楼梯”结构、死细胞三角形、边界高密度等）可以为数学家提出关于极大蛇长度和枚举公式的新猜想提供依据。
未来方向：
- 模型优化：改进架构（如增加下采样层级以适应更大网格）或调整位置编码。
- 迭代训练：利用模型生成的候选数据（经筛选后）重新训练模型，形成迭代增强循环。
- 损失函数改进：设计更复杂的损失函数以惩罚分支和循环等非法结构。

总结：这篇论文展示了人工智能在解决经典组合数学难题中的潜力，通过 SPS Diffusion 模型，成功将极大蛇形生成的边界从传统算法的极限推向了更大的网格尺寸，尽管目前仍存在生成错误率高的问题，但其作为辅助发现工具的价值已得到初步验证。