用深度模型生成大矩形中的最长蛇形多格骨牌，突破传统枚举瓶颈。
Generation of Maximal Snake Polyominoes Using a Deep Neural Network
- 用去噪扩散模型从数据中学习蛇形结构，不显式编码规则
- 生成最大可达28×28的蛇形多格骨牌，逼近当前计算极限
- 适合研究复杂组合结构生成的算法与机器学习交叉方向
在大矩形中研究最大蛇形多格骨牌数值困难，因需穷举所有可能路径，相当于暴力搜索。这限制了对大矩形中最大蛇形的研究，且多数可枚举的蛇形集中在小矩形，掩盖了宏观模式。本文探索深度神经网络在数据驱动下生成最大蛇形多格骨牌的潜力，其中最大化和邻接约束未显式编码，而是由模型学习。实验采用一种去噪扩散模型，称为结构化像素空间扩散（SPS Diffusion）。结果表明，该模型能从小矩形泛化至大矩形，生成长度达28×28的有效蛇形，并产生接近当前计算极限的最大蛇形候选。但模型仍存在分支、环路或多个组件等错误。总体而言，扩散模型表现出前景，表明深度神经网络可理解复杂组合对象，对相关研究具有价值。
原文摘要 · Abstract (English)
Maximal snake polyominoes are difficult to study numerically in large rectangles, as computing them requires the complete enumeration of all snakes for a specific rectangle size, which corresponds to a brute force algorithm. This hinders the study of maximal snakes in larger rectangles. Moreover, most enumerable snakes lie in small rectangles, obscuring large-scale patterns. In this paper, we investigate the contribution of a deep neural network to the generation of maximal snake polyominoes from a data-driven training, where the maximality and adjacency constraints are not encoded explicitly, but learned. To this extent, we experiment with a denoising diffusion model, which we referred as Structured Pixel Space Diffusion (SPS Diffusion). We find that SPS Diffusion generalizes from small rectangles to larger ones, generating valid snakes up to 28x28 squares and producing maximal snake candidates on squares close to the current computational limit. The model is, however, prone to errors such as branching, cycles, or multiple snake components. Overall, the diffusion model is promising and suggests that complex combinatorial objects can be understood by deep neural networks, which is useful in their investigation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。