🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

本文介绍了CayleyPy项目，该项目将强化学习与扩散距离方法相结合，以高效求解大规模凯莱图上的路径寻找问题，成功超越了GAP等经典工具，为关于对称群直径的OEIS-A186783猜想提供了有力证据，确立了新的理论界限，并通过Kaggle竞赛邀请社区参与。

原作者： A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

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

以下是论文《CayleyPy RL：凯莱图上的路径查找与强化学习》的通俗解释，辅以富有创意的类比。

全景图：在镜子迷宫中寻找最短归途

想象你身处一个巨大且无限的迷宫。但这并非由墙壁构成的普通迷宫，而是一个由规则构建的迷宫。每当你迈出一步，你都在遵循一条特定的规则，从而改变你的位置。在数学中，这被称为凯莱图（Cayley graph）。

本文的目标是解决一种特定类型的迷宫：LRX 迷宫。这个迷宫是基于洗牌规则（或数字的排列）构建的。

规则 L：将所有元素向左移动一个位置。
规则 R：将所有元素向右移动一个位置。
规则 X：交换前两个元素。

挑战在于：如果你从一副乱序的扑克牌开始，需要什么样的最短左移、右移和交换序列，才能将其恢复为完美顺序？

问题：迷宫对人类（以及旧式计算机）来说太大了

对于一副小牌，人类或标准计算机程序（如著名的数学软件GAP）可以找出解决方案。但随着牌的数量（ $n$ ）增加，可能的排列组合呈爆炸式增长。

当 $n=20$ 时，迷宫已极其庞大。
当 $n=100$ 时，迷宫之大，其路径数量甚至超过了宇宙中的原子总数。

旧式计算机程序会陷入困境。它们试图绘制每一条路径，耗尽内存后被迫放弃。作者们想看看**人工智能（AI）**是否能像一位聪明的探险家那样，在不绘制每一寸路径的情况下，找到穿越这些巨大迷宫的方法。

解决方案：训练 AI“猜测”路径

作者们构建了一个名为CayleyPy RL的系统。你可以将其想象为训练一个机器人在迷宫中导航。他们使用了一种称为**强化学习（RL）**的方法。

以下是他们训练机器人的过程，使用了一个简单的类比：

1. “热身”阶段（扩散距离）
想象你在玻璃杯的水中滴入一滴墨水。墨水会随机扩散。如果你想知道某个特定点距离中心有多远，你可以观察墨水到达该点所需的时间。

AI 首先通过观察数百万次“随机游走”（就像墨水扩散一样）来学习。它并不知道最短路径，但它学会了一种对距离的“感觉”。它知道：“如果我在这里，通常需要大约 50 步随机移动才能回家。”
这为 AI 提供了一张粗略的地图，但并不完美。

2. “智能训练”阶段（强化学习）
接下来，他们教导 AI 变得更聪明。不再仅仅基于随机游走进行猜测，他们使用了一种称为**深度 Q 学习（Deep Q-Learning）**的技术。

想象 AI 正在玩一个游戏，每走一步都会受到“惩罚”。它希望以尽可能少的惩罚到达终点。
AI 尝试不同的移动，观察哪些移动让它更接近目标，并调整其“大脑”（神经网络）以做出更好的猜测。
创新点：他们将“墨水扩散”的直觉与“游戏博弈”的逻辑相结合。这帮助 AI 避免了陷入通常会让简单算法受困的死胡同（局部极小值）。

3. “束搜索”阶段（探险家团队）
这是最关键的部分。想象你派出一名探险家进入迷宫。如果他走错了路，你就输了。

相反，作者们派出了一个团队（即“束”）的探险家。
在每个岔路口，团队会分裂。他们保留前 10,000 条最有希望的路径，并丢弃糟糕的路径。
通过维持一个庞大的团队（在某些情况下包含数百万条路径），AI 确保了即使大多数探险家迷路了，至少有一人能发现完美的最短路径。

“魔法技巧”（X 技巧）

作者们发现了一个有趣的小捷径。在他们的代码中，他们添加了一行逻辑：

如果前两张牌已经处于正确顺序，就不要交换它们。

这对人类来说显而易见，但对计算机而言，这却是一个改变游戏规则的技巧。这个被称为"X 技巧"的微小规则，使得他们的 AI 能够解决包含100 张牌（ $n=100$ ）的迷宫。

没有这个技巧：AI 只能处理约 40 张牌。
有了这个技巧：它能处理 100 多张牌，击败了旧式计算机软件（GAP），后者在约 20 张牌时就会崩溃。

他们证明了什么？（数学部分）

除了构建一个快速的求解器，他们还利用 AI 对这些迷宫的数学特性进行了发现：

“上帝之数”猜想：数学界有一个著名的猜想，即 $n$ 张牌最难洗乱的顺序恰好需要 $n(n-1)/2$ 步移动。AI 对巨大的数字进行了测试，从未发现任何比这更难的洗牌方式。这有力地支持了该公式是绝对上限的观点。
“最长”洗牌：他们确定了可能存在的单一最混乱的洗牌状态（即“最长元素”），并证明了如何将其精确分解为移动步骤。
新的界限：他们在数学上证明了迷宫不可能小于某个尺寸，也不可能大于另一个尺寸，从而显著缩小了答案的范围。
迷宫的形状：他们发现，如果统计在距离起点每个距离处存在的洗牌数量，这些数字并不遵循完美的钟形曲线（正态分布）。相反，它们遵循一种奇怪且不对称的形状，称为古姆贝尔分布（Gumbel distribution）。

结果：AI 对阵旧派

该论文将他们的新型 AI 方法与标准计算机代数系统GAP进行了比较：

GAP：最多能解决约 20 张牌的问题。耗时数小时甚至数天。它找到的路径往往很长且效率低下。
CayleyPy RL（AI）：最多能解决约 100 张牌的问题。速度快得多。它找到的路径非常接近理论上的最短路径。

总结

作者们创造了一个智能 AI 系统，将复杂的数学问题视为巨大的迷宫。通过将随机猜测与智能学习相结合，并派遣一支庞大的“虚拟探险家”团队，他们能够穿越那些传统计算机无法处理的巨大迷宫。他们甚至发现了一个微小的“作弊码”（X 技巧），使他们能够解决比之前大 5 倍的问题，同时证明了关于这些迷宫结构的新的数学事实。

他们还将代码和挑战发布在一个名为Kaggle的平台上，邀请其他人尝试打破他们的记录，并帮助解决这些谜题的更难版本。

技术摘要：CayleyPy 强化学习：Cayley 图上的路径搜索与强化学习

问题陈述
本文解决了在极大有限 Cayley 图上进行路径搜索的问题，具体聚焦于由左循环移位（ $L$ ）、右循环移位（ $R$ ）以及前两个元素的换位（ $X$ ）生成的对称群 $S_n$ 。这种配置被称为 LRX Cayley 图，对应于 OEIS 序列 A186783。核心数学挑战是将群元素分解为生成元的最短乘积（即在图中寻找最短路径）。对于通用有限 Cayley 图，该问题是 NP 难的。经典计算机代数系统（如 GAP）依赖于 Schreier-Sims 算法，该算法往往产生指数级长度的路径，且无法处理规模超过 $10^{30}$ （对于 $S_n$ 而言大致对应 $n \approx 20$ ）的群。作者旨在开发高效的人工智能方法，能够处理规模高达 $10^{70}$ （例如 $n \approx 40$ 至 $100$）的图，同时生成近优或最优路径。

方法论
作者提出了一种混合方法论，将强化学习（RL），特别是深度 Q 学习（DQN），与基于扩散距离的预训练策略相结合。

强化学习框架：路径搜索问题被构建为从状态 $s$ 到单位元 $e$ 的最短路径寻找问题。该问题利用贝尔曼方程进行建模，其中距离函数 $d(s)$ 满足 $d(s) = 1 + \min_{t \in N(s)} d(t)$ 。标准的 DQN 被调整以利用神经网络近似该价值函数。
扩散距离预训练：为了解决“稀疏奖励”问题以及标准 DQN 初始化中固有的噪声，作者引入了一个“热身”阶段。他们通过从目标开始的随机游走（扩散）生成训练数据。首先训练一个神经网络来预测这些随机游走中的步数（扩散距离）。
改进的 DQN：预训练网络随后使用改进的 DQN 算法进行微调。关键在于，贝尔曼更新目标根据状态在随机游走生成过程中首次被访问的时间步 $k$ 进行截断。这防止了网络高估距离并稳定了训练过程。
引导束搜索：一旦神经网络被训练用于估计距离，它便作为束搜索算法的启发式函数。束搜索在每一步维持固定数量（ $W$ ）的最有希望的状态，扩展它们的邻居，并根据网络的预测选择前 $W$ 个。这避免了陷入局部极小值，而这是贪婪搜索常见的失败模式。
"X 技巧”：针对 LRX 生成元引入了一种特定的启发式修改。如果排列的前两个元素已经排序，则生成元 $X$ （交换它们）被排除在邻居集合之外。这一行代码的修改极大地减少了搜索空间并改善了混合时间。
非回溯：作者在随机游走生成和束搜索中均纳入了非回溯约束，以减少距离估计的方差并防止在局部极小值中停滞。

主要贡献

算法进步：本文提出了一种将扩散距离预训练与改进的 DQN 相结合的新颖组合。这种方法克服了标准 DQN 的局限性（稀疏奖励、噪声目标），并优于经典方法。
性能基准：所提出的方法成功找到了 $n \approx 44$ 的 LRX Cayley 图的路径（零先验知识），并在利用"X 技巧”时找到了 $n \approx 100$ 的路径。这显著超过了 GAP 的能力（仅限于 $n \approx 20$ ）。对于可比的 $n$ ，AI 方法生成的路径更短且运行速度更快。
数学结果与猜想：
- 直径猜想：作者强烈支持 OEIS-A186783 猜想，即 LRX Cayley 图的直径为 $n(n-1)/2$ 。他们通过 $n \le 15$ 的暴力 BFS 和 $n$ 高达 200 的 AI 分解（通过 Kaggle 竞赛）验证了这一点，未发现比猜想长度更短的分解。
- 最长元素：他们识别出一个独特的“最长元素” $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ ，并提供了长度为 $n(n-1)/2$ 的显式分解。
- 界限：本文通过构造性算法证明了直径的下界为 $n(n-1)/2 - n/2 - 1$ ，上界为 $n(n-1)/2 + 3n$ 。一个经验算法表明更紧的界限为 $n(n-1)/2 + n/2$ 。
- 增长分布：数值实验表明，对于大 $n$ ，LRX 图的增长函数遵循左偏的 Gumbel 分布，这与在邻居换位图中观察到的正态分布形成对比。
- 混合时间：虽然标准随机游走的混合时间在 $O(n^3)$ 和 $O(n^3 \log n)$ 之间，但作者猜想经过"X 技巧”修改的随机游走混合更快，时间复杂度为 $O(n^2)$ 。
- 谱：LRX 图的谱似乎遵循均匀分布。
开源与众包：作者发布了"CayleyPy"项目，并创建了 Kaggle 竞赛以众包解决最长元素的分解和寻找最优算法的问题，促进了 AI 与数学社区之间的协作。

结果

效率：对于 $n=20$ ，GAP 需要超过 41 分钟才能找到长度为 217,944 的路径，而扩散距离方法在不到 4 分钟内找到了长度为 190 的最优路径。
可扩展性：利用"X 技巧”，该系统在单张 GPU 上约 8.5 小时内解决了 $n=100$ （图规模 $\approx 10^{157}$ ）的实例，找到了长度为 16,632 的路径（相比之下，猜想直径为 4,950）。
模型性能：对于此特定任务，简单的模型（如多层感知机 MLP 和梯度提升模型 CatBoost/XGBoost）往往优于复杂的架构（如 Transformer 和 CNN）。
束搜索：找到路径的成功率高度依赖于束宽，随着束大小的增加，成功率呈现超线性提升，这类似于研究社区中“思想交流”的效应。

意义
本文声称，计算实验，特别是利用 AI 的实验，可以显著推动关于 Cayley 图的数学研究。它表明 AI 方法在可扩展性（处理大得多的 $n$ ）和解决方案质量（寻找更短、近优的路径）方面均能“超越”经典计算机代数系统。这项工作 bridging 了理论群论与实用 AI 之间的鸿沟，提供了严格的界限、关于增长和混合时间的新猜想，以及解决以前无法处理的极大状态空间中路径搜索问题的框架。作者将此定位为将 AI 应用于理论科学中其他复杂规划问题的第一步。