剛剛，Claude獨立攻克圖論猜想，僅用31步！算法祖師爺高德納震驚發文

新智元報道

編輯：Aeneas KingHZ

【新智元導讀】就在剛剛，Claude獨立攻克了圖論猜想，寫《計算機程序設計藝術》的計算機泰斗高德納徹底震驚了！這一次，AI在自動推理和解決創造性問題上，又達到了全新的里程碑。

震驚！震驚！

就在剛剛，Claude僅用31步，就獨立攻克了未解的圖論猜想難題。

寫《計算機程序設計藝術》的算法祖師爺高德納驚呼：「我不得不重新評估生成式AI在數學研究中的作用」。

在斯坦福的官網上，他本人發布了一篇原始論文。開頭兩個字，就是「Shock！Shock！」

論文地址：https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf

高德納是誰？

他是寫出了《計算機程序設計藝術》（TAOCP）、發明TeX的圖靈獎得主，算法界祖師爺。

《計算機程序設計藝術》是高德納一生中最重要的事業，他寫這本書的目的是「組織和總結所知道的計算機方法的相關知識，并打下堅實的數學、歷史基礎。

一個寫了50年算法書的人，都開始認真看待AI的數學能力，那就說明：AI，正在進入人類最核心的智力領域。

難倒算法祖師爺的問題

被Opus 4.6攻克了

在論文開頭，高德納這樣講述道：

我昨天得知，一個我花了數周時間研究的未解問題，剛剛被Claude Opus 4.6——Anthropic公司在三周前發布的混合推理模型——解決了！

他直言：

看來我遲早得重新審視自己對「GenAI」的看法了。 得知自己的猜想不僅有一個漂亮的解法，同時還能見證自動推理與創造性問題求解方面的這一戲劇性進步，真是令人欣喜不已。

故事是這樣的，《計算機程序設計藝術》這個系列，從上世紀60年代就開始寫，現在已經出了5本。

在88歲的高齡，這位算法祖師爺還在繼續寫這套書。

他在書里準備了一道關于有向哈密頓循環的題，和朋友們證明了這道題的特殊解，想把它推廣到一般情況時，卻解決不了了。

結果，這道題被Claude Opus 4.6解決了。

更嚴謹的說法是，AI找到了一個漂亮的構造方法，而高德納隨后給出了嚴格的數學證明。

這篇論文也因此成為一個標志性事件——生成式AI，第一次被認真記錄在數學研究的故事里。

難倒算法祖師爺的題長啥樣

這道題，是一道看起來簡單，但實際上非常復雜的圖論問題。

先想象一個三維網格空間，比如一個m×m×m的立方體。

其中每個點都可以用(i, j, k)三個坐標表示，每個坐標都在0到m-1之間。所以，整個空間里一共有m3個點。

接下來我們規定，從每個點都可以沿三個方向移動：i增加1，j增加1，k增加1。如果超過m?1，就從0重新開始。 這就形成了一個環形空間。

按照高德納在論文中的正式定義，就是從每個頂點有三條有向邊，分別指向三個方向的「下一個」頂點。

因此，整個圖有m3個頂點，3m3條有向邊。

而哈密頓環，就是一條路徑經過所有頂點，每個頂點恰好一次，最后回到起點。這就是一個經典的圖論問題。

而高德納提出的問題更難：不是找一條路線，而是要找到三條路線，并且滿足每條都是哈密頓環，每條長度都是m3，三條環剛好覆蓋所有邊。

也就是說：每條邊只能屬于其中一條環。

原本，高德納就是準備把這個問題寫進《計算機程序設計藝術》的新章節。

為什么這個問題如此困難？原因就在于，每個點都有三條出邊。如果要組成哈密頓環，就必須選擇其中一條。所以在每個點，都需要做一個選擇。

因此，問題規模達到了3^(m3)個！這幾乎無法通過暴力搜索完成，因此，必須找到某種規律性的構造方法。

此前，高德納已經解決了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只是提出了構造方法，數學上還需要嚴格證明。

隨后，高德納證明，這條路徑確實訪問了所有m2個具有相同i值的頂點，然后依次覆蓋所有i，最終形成長度為m3的完整環。

類似證明也適用于另外兩條環，于是整個問題被解決了。

而且，高德納還通過進一步研究發現，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條八卦：

可以上下滾動的圖片，轉自：https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ

開Vibe Coding之先聲

對高德納而言，編程不僅是技術、科學，還是藝術。

日常生活大概就像編程。如果你熱愛一件事，就能把美感融入其中。

排版系統TeX讓他萌發了「文學編程」的概念——

文學編程范式不同于傳統的由計算機強加的編寫程序的方式和順序，而代之以讓程序員用他們自己思維內在的邏輯和流程所要求的順序開發程序。

對他來說，「文學編程確實是由TeX項目派生出來的最重要的東西」。

后來，高德納回憶道：

它不僅讓我前所未有地更快地寫和維護可靠性更高的程序，而且成為我自20世紀80年代以來的最大的快樂之源——它有時實際上是不可或缺的。

我做的其它一些大程序，比如MMIX元模擬器，用我見過的任何一種其它的方法論是無法寫出來的。其復雜性讓我有限的智能望而卻步。

沒有文學編程，我的整個事業規劃就會轟然倒塌?！膶W編程是你更上一層樓的必要工具。

完全可以說，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