圖片來源圖蟲：已授站長之家使用
本文來自於微信公眾號量子位(ID：QbitAI)，作者：曉查，站長之家經授權轉載。
9102 年，人類依然不斷回想起圍棋技藝被AlphaGo所碾壓的恐怖。
卻也有不以為然的聲音：只會下棋的AI，再厲害也還是個運動員啊!
百度說：你們錯了，它還是一位數學家。
百度矽谷AI實驗室的同學們，就在用這個出自谷歌DeepMind的圍棋算法，解決一個比圍棋複雜得多的數學問題。
為了重新訓練這個算法，百度用了 300 張1080Ti和2080Ti顯卡。
他們解決的問題，叫做「圖著色問題」，又叫著色問題，屬於前些天讓中國奧數隊全軍覆沒的圖論。它是最著名的NP-完全問題之一。
簡單來說，就是用儘可能少的顏色，給一張圖的頂點上色，保證相鄰頂點的顏色不重複。
10 個頂點的簡單版是這樣的：
而複雜版……只要頂點足夠多，分分鐘讓人類數學家無從下手，如果有 512 個頂點，這個問題的複雜度會比圍棋高出幾百個數量級。
在這個數學問題上，運動員AlphaGo表現優秀，最高能將一張圖所用的顏色減少10%。
從四色定理談起
就算你對「圖論」、「著色問題」這些詞有點陌生，應該也聽說過「四色定理」。這是第一個由計算輔助證明的數學定理。
四色定理告訴我們，只需 4 種顏色我們就可以讓地圖上所有相鄰國家的顏色互不相同。
這其實就是一個平面上的著色問題，國家可以簡化為頂點，國與國之間的相鄰關係可以簡化為連接頂點之間的線。對於平面圖而言，顏色數k最小等於幾?
歷史上數學家已經手工證明了五色定理(k=5)，但是因為運算量太大，在將顏色數量進一步減少到四種(k=4)時卻遲遲無法解決，最終在 70 年代靠計算機才完成證明。
一般來說，我們可以用貪心算法解決這個問題，其基本思路是：先嘗試用一種顏色給儘可能多的點上色，當上一步完成後，再用第二種儘可能多地給其他點上色，然後再加入第三種、第四種等等，直到把整張圖填滿。
或者是用深度優先搜索算法，先一步步給圖像著色，若遇到相鄰點顏色相同就回溯，再換一種著色方法，直到問題解決為止。
比圍棋世界更複雜
如果圖的頂點數比較少，以上兩種方法還可行，但隨著頂點數的增加，以上兩種算法的局限性就暴露了出來。
△ 用貪心算法著色和最優解的對比
貪心算法會陷入局部最優解，而深度優先搜索算法的運算量會越來越大，以至於完全不可行。
圖著色問題的複雜度隨著頂點數增加而急劇增長。當頂點數達到 512 時，其可能得狀態數就達到達到了10^790，遠超圍棋的10^460，當然更是比全宇宙的粒子數10^ 80 多得多。
即使中等大小圖的狀態數也遠超圍棋，如果頂點數量達到 1000 萬，複雜度會大得驚人，相當於在 1 後面有 4583 萬個0。
另外著色問題還有另一個複雜維度，圍棋算法可以反覆在同一張相同棋盤上進行測試，而圖即使頂點相同，因為連接各點的邊不相同，結構也不完全相同。