近日，Claude独立攻克了一项图论猜想，其成果被正式记录于一篇数学研究论文中。这一事件引发了算法领域泰斗、《计算机程序设计艺术》作者高德纳（Donald Knuth）的深度关注与思考，标志着生成式AI在自动推理与创造性问题求解方面达到了新的里程碑。
高德纳在斯坦福大学官网亲自发布了一篇题为《Claude’s Cycles》的原始论文，开篇即以“Shock! Shock!”表达了他的震撼。
论文地址： https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
高德纳是计算机科学领域的标志性人物，他是图灵奖得主，著有被誉为“算法圣经”的《计算机程序设计艺术》（TAOCP），也是排版系统TeX的发明者。
《计算机程序设计艺术》是高德纳毕生的事业，旨在系统性地整理和夯实计算机算法的数学与历史基础。一位深耕算法领域五十余载的学者开始严肃审视AI的数学能力，这本身即是一个强烈的信号：AI正在触及人类最核心的智力疆域。
难倒算法祖师爷的问题，被Claude Opus 4.6攻克
在论文中，高德纳叙述道：“我昨天得知，一个我花费数周时间研究的未解问题，刚刚被Claude Opus 4.6——Anthropic公司于三周前发布的混合推理模型——解决了！”
他进一步表示：“看来我迟早得重新审视自己对‘生成式AI’的看法了。得知自己的猜想不仅有一个漂亮的解法，同时还能见证自动推理与创造性问题求解方面的这一戏剧性进步，真是令人欣喜不已。”
事件的起因源于高德纳为其持续撰写的《计算机程序设计艺术》系列新章节准备的一道题目。该题涉及有向图中的哈密顿循环，他与朋友们证明了其特殊情形，但在试图推广至一般情况时遇到了阻碍。
最终，Claude Opus 4.6为这个问题找到了一个优雅的构造性解法。随后，高德纳本人为此构造提供了严格的数学证明。这篇论文也因此成为一个标志：生成式AI的贡献首次被正式、严谨地记录在一项数学研究之中。
难题：三维环面图中的三环分解
这道题是一个看似简单实则复杂的图论问题。
设想一个三维的环面网格空间，即一个 m × m × m 的立方体，其中每个顶点由坐标 (i, j, k) 表示（每个坐标取值范围为0到m-1）。因此，图中共有 m³ 个顶点。
从每个顶点出发，允许沿三个坐标轴正方向移动（i+1, j+1, k+1），当坐标值达到m时则循环回0。这样，每个顶点都有三条出边，整个图共有 3m³ 条有向边。
问题的目标是：找到三个哈密顿循环（即访问每个顶点恰好一次并回到起点的回路），使得这三条回路恰好覆盖图中所有的边，且每条边仅属于其中一个循环。高德纳原计划将这个问题及其（当时未知的）解法写入他的著作。
该问题的难点在于其巨大的搜索空间。每个顶点需在三出边中选择其一以构成回路，因此可能的组合数高达 3^(m³)，暴力搜索几乎不可行，必须找到一种规律性的构造方法。
此前，高德纳已解决了m=3的情况，其合作者Filip Stappers通过计算实验找到了4 ≤ m ≤ 16的解，这强烈暗示了通用解的存在性。
那么，能否找到一个适用于所有（或一类）m的通用公式？
研究过程：Claude的31次探索
Filip将问题交给了Claude Opus 4.6，并要求其严格记录每次程序运行的探索进展。有趣的是，Claude的求解过程并非一蹴而就，而是经历了31次系统性的尝试，其模式类似于人类研究者的工作流程。
- 初步尝试：首先尝试使用简单的线性函数来决定每个顶点的移动方向，但很快发现此路不通。
- 暴力搜索：转向深度优先搜索（DFS），但因状态空间爆炸而效率低下。
- 降维分析：转而分析二维类似问题，发现了“蛇形路径”的构造，并试图将其推广至三维。
- 持续试错：在随后的十几次探索中，Claude不断尝试各种路径构造与分解方法，但均未获得通用解。
关键突破：纤维分解（Fiber Decomposition）
在第15次探索中，Claude提出了一个核心概念：纤维分解。
它观察到，如果定义 s = (i + j + k) mod m，那么所有的有向边都会将顶点从s层移动到(s+1) mod m层。这意味着整个三维图可以按照s值“切片”，每一层（固定s）的顶点构成一个二维网格结构。这一洞见极大地简化了问题。
此后，Claude尝试了随机搜索、模拟退火和回溯搜索，虽然能为特定m找到解，但仍未提炼出通用规则。它由此得出结论：需要寻找一个纯数学的构造规则。
最终成功：第31次探索找到构造规则
在第31次探索中，Claude最终提出了一套简洁的规则。规则的核心依然是基于 s = (i + j + k) mod m。
具体规则根据s的值、i和j的奇偶性或取值，来决定在哪个坐标方向上进行“跃迁”（bump）。例如：
* 当 s = 0 时，移动方向由 j 的值决定。
* 当 0 < s < m-1 时，移动方向由 i 的值决定。
* 当 s = m-1 时，则应用另一套规则。
Claude通过编程验证，对于m=3, 5, 7, 9, 11等奇数，由此规则生成的路径均能成功分解为三个哈密顿循环。
当然，Claude提供的是构造方法。高德纳随后完成了严格的数学证明，证实该构造确实能生成覆盖所有顶点的回路，并且三条回路互不重叠地覆盖了所有边。
此外，高德纳的进一步研究表明，Claude发现的只是众多可能解中的一个。实际上存在760种满足类似结构的分解方法。同时，该构造目前仅适用于m为奇数的情况。对于偶数m，问题仍未完全解决（例如m=2已被证明无解）。
意义：超越解题的研究范式探索
此事件最深远的意义，或许不在于解决了一个具体的猜想，而在于AI解决问题所展现出的研究范式。
在整个过程中，Claude并非进行盲目的猜测，而是系统地进行了问题重述、编程实验、模式识别与规律提炼。这一过程与人类数学研究者的工作方式高度相似。
数十年来，数学证明一直被视为AI难以涉足的圣殿。而这篇论文表明，AI已开始能够参与实质性的数学探索。未来，一种新的研究协作模式可能成为常态：人类提出关键问题与方向，AI进行探索与发现潜在结构，人类最终完成严格证明与理论升华。
《Claude‘s Cycles》这篇论文，或许将被视为这一新时代的起点。
高德纳撰写《计算机程序设计艺术》已逾半个世纪，这套巨著记录了人类算法思想的演进历程。如今，AI的贡献被正式写入这位算法宗师的论文之中。这，可能仅仅是一个开端。
高德纳：不止于计算机科学教父
高德纳（Donald Ervin Knuth），1938年1月10日出生于美国密尔沃基，是享誉世界的计算机科学家、斯坦福大学名誉教授。
他被公认为算法分析领域的奠基人，是现代计算机科学的先驱之一，在多个理论计算机科学分支做出了基石性的贡献。因其在算法分析和程序设计语言设计方面的开创性工作，他于1974年荣获图灵奖（计算机科学领域的最高荣誉），时年36岁，至今仍是该奖项最年轻的获奖者之一。
颁奖词特别提到了他的系列巨著《计算机程序设计艺术》（The Art of Computer Programming, TAOCP）对计算机编程艺术的杰出贡献。1999年，该书被《美国科学家》期刊评为20世纪最佳12部学术专著之一，与爱因斯坦的“相对论”等重要著作并列。
该丛书第一卷于1968年出版，至1976年时销量已超过一百万册。比尔·盖茨曾评价道：“如果你自认为是一个优秀的程序员，就去读《计算机程序设计艺术》吧。如果你读完了，请务必把简历发给我。”
为了追求更完美的书籍印刷效果，高德纳于1977年决定开发一套排版系统。历时八年，他推出了TeX系统，该系统现已成为全球学术界，尤其是数学、物理等需要处理复杂公式的领域，排版的不二之选。
截至2025年，TAOCP已出版第1、2、3、4A和4B卷，未来预计还将出版更多卷册。其中，第1至5卷旨在阐述顺序计算机程序设计的核心内容，而第6卷和第7卷则专注于更专门但仍至关重要的主题。
值得一提的是，他的中文名“高德纳”是1977年访华前，由好友姚期智（清华姚班创始人）的夫人姚储枫所起。
高德纳为人风趣幽默。例如，他设立了“找错奖励”：任何在其著作中发现错误的人，都能获得2.56美元，因为“256美分刚好是十六进制的一美元”。
文学编程的先声
对高德纳而言，编程不仅是技术和科学，更是一门艺术。
他认为，日常生活如同编程，如果你热爱一件事，就能将美感融入其中。开发TeX系统的经历，让他提出了“文学编程”的概念。这种范式不同于传统按计算机逻辑顺序编写程序的方式，而是允许程序员按照其思维的内在逻辑和流程来组织代码。
高德纳曾表示：“文学编程确实是由TeX项目派生出来的最重要的东西。”他后来回忆道：“它不仅让我前所未有地更快编写和维护可靠性更高的程序，而且成为我自20世纪80年代以来的最大快乐之源……没有文学编程，我的整个事业规划就会轰然倒塌。它是你更上一层楼的必要工具。”
从神童到计算机科学巨匠
高德纳自幼便展现出非凡的才智。8岁时，他为了参加一项用指定字母拼写单词的比赛，假装胃痛在家待了两周，凭借一部大词典列出了4500个单词，远超裁判掌握的2000个，最终为班级赢得冠军，自己也获得奖励。
他在凯斯理工学院攻读数学时表现极为出色，毕业时被同时授予学士和硕士学位。1963年，他获得加州理工学院数学博士学位，随后留校任教。1968年，他加入斯坦福大学，历任教授及冠名教授，直至1993年荣休，成为“计算机程序设计艺术”荣休教授。
据统计，高德纳一生荣获超过100项荣誉。
参考资料：
https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
https://valeman.substack.com/p/donald-knuths-30-year-problem-solved
关注“鲸栖”小程序，掌握最新AI资讯
本文来自网络搜集，不代表鲸林向海立场，如有侵权，联系删除。转载请注明出处：https://www.itsolotime.com/archives/24171
