新智元报道
最近，Claude独立破解了一个长期未解的图论难题，震惊了撰写《计算机程序设计艺术》的大师高德纳。
震惊！震惊！
这一次，人工智能在自动推理和解决创造性问题方面取得了重大突破，引起了全球科技界的高度关注。
高德纳对这一成就表示惊叹，并认为生成式AI在数学研究中的作用需重新评估。
斯坦福大学官网上发布了一篇关于此次事件的论文。文章开头便以“震惊！震惊！”二字引人注目，展现了这次突破的重要性。
论文详细分析了Claude如何通过31步独立解决了这道难题的过程，并提出了一个新的构造方法。
高德纳是谁？
高德纳是《计算机程序设计艺术》的作者和TeX系统的发明者，被誉为算法界的奠基人。
写作该书的初衷是为了组织和总结有关计算机方法的知识体系并奠定坚实的数学基础。
即使像高德纳这样长期从事算法研究的人也开始认真看待AI在数学领域的能力，这表明人工智能已经开始深入人类的核心智力活动之中。
难倒算法祖师爷的问题
在论文中，高德纳详细描述了Claude如何解决了他在《计算机程序设计艺术》中的一个问题。
他提到，自己花费数周时间研究的一个难题被名为Claude的生成式AI在短短三周内解决。
这一成就不仅为数学界提供了新的解题思路，同时也标志着人工智能首次正式参与到严肃的学术探索之中。
他直言：
高德纳的问题源于一个关于有向哈密顿循环的难题，这道题原本准备收录进他的新章节中。
他和朋友们证明了这个问题的一个特殊情况后尝试推广到一般情况时遇到了瓶颈。
然而，Claude Opus 4.6却成功解决了这个难题，提出了一个构造方法，并由高德纳进行了严格的数学验证。
这道题涉及的是如何用特定字母组合生成尽可能多的单词问题，是《计算机程序设计艺术》中的一部分内容。
其难度在于需要找出所有可能的排列组合，而不仅仅是简单的逻辑推理。
人工智能通过一系列复杂的算法和模型，成功解决了这个问题，并提出了一个全新的构造方法。
高德纳表示，这次突破不仅是对数学领域的贡献，更重要的是展示了AI在解决问题过程中的独特思维方式。
这种方式与人类研究问题的方法非常接近，未来可能形成一种新的合作模式：人类提出问题，人工智能探索结构，最后由人类完成证明工作。
高德纳本人是一位杰出的计算机科学家和数学家，在算法分析领域做出了开创性的工作。
他因《计算机程序设计艺术》系列丛书而闻名于世，并因此获得图灵奖等众多荣誉。
自1968年以来，这套书已经成为全球程序员必读的经典之一，影响了几代人的编程观念。
高德纳在开发TeX系统时提出的“文学编程”概念更是改变了学术出版界的面貌。
这一理念主张用自然语言描述程序逻辑而非强制性的编程语法规则来进行软件设计。
他个人认为，这种思维方式不仅让他能够更高效地编写和维护复杂的代码库，还为他的工作带来了很多乐趣。
高德纳自小就展现出了非凡的智力，在各种比赛中屡获佳绩。例如，8岁时通过查阅大量字典解决了糖果商举办的益智比赛。
1963年获得加州理工学院数学博士学位后，他先后在多所大学担任教授职位，并获得了众多学术荣誉和奖项。
目前，高德纳已经退休，但仍活跃于科研领域。他的工作不仅推动了计算机科学的发展，也为后来者树立了榜样。
总体而言，Claude解决图论难题的案例表明人工智能已经开始深刻影响数学研究的方式，并展现出广阔的应用前景。
为什么这个问题如此困难？原因就在于，每个点都有三条出边。如果要组成哈密顿环，就必须选择其中一条。所以在每个点，都需要做一个选择。
因此，问题规模达到了3^(m³)个！这几乎无法通过暴力搜索完成，因此，必须找到某种规律性的构造方法。
此前，高德纳已经解决了m=3的情况，他的朋友Filip Stappers又通过实验找到了4≤m≤16的解。
这就说明：答案很可能存在！
那么，能否找到一个通用公式？
多次尝试，Claude在做研究
Filip把问题交给了Claude Opus 4.6，而且制定了一个严格的规则——每次运行程序后，都必须记录探索的进展。
有趣的是，Claude并不是突然灵光一现，而是经历了31次探索，过程非常像一个研究生在做研究。
第一步，它尝试了简单函数，试图用一个函数g(i,j,k) 决定每个点的方向。但是很快它发现，简单线性函数不行。
第二步，它开启了暴力搜索，尝试用深度有限搜索（DFS），但搜索空间太大，效率太低。
第三步，是二维分析。Claude发现，如果只看二维情况，可以找到一种「蛇形路径」。于是，它试图把二维思路推广到三维。
随后，它构造了一种类似Gray code的三维蛇形路径，但删除第一条路径后，剩下的结构很难分解。
接下来的十几次探索，Claude基本都是在不断试错。
关键突破：纤维分解
在第15次探索时，Claude提出了一个关键想法：fiber decomposition（纤维分解）。
它注意到，如果定义s = (i + j + k) mod m，那么所有边都会把顶点从s移动到s+1，这就意味着：整个图可以按s分成层结构。
这样，每一层都像一个二维网格，这就把问题大大简化了。
Claude随后尝试了随机搜索、模拟退火和回溯搜索，这些方法可以找到一些解，但仍然没有发现通用规律。
于是Claude得出结论——需要纯数学结构。
第31次探索，Claude找到规则
在第31次探索时，Claude终于提出了一套简单规则，核心仍然是s = (i + j + k) mod m。
然后根据s、i、j的情况决定是否增加i、增加j、增加k。论文中称之为「bump」规则。
规则大致如下：如果s=0，根据j的值决定移动方向。如果0
这样就生成一条完整的路径。
Claude用程序验证了：对于m=3,5,7,9,11，路径都成立。而且三条路径都是哈密顿环，所有边都被使用。
当然，Claude只是提出了构造方法，数学上还需要严格证明。
随后，高德纳证明，这条路径确实访问了所有m²个具有相同i值的顶点，然后依次覆盖所有i，最终形成长度为m³的完整环。
类似证明也适用于另外两条环，于是整个问题被解决了。
而且，高德纳还通过进一步研究发现，Claude找到的并不是唯一解。
实际上存在760种类似的分解方法，这些解都满足同样的结构。Claude只是找到了其中一个。
另外，Claude只解决了m为奇数的情况。
如果m是偶数，问题仍然没有通用解，甚至m=2已经被证明不可能，所以这个研究仍然没有完全结束。
最大的意义，并不在于解题
如果说这件事真正有意义的地方，不只是解题，而是AI解题的方式。
在这个过程中，Claude并不是猜答案，而是在重新表述问题，写程序，发现规律。这一过程，和人类研究非常接近！
几十年来，人们普遍认为，数学证明是AI最难进入的领域。
但这篇论文说明：AI已经开始参与真正的数学探索，
未来也许会出现新的研究模式——人类提出问题，AI探索结构，人类完成证明。
而这篇「Claude’s Cycles」，也许会被视为一个起点。
高德纳写《计算机程序设计艺术》，已经超过半个世纪了，这套书记录了人类算法思想的发展。
而现在，AI被写进了算法大师鼻祖的论文中。这，可能只是一个开始。
高德纳是谁？不止计算机科学教父
高德纳，原名叫Donald Ervin Knuth，1938年1月10日出生于美国密尔沃基。
Donald Knuth，美国计算机科学家，斯坦福大学名誉教授
高德纳是公认为算法分析「祖师爷」，现代计算机科学的先驱，在数个理论计算机科学的分支做出基石一般的贡献。
凭借对算法分析和程序设计语言设计的重大贡献，他斩获1974年图灵奖（计算机科学领域的「诺贝尔奖」）。
当时，他只有36岁，这个历史记录还没有其他得主打破。
颁奖词中特意强调：他所著的系列丛书《计算机程序设计艺术》（The Art of Computer Programming，TAOCP）为计算机编程艺术做出的杰出贡献。
1999年底，这本书被《美国科学家》（American Scientist）期刊列为20世纪最佳12部学术专著之一，爱因斯坦的「相对论」、 罗素和怀海德的《数学原理》等科学史上的重要著作并列必读经典。
1968年出版第一卷第一版，至1976年，已卖出超过一百万册。
比尔盖茨曾评价这套书：
如果你真自认为自己是一个好程序员，去读《计算机程序设计艺术》吧。 如果你读完了这套书，你一定要把简历发给我。
1977年，他为了让这本书的印刷更精美，决定开发排版系统。八年后，他带着TeX回归。
TeX是全球学术排版的不二之选，尤其是处理复杂数学符号
截至2025 年，已出版的卷册包括第1、2、3、4A和4B卷，未来预计还将发布更多卷册。
第1至5卷旨在阐述适用于顺序机器的计算机程序设计核心内容；第6卷和第7卷的主题则更为专门，但仍具重要意义。
顺便一提，他的中文名高德纳，是在1977年访问中国前，他的朋友清华姚班之父姚期智的夫人姚储枫给他起了这个名字。
高德纳为人风趣。比如，他会奖励每一个找出他的著作中任何错误的人，就能得到2.56美元，因为「256美分刚好是十六进制的一美元」（256 pennies is one hexadecimal dollar）。
水木有帖子汇总整理关于Knuth的18条八卦：
可以上下滚动的图片，
开Vibe Coding之先声
对高德纳而言，编程不仅是技术、科学，还是艺术。
日常生活大概就像编程。如果你热爱一件事，就能把美感融入其中。
排版系统TeX让他萌发了「文学编程」的概念——
文学编程范式不同于传统的由计算机强加的编写程序的方式和顺序，而代之以让程序员用他们自己思维内在的逻辑和流程所要求的顺序开发程序。
对他来说，「文学编程确实是由TeX项目派生出来的最重要的东西」。
后来，高德纳回忆道：
它不仅让我前所未有地更快地写和维护可靠性更高的程序，而且成为我自20世纪80年代以来的最大的快乐之源——它有时实际上是不可或缺的。
我做的其它一些大程序，比如MMIX元模拟器，用我见过的任何一种其它的方法论是无法写出来的。其复杂性让我有限的智能望而却步。
没有文学编程，我的整个事业规划就会轰然倒塌。……文学编程是你更上一层楼的必要工具。
完全可以说，Vibe Coding和文学编程一脉相承，不知道老爷子自己有没有体验过真正的Vibe Coding。
从神童到计算机科学全才
自小，高德纳就「聪敏绝顶」——
他8岁时，当时某糖果商举办了一项小学生益智趣味比赛，要求用「Ziegler’s Giant Bar」（分别为糖果厂名和出产的棒棒糖名）里的字母写出尽可能多的单词。
小高德纳假装胃疼宅家两周，依靠一部大字典列出了4500个单词，而裁判才掌握的2000个单词！
这不仅使所在班级夺冠（奖品为一台电视机和每人一块Giant Bar），他个人人也赢得一付雪撬。
他在凯斯理工学院的数学研究表现极为出色，以至于在他完成本科学业时，学院授予了他数学硕士学位。
1963年，他获得加州理工学院数学博士学位。
1963-1968年，他先后任加州理工学院助理教授、副教授。
1968-1992年，任斯坦福大学一系列正教授及冠名教授职位。
1993年至今，任斯坦福大学「计算机程序设计艺术」荣休教授（Emeritus）。
据统计，高德纳一生荣获100多项大小荣誉，包括：
参考资料：
https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
https://valeman.substack.com/p/donald-knuths-30-year-problem-solved
https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ
https://mp.weixin.qq.com/s/PkrJnuvtrL0OCJXzRPCxxA
https://mp.weixin.qq.com/s/XIcafYS9PbNgE2cMYHfQ5w