大數據文摘出品
來源：quanta
編譯：徐玲、coolboy
試想，當你剛進入研究生院的時候，你的導師向你提出：我們一起來研究理論計算機科學領域最有名的待解決問題吧，你會是什麼心情？
但這就是Nathan Klein兩年前遇到的事，他的導師邀請他一起解決的問題是旅行商問題，是理論計算機科學家試圖解決的基礎性問題之一，旨在探索高效計算（efficient computation）的極限。
即使無法解決該問題，他們認為Klein也會在這個過程中學到很多東西。Klein也接受了這個主意，他說：「我當時還不知道害怕，」「我只是一年級的研究生，根本搞不清狀況。」
好在，最後Klein也順利畢業了，也就是說，他們實現了計算機科學家追求了近半個世紀的目標：一種找到旅行商問題近似解的更好方法，在7月份發表的arXiv論文中進行了詳細的闡述。
這個優化問題，其目標是尋找走完一組城市的最短路徑（或成本最低的路徑）。這個問題的解決方案可用於DNA測序和共享物流規劃等許多應用。幾十年來，這一問題激發了計算機科學領域多項根本性的進步，有助於闡明線性規劃等技術的力量。不過，其潛在的可能性還未得到完全探索。
正如計算複雜性領域專家Christos Papadimitriou說的那樣，旅行商問題「不是問題，而是一個會讓人上癮的東西」。
大多數計算機科學家認為：並不存在一種有效解決各種城市組合可能性的最優解。但在1976年，Nicos Christofides提出了一種能有效找到近似解的算法——往返旅程最多比最佳往返旅程長50%。那時，計算機科學家預計很快就有人能在Christofides的簡單算法上實現提升，進一步接近真實解。但預期的進展並未到來。
史丹福大學教授Amin Saberi表示：「很多人花了無數時間試圖提升這一結果。」
現在，Karlin、Klein和Oveis Gharan已經證明：十年前設計的一種算法優於Christofides算法的50%標準，雖然它也只是將這個百分數減少了非常小的數字（10^-36，0.2 billionth of a trillionth of a trillionth of a percent）。儘管如此，進步終究是進步，這一微小進步能夠突破理論上的僵局以及心理上的門檻。研究者希望這能帶來契機，實現進一步的改進。
華盛頓大學研究生 Nathan Klein（左）及其導師Anna Karlin和Shayan Oveis Gharan
康奈爾大學教授David Williamson表示：「這是我一生事業所追求的目標。」他自 1980 年代以來一直在研究旅行商問題。
Williamson說：「這個新結果是向人們證明高效計算的前沿實際上比我們預期的要好的第一步。」
進展
儘管可能並不存在找到最短旅程的有效方法，但卻有可能找到足夠好路徑的方法：連接所有城市的最短樹（tree），也就是一個由連接（邊）構成的，沒有封閉迴路。Christofides的算法使用了這個樹作為骨幹部分來進行往返旅行，然後通過添加額外的邊來將其轉換成往返旅程。
任何往返旅程路線連接每個城市的邊的數量都必然為偶數，因為每一次到達之後都必然有一次離開。事實證明反過來也是如此——如果網絡中每座城市的連接數為偶數，則網絡中的邊必然能實現往返旅程。
而連接所有城市的最短樹則不具備這種偶數性質，因為任何在路線末端的城市與另一個城市僅有一個連接。因此為了將最短樹轉換到往返旅程中，Christofides（已於去年逝世）發現最佳方法是連接有奇數條邊的城市對。他證明，所得到的往返旅程永遠不會比最佳往返旅程長50%。
在此過程中，他設計出了理論計算機科學領域最有名的近似算法——這個算法通常是教科書或課程中提到的第一個例子。
法國格勒諾布爾-阿爾卑斯大學與法國國家科學研究中心的Alantha Newman稱：「這個簡單算法人人皆知。」而且當你學習它的時候，「它就是當前最佳方法。」—這個說法直到7月份時還依然成立。
長期以來，計算機科學家猜想應該存在優於Christofides算法的近似算法。畢竟他的算法雖然簡單直觀，但並不總能有效設計出旅行商行進路線，因為連接城市的最短樹可能並非你可選擇的最佳骨幹。舉例來說，如果這個樹有很多分支，那麼每個分支末端的城市都需要與另一個城市匹配，這就有可能形成大量成本高昂的新連接。
2010年，喬治亞理工學院的Oveis Gharan、Saberi和Mohit Singh開始思考：也許可以不選擇連接所有城市的最短樹，而從一個精心選取的集合中取一個隨機樹來改進Christofides算法。他們的靈感來自旅行商問題的一個替代版本，該問題中旅行商可沿路徑組合行進，比如為了到達丹佛，可以從芝加哥到丹佛的3/4加上洛杉磯到丹佛的路徑。
不同於常規的旅行商問題，這個分數化的問題可以得到有效解決。儘管這種分數化路徑（fractional route）並不具有實際意義，但計算機科學家長期認為，最佳的分數化路徑能為尋找優良的常規路徑提供粗略的指導。
因此，為了創建自己的算法，Oveis Gharan、Saberi和Mohit Singh定義了一種用於選取連接所有城市的樹的隨機過程，並令給定邊在該樹中的機率等於該邊在最佳分數化路徑中的分數。這樣的隨機過程有很多，研究者傾向於選擇能生成多個偶數連接城市的樹的隨機過程。在這個隨機過程選出一個特定的樹之後，再將他們的算法接入到Christofides的方案，匹配有奇數條邊的城市，並將結果轉化為一個往返旅程。
圖片來源：Samuel Velasco/Quanta Magazine
這個方法看起來很有希望，不止這三位研究者這麼看，其他計算機科學家也這麼想。瑞士洛桑聯邦理工學院副教授Ola Svensson表示：其中的直觀理解很簡單，但證明它卻又是一大難題。
不過，在第二年里，Oveis Gharan、Saberi和Singh成功證明他們的算法在「圖式」旅行商問題中優於Christofides算法。「圖式」旅行商問題將城市之間的距離表示為網絡（不必包含所有連接），其中所有邊的長度全都一樣。但他們沒能找到將這一結果擴展到一般旅行商問題的方法，一般旅行商問題中一些邊可能比另一些邊長很多。
Karlin表示：「如果在匹配中加入一條成本很高的邊，這個方案基本就完蛋了。」
進展的歷程
儘管如此，在這場合作中，Oveis Gharan有了一個不可動搖的信念：他們的算法在一般旅行商問題上同樣勝過Christofides算法。他說：「我從未懷疑過。」
接下來的很多年裡，這個問題一直在Oveis Gharan的腦中盤旋。他猜想，一個名為「多項式幾何」的數學學科中可能有他需要的工具，但這是理論計算機科學社區不太關注的領域。因此，當Karlin兩年前建議他一起指導天才研究生新生Nathan Klein時，他回答說：「沒問題，我們就試試看——我正好有個有趣的問題。」Nathan Klein在本科階段主修了數學和大提琴兩個專業。
Karlin當時想的是，就算沒有成果，這也是一個學習多項式幾何的好機會。她說：「我當時確實認為我們沒法解決這個問題。」
她和Oveis Gharan毫不猶豫地將Klein帶入到了計算機科學研究的這一深層領域。Oveis Gharan本人在2010年研究生階段時就研究旅行商問題。這兩位導師都認為給研究生布置難題大有裨益，尤其是前幾年他們還沒有出成果的壓力時。
這三位研究者開始了密切合作。Klein說：「我這兩年里思考的都是它。」
在第一年裡，他們解決了該問題的一個簡化版本，以便感受他們所面臨的難度。但即便在解決了簡化問題之後，Klein說解決一般旅行商問題還是「難如登天」。
儘管如此，他們已經很好地理解了所用的工具，尤其是多項式幾何。多項式是冪表達式，比如3x2y+8xz7。為了研究旅行商問題，他們將城市構成的地圖提煉成了多項式，其中每個變量表示城市之間的一條邊，而每一項表示可以連接所有城市的每個樹。然後使用數值因子對這些項進行加權，以反映各條邊在旅行商問題的分數解中的值。
他們發現，這個多項式具有一個他們需要的特性，即「實數穩定性」（real stability），也就是說能讓該多項式為零的複數永遠不會出現在複平面的上半部分。實數穩定性的優勢在於即便對多項式進行許多更改，它仍舊有效。
舉個例子，如果研究者想要關注特定的一些城市，他們可以使用單個變量表示連接一個城市的所有不同邊，然後將不關心的邊的變量設為1。在操作這些簡化版多項式時，他們的操作結果仍具有實數穩定性，這為各種技術的應用開啟了大門。
該方法讓研究者可以處理很多問題，比如算法被迫連接兩個相距較遠的城市的頻率是多少。在近80頁的分析中，他們成功證明該算法在一般旅行商問題上優於Christofides算法（該論文還未經過同行評議，但一些專家給予了肯定。）
論文剛完成，Oveis Gharan就給他的博士導師Saberi發了封電子郵件。他開玩笑道：「我想我終於畢業了。」
史丹福大學教授Amin Saberi（左）和喬治亞理工學院的Mohit Singh
儘管該研究實現的提升微乎其微，但計算機科學家希望這一突破能啟發進一步的進展。
回想2011年，那時候Oveis Gharan、Saberi和Singh解決了圖式旅行商問題。之後不到一年時間，其他研究者就提出了非常不同的算法，並極大提升了在圖式案例上的近似性能。現在在圖式案例上，這些算法已經將近似率（approximation factor）從Christofides算法的50%下降到了40%。
「當他們宣布有關圖式旅行商問題的結果時，我們覺得這是有可能的。我們也開始研究它。」後來在這一案例上取得進展的研究者Svensson說。他之前多年一直嘗試在一般旅行商問題上超過Christofides算法。他說：「現在我知道這是可能的，我會再次嘗試。」
過去幾十年來，旅行商問題已經催生了很多新方法。Oveis Gharan希望現在人們能看到多項式幾何的價值，而且事實上他已經成為這一方法的熱情布道者。在最近十年中或自他開始學習這一方法以來，多項式幾何已經幫助他證明了很多定理。他表示：這一工具「塑造了我的整個職業生涯」。
旅行商問題的新結果證明了該方法的強大。Newman稱：「仔細研究的話肯定能大受啟發。」
Klein現在則必須找一個新問題來研究了。「失去這個問題是有點悲傷，因為它在我的頭腦中構建了許多結構，但現在它們差不多都消失了。」但他對計算機科學研究的貢獻已經很令人滿意了。
「我感覺我們把未知之物又推進了一點。」
相關報道：
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/