（圖片來源：Islenia Mil for Quanta Magazine）

兩(liang) 年前，當Nathan Klein開始他的研究生學業(ye) 時，他的導師們(men) 提出了一個(ge) “謙虛的”計劃：一起研究理論計算機科學中最著名的難題之一。

即使沒有想到可以真的解決(jue) 它，導師們(men) 也認為(wei) ，Klein會(hui) 在這個(ge) 過程中學到很多東(dong) 西。他接受了這個(ge) 提議。“我都不知道自己應該被嚇倒。”他說，“我隻是個(ge) 博一的研究生——我不知道發生了什麽(me) 。”

現在，Klein和他在美國華盛頓大學的導師Anna Karlin，Shayan Oveis Gharan於(yu) 7月在線發表了一篇論文，實現了計算機科學家近半個(ge) 世紀以來追求的目標：找到了一種更好的方法來解決(jue) “旅行推銷員”問題的近似方案。

旅行推銷員問題（Traveling Salesman Problem）是數學領域的著名問題之一。假設有一個(ge) 旅行商人要拜訪n個(ge) 城市，他必須選擇所要走的路徑，路徑的限製是每個(ge) 城市隻能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為(wei) 所有路徑之中的最小值。

這個(ge) 組合優(you) 化問題，致力於(yu) 尋求最短（或最“便宜”）的多城市間往返路徑距離，其應用範圍上至DNA測序，下至乘車物流。幾十年來，它促進推動了計算機科學中許多最基本的進步，幫助闡明了線性編程等技術的力量。但研究人員還沒有將其可能性探索完全——這並不是因為(wei) 他們(men) 不想嚐試。

旅行推銷員問題。 （圖片來源：Gfycat）

正如計算複雜性領域的頂尖專(zhuan) 家Christos Papadimitriou喜歡說的那樣，旅行推銷員問題“不是問題，而是一種癮”。

多數學者認為(wei) ，沒有一種算法可以有效地從(cong) 所有可能的城市組合中找出最佳解決(jue) 方案。但在1976年，Nicos Christofides提出了一種算法，可以高效地找到近似解，令往返距離可以不超出最佳路徑的1.5倍。當時，學界期望很快就會(hui) 有人對Christofides 的簡單算法進行改進，並向真正的解決(jue) 方案進一步接近。但預期的進展並沒有到來。

Nicos Christofides （圖片來源：imperial.ac.uk）

斯坦福大學的 Amin Saberi 說：“很多人花了無數時間，試圖改進這個(ge) 結果。”

現在，Karlin、Klein和Oveis Gharan已經證明，十年前被設計出的一種算法超越了Christofides的算法。雖然新方法隻比後者縮短了五千萬(wan) 億(yi) 分之一，但這個(ge) 看似微不足道的進步既突破了理論上的困局，也突破了心理上的。研究人員希望，這將為(wei) 進一步的改進打開一扇閘門。

“這是我窮盡一生想追求的結果。”康奈爾大學的David Williamson說，他從(cong) 上世紀80年代起就開始研究旅行推銷員問題。

旅行推銷員問題作為(wei) 少數幾個(ge) 被理論計算機科學家經久不息研究的基礎性問題之一，被一次又一次地用來測試高效計算的極限。Williamson說，新的結果“是表明高效計算的前沿進展實際上比我們(men) 想象得更出色的第一步”。

一個(ge) “小”進步

雖然總能找到最短路徑的有效方法或許不存在，但我們(men) 有可能找到幾乎一樣好的東(dong) 西：連接所有城市的最短“樹”，也就是不包含閉環的連接（“邊”）構成的網絡。Christofides的算法使用了這類樹作為(wei) 骨幹，增加額外的邊，將其轉換為(wei) 往返路徑。

任何一條往返路徑都必須有偶數數量的邊進入每個(ge) 城市（節點），因為(wei) 每個(ge) 到達城市後麵都緊跟一個(ge) 作為(wei) 出發點的城市。事實證明，反過來也是如此——如果單一網絡中的每個(ge) 城市都有偶數個(ge) 連接，那麽(me) 網絡的邊一定會(hui) 形成一條往返路徑。

連接所有城市的最短樹缺乏這種均勻屬性，因為(wei) 任何一個(ge) 分支末端的城市與(yu) 另一個(ge) 城市隻有一條邊相互連接。因此，為(wei) 了將最短樹變成往返路徑，Christofides（已於(yu) 2019年去世）找到了連接具有奇數邊的城市對的最佳方法。然後，他證明了由此產(chan) 生的往返路徑絕不會(hui) 比可能的最佳往返路徑長50%以上。

在這個(ge) 過程中，他設計了可能是理論計算機科學中最著名的近似算法——它總是教科書(shu) 和課堂上第一個(ge) 出現的算法例子。

“每個(ge) 人都知道這個(ge) 簡單的算法，”法國格勒諾布爾-阿爾卑斯大學和國家科學研究中心的研究員Alantha Newman說，當你認識它的時候，“你知道的已經是當下最先進的星空体育官网入口网站了。”至少，在今年7月之前，這是事實。

計算機科學家一直懷疑，應該存在一種近似算法能勝過Christofides的算法。畢竟，他簡單直觀的算法在設計旅行推銷員路線時並不總是那麽(me) 有效，因為(wei) 連接城市的最短樹可能不是你能選擇的最佳骨幹。例如，假若這棵樹有很多分支，分支末端的每個(ge) 城市都需要與(yu) 另一個(ge) 城市進行匹配以形成往返路徑，可能會(hui) 帶來很多高成本的新連接。

2010年，佐治亞(ya) 理工學院的Oveis Gharan、Saberi和Mohit Singh開始琢磨能否改進Christofides的算法：不是選擇連接所有城市的最短樹，而是從(cong) 被精心挑選出的集合中隨機選擇一棵樹。他們(men) 從(cong) 旅行推銷員問題的另一個(ge) 版本中獲得靈感，在這個(ge) 問題中，你被允許沿著組合路徑旅行——也許你去往丹佛的路線可以分成兩(liang) 段：從(cong) 芝加哥到丹佛的3/4加上從(cong) 洛杉磯到丹佛的1/4。

與(yu) 普通的旅行推銷員問題不同，這個(ge) 分段問題是可以被有效解決(jue) 的。而且雖然分段路線沒有物理意義(yi) ，但計算機科學家一直認為(wei) ，最佳的分段路線應該可以為(wei) 好的普通路線提供大致的輪廓指導。

因此，為(wei) 了創建他們(men) 的算法，Oveis Gharan、Saberi和Singh定義(yi) 了一個(ge) 隨機過程，該過程挑選出一棵連接所有城市的樹，使給定邊位於(yu) 樹上的概率等於(yu) 該邊長度在最佳分段路線中的占比。這樣的隨機過程有很多，所以研究人員選擇了一個(ge) 傾(qing) 向於(yu) 產(chan) 生許多均勻連接城市的樹的隨機過程。在這個(ge) 隨機過程產(chan) 出一棵特定的樹後，他們(men) 的算法將其插入Christofides的方案中，用於(yu) 匹配具有奇數邊的城市，將其轉換為(wei) 往返路徑。

不僅(jin) 在三位研究人員眼中，在其他計算機科學家看來，這種方法似乎都很有前途。“直覺上，它很單純；”瑞士洛桑聯邦理工學院的Ola Svensson說，但“要把它證明出來可就完全不一樣了”。

第二年，Oveis Gharan、Saberi和Singh成功地證明了他們(men) 的算法在“圖形化”旅行推銷員問題上勝過Christofides的算法——城市之間的距離由一個(ge) 網絡（不一定包括所有的連接）來表示，在這個(ge) 網絡中，每條邊都有相同的長度。但研究人員無法將他們(men) 的結果擴展到一般性的旅行推銷員問題上：在這個(ge) 問題上，一些邊可能比其他邊長很多。

“如果我們(men) 必須為(wei) 這種組合增加一條超級浪費距離的邊，那麽(me) 我們(men) 基本上就完蛋了。”Karlin說。

推動邊界

盡管如此，Oveis Gharan 還是從(cong) 那次合作中獲得一個(ge) 不可動搖的信念，那就是他們(men) 的算法應該可以在廣義(yi) 旅行推銷員問題上擊敗Christofides 的。“我從(cong) 來沒有懷疑過這一點。”他說。

在之後的歲月裏，Oveis Gharan不斷在腦海中反芻這個(ge) 問題。他懷疑，在理論計算機科學界鮮為(wei) 人知的一門名為(wei) “多項式幾何”的數學學科中，或許有他需要的工具。因此，當兩(liang) 年前Karlin來找他，建議他們(men) 共同指導一個(ge) 名叫Nathan Klein的優(you) 秀新研究生（他主修雙專(zhuan) 業(ye) ：數學和大提琴）時，他說：“好吧，讓我們(men) 試試，我這兒(er) 有個(ge) 好玩的問題。”

左起：Nathan Klein、他的導師Anna Karlin和Shayan Oveis Gharan. （圖片來源：Quanta magazine）

Karlin認為(wei) ，即使沒有其他原因，這個(ge) 課題也是可以讓人了解更多多項式幾何的有趣機會(hui) 。“我真的沒想到我們(men) 能解決(jue) 這個(ge) 問題。”她說。

她和Oveis Gharan毫不猶豫地把Klein扔進了計算機科學研究的最深層。Oveis Gharan自己也曾在十年前以研究生身份琢磨了旅行推銷員問題一番。而兩(liang) 位導師也一致認同給研究生分配難題的好處，尤其是在頭幾年，因為(wei) 他們(men) 將不會(hui) 麵對必須取得成果的壓力。

三人進入了緊張的合作中。“兩(liang) 年來，這個(ge) 問題成了我腦海中的一切。”Klein說。

他們(men) 把第一年的時間用來解決(jue) 問題的簡化版，以了解所麵臨(lin) 的挑戰。但即使在完成了這些工作之後，一般性的原問題仍然讓他們(men) 感覺像是在“完成登月計劃”，Klein說。

不過，他們(men) 還是用自己的工具找到了思路，尤其是多項式幾何。多項式是由數字和指數型變量組成的項的組合（如3x2y+8xz7）。為(wei) 了研究旅行推銷員問題，研究人員將一張城市地圖提煉成一個(ge) 多項式，城市之間的每條邊都由一個(ge) 變量代表，每棵可以連接所有城市的樹都由多項式中的一項代表。然後，數值因子對這些項進行加權，以反映每條邊在旅行推銷員問題的分數解中的價(jia) 值。

他們(men) 發現，這個(ge) 多項式有一個(ge) 令人垂涎的特性——“實部穩定性”（real stabilty），這意味著使多項式結果為(wei) 零的複數部分永遠不會(hui) 位於(yu) 複平麵的上半部分。這個(ge) 特性的好處是，即使對多項式進行多種改變，它也會(hui) 保持有效。因此，舉(ju) 例來說，如果研究人員想關(guan) 注特定城市，他們(men) 可以用一個(ge) 單一變量來代表所有通往城市的不同邊，並將代表他們(men) 不關(guan) 心的邊的變量設置為(wei) 1。當他們(men) 對這些簡化的多項式進行操作時，他們(men) 的操作結果仍然具有實部穩定性，這為(wei) 種種技術打開了大門。

這種方法使得研究人員能夠掌握一些問題，如“算法曾多少次被迫連接兩(liang) 個(ge) 遙遠城市”。在一份近80頁的分析中，他們(men) 成功地證明了該算法在廣義(yi) 旅行推銷員問題上勝過了Christofides的算法（該論文還沒有經過同行評審，但專(zhuan) 家們(men) 確信它是正確的）。論文完成後，Oveis Gharan就給他曾經的博導Saberi發了一封郵件。“我想我終於(yu) 可以畢業(ye) 了。”他玩笑式地說。

雖然研究人員建立的改進是微乎其微的，但計算機科學家們(men) 希望這一突破能進一步激勵該領域的快速進展。早在2011年，當Oveis Gharan、Saberi和Singh弄清圖形化案例時，就發生過這樣的事情。在一年之內(nei) ，其他研究人員提出了完全不同的算法，極大地改善了上述圖形化案例中的近似係數，現在已經降低到40%，而不是 Christofides的50%。

“當他們(men) 宣布關(guan) 於(yu) 圖形化案例的結果時，……讓我們(men) 認為(wei) 這是可能的。這鼓舞了我們(men) 。”在該案例中取得進一步進展的研究人員之一Svensson說。他多年來一直在嚐試擊敗Christofides的一般性旅行推銷員問題的算法。“現在，既然我知道這是可能的，我會(hui) 再試一次。”他說。

幾十年來，已經出現了許多突出的，用於(yu) 解決(jue) 旅行推銷員問題的新方法。Oveis Gharan希望多項式幾何將在舞台上發光發熱。

他已經成為(wei) 了這個(ge) 工具的熱心傳(chuan) 播者。在他開始學習(xi) 這種方法後的十幾年裏，該方法幫助他證明了各種各樣的定理。他說，這個(ge) 工具“塑造了我的整個(ge) 職業(ye) 生涯”。

Newman說，新的旅行推銷員問題的結果凸顯了這種方法的力量。“這肯定是一種啟發，讓我們(men) 得以去更仔細地觀察它。”

Klein現在要找一個(ge) 新的問題來沉迷了。“失去這個(ge) 問題讓我有點難過，因為(wei) 它剛剛在我的腦海中建立了那麽(me) 多結構，現在它們(men) 都有點消失了。”他說，但他已經獲得了一個(ge) 最完美的計算機科學研究入門了，“我覺得我們(men) 把未知事物的邊界向外推動了一點”。

作者：Erica Klarreich

翻譯：鄭蘊儀(yi)

審校：魏瀟

引進來源：Quanta magazine

引進鏈接：https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/