選自quantamagazine
作者：Erica Klarreich
機器之心編譯
編輯：rome rome
計算機科學家組成的科研團隊，為計算機領域中經典的最大流問題提出了一種速度極快的演算法。最大流問題是一種組合最最佳化問題，討論如何充分利用裝置的能力，使得運輸的流量最大以取得最好的效果。
這個問題在網路流理論中非常基礎。「新演算法快的離譜。其實，我本來堅信這個問題不可能存在這麼高效的演算法，」來自耶魯大學的 Daniel Spielman 說道。
自 20 世紀 50 年代以來，人們一直在研究最大流量，當時研究最大流是為了建模研究前蘇聯鐵路系統。
「對它的研究甚至比計算機科學理論還古老，」來自谷歌加州山景城研究中心的 Edith Cohen 這樣說。
這個問題通向很多應用：網際網路資料流、航空公司日程安排，甚至包含將求職者與空缺職位進行匹配。這篇新論文既處理了最大流量問題，也處理了更一般的問題，即處理最大流同時還希望最小化成本。多年來，這兩個問題激發了演算法技術的許多重大進步。Spielman 說：“這幾乎就是我們一直耕耘演算法領域的原因。“
新演算法在「近似線性」的時間內解決了這兩個問題，就是說該演算法的執行時間基本與記錄網路細節所需的時間正比。對於所有可能的網路，解決這些問題的其他演算法都無法達到如此快的速度。加州大學伯克利分校的 Satish Rao 表示，這個結果讓他跳了起來：「簡直太棒了。」
Spielman 則認為，我們已經找到如此快的演算法，現在是時候著手思考解決之前沒有想過的各種應用問題了。
目前，新方法主要是理論上的提升，因為演算法速度的提升還只適用於比現實世界中遇到的大得多的網路，對於這些網路，最大流量問題已經可以很快地得到答案（至少在不考慮代價最小化的情況下）。加拿大滑鐵盧大學的 Richard Peng 預計，新演算法可能在一年內得到實際應用，他是該演算法的六位創造者之一。
有研究人員認為，在未來幾年裡，計算機科學家可能會找到方法使其更實用，甚至可能更快。
麻省理工學院的 Aleksander M dry 說，未來即使有所改進，但這篇新論文也是「扣籃大賽中最精彩的扣籃」。他說，這基本上是最好的」。
一次一條路徑
Richard Peng 表示，很多計算機科學家在研究最大流問題，以至於在會議上討論過去的工作就像過電影最後的鳴謝部分。但大多數人都同意第一個形式化演算法是 1956 年由 Lester Ford 和 Delbert Fulkerson 應用貪心演算法求解最大流，這種方法在每一步都使用最容易得到的物件。
你可以這樣理解這種方法：首先，設想一個高速公路網路，你希望在給定的時間內將盡可能多的送貨卡車從洛杉磯運送到紐約市。Ford 和 Fulkerson 的演算法從選擇從洛杉磯到紐約的一條路徑開始，並沿著這條路徑安排儘可能多的卡車。該方法通常不會利用該特定道路上所有道路的全部通行能力：如果道路的是五車道公路，但它透過一架兩車道的橋樑，那麼你在任何時候都只能啟動兩輛卡車。
接下來，該演算法修改這些路段的通行能力，以反映現在使用了部分路段的通行能力：它從路段的通行能力中減去傳送的卡車數量，因此五車道公路現在通行能力是 3，而雙車道橋的通行能力為零。同時，該演算法在反向方向上為這些公路的通行能力增加了 2，因此，如果我們願意，我們可以稍後撤銷部分流量。
然後，該演算法找到一條從洛杉磯到紐約的新路徑，該路徑可以容納一些卡車，沿著該路徑傳送儘可能多的卡車，並再次更新容量。經過有限數量的這些步驟後，從洛杉磯到紐約的道路將無法容納更多的卡車，到這裡演算法就完成了：我們只要將構建的所有流量合併，就可以透過獲得網路最大可能的流量。
Ford 和 Fulkerson 的演算法並不試圖在這一過程中做出聰明的選擇。如果它選擇了一條切斷其他有用路徑的路徑，那是演算法之後要處理的問題。在該演算法發表後的幾十年裡，研究人員試圖透過讓演算法做出更明智的選擇來加速執行時間，例如總是使用最短的可用路徑或可用容量最大的路徑。
1970 年，Yefim Dinitz 發現了一種在一步中使用網路中所有最短路徑的有效方法。這一演算法在低容量網路中的執行時間，由 Shimon Even 和 Robert Tarjan 證明為 m^1。5 （m： 網路中的連結數，相比之下，Ford-Fulkerson 演算法在低容量網路中需要多個 m^2）。
近 30 年後，Rao 和 Andrew Goldberg 對高容量網路得出了類似的結果。但沒有人能擊敗 m^1。5 指數。這篇新論文的作者之一、多倫多大學的蘇珊特 薩赫德瓦（SushantSachdeva）說：「進入 21 世紀……m^1。5 的壁壘根深蒂固。」為了取得更大進展，計算機科學家必須尋找完全不同的方法。
從組合到微積分
到目前為止，所有這些演算法都採用了組合方法，即在每個步驟中尋找某種型別的結構，並使用該結構來更新流。但在 2003 年，南加州大學的 Spielman 和 ShangHua Teng 開啟了一扇完全不同的「最佳化」方法之門，在這種方法中，使用微積分技術為指導尋找最優解。
Spielman 和 Teng 開發了一種快速最佳化演算法，該演算法解決的不是最大流量問題，而是一個密切相關的問題，即透過每根具有給定電阻的導線網路找到能量最低的電流。Sachdeva 說，Spielman 和 Teng 的進步是「關鍵時刻」。
建立確定網路最大流量和最小成本的超快速演算法團隊成員 （從左上角順時針開始）：Yang Liu、 Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng、Sushant Sachdeva。
研究人員很快開始探索如何將這一進展應用於最大流問題。可以把公路網想象成由電線組成的網路，在沒有太多可用容量的公路上增加電阻，阻止電子穿過公路。由於 Spielman 和 Teng 的工作，我們可以快速計算透過這些電線的電流，這個模型具有透過高速公路的最大車輛流量的粗略屬性。（它們不會完全相同，因為電流問題對導線的容量沒有任何硬性限制。）
然後，在產生了這個初始流量之後，我們可以像 Ford 和 Fulkerson 的組合演算法一樣重新調整容量。接下來，可以重置每條導線的電阻，以反映這些變化的量，並解決新生成的電路問題。
與一次改變一個網路塊的組合方法不同，Spielman 和 Teng 的最佳化方法每次完成整個網路的掃描。這使得每一步都更加有效，因此達到最大值需要的總步驟更少。2008 年，谷歌的 Samuel Daitch 和 Spielman 使用了這種方法，基本上與之前的最大流量 m^1。5 的界限相近。在 2013 年，M dry 進一步推進了該方法，以突破低容量網路的 m^1。5，將執行時間提高到大約 m^1。43 的倍數。「這太令人震驚了，」Rao 表示。
接下來的幾年裡，研究人員進一步擴充套件了這種方法，但他們的結果仍停留在 m^1。33。他們開始懷疑這個指數是否是一個基本極限。
對於最大流演算法來說，最快的可想象執行時間應該是 m 倍（即 m^1。0），因為寫下一個網路需要 m 個步驟的倍數。這被稱為線性時間。但對許多研究人員來說，這樣一個極快的演算法似乎是不可想象的。「沒有任何充分的理由，能讓我們相信能做到這一點，」Spielman 說到。
縮小、重用、回收
這篇新論文的作者認為，Daitch 和 Spielman 的方法有更多的優點。M dry 曾用它來減少解決最大流問題所需的步驟數，但這種減少是有代價的：在每一步中，整個網路都必須重寫，並且必須從頭開始解決電力流問題。
這種方法將 Spielman 和 Teng 的演算法視為黑盒 —— 不管演算法內部在做什麼。六位研究人員決定深入研究該演算法的核心，並根據最大流量問題調整其各個組成部分。他們懷疑，這些元件甚至可能讓他們解決更難的「最低成本問題，在這個問題是尋找最便宜的方式來運輸給定數量的材料。計算機科學家早就知道，任何最小成本演算法都可以解決最大流問題。
與其他最佳化方法一樣，研究人員提出了流的「能量」概念即連結成本和容量的函式。將流量從昂貴的低容量鏈路轉移到廉價的高容量鏈路會降低系統的總能量。
為了弄清楚如何快速地將流移向低能狀態，研究人員將這種最佳化方法與舊的組合觀點相結合。後者一次只更改網路的一部分，提供了重用前面步驟中的一些工作的可能性。
在每一步中，演算法都會尋找一個可以減少能量的迴圈，即開始和結束是同一個點的路徑。基本想法很簡單：假設你建立了一條從芝加哥到紐約的收費公路，然後你發現有一條更便宜的高速公路。這時把紐約新增進迴圈，沿著昂貴的道路執行到芝加哥，然後沿著較便宜的路線返回，形成一個迴圈，從而替換掉昂貴的路徑，從而降低了流量的總成本。
加拿大維多利亞大學的 Valerie King 說，這種方法使用的步驟比「電氣方法」多得多，所以乍一看聽起來「像是在倒退」。為了進行補償，演算法必須在每一步都以難以置信的速度找到優質的迴圈，比檢查整個網路所需的速度還要快。
這就是 Spielman 和 Teng 的演算法的工作原理。他們的演算法提供了一種使用「低延伸生成樹」的新方法，這種樹是演算法的關鍵，它可以捕獲網路的許多最顯著的特徵。給定這樣一個樹，透過在樹外新增一個連結，總是可以構建至少一個良好的迴圈。因此，擁有一個低伸縮的生成樹可以大大減少需要考慮的迴圈數。
即便如此，為了讓演算法快速執行，團隊也無法在每一步都構建一個全新的生成樹。相反，他們必須確保每個新週期在生成樹中只產生較小的漣漪效應，以便重用以前的大部分計算。該論文作者之一、斯坦福大學研究生 Yang Liu 表示，實現這種控制水平是「核心難點」。
最終，研究人員建立了一種在「幾乎線性」時間內執行的演算法，這意味著當用越大的網路時，它的執行時間越接近 m。
該演算法借鑑了 Spielman 和 Teng 的許多想法，並將它們結合在一起，形成了一種全新的東西。Spielman 說，如果你只見過馬拉的車，那麼現在的演算法就像是汽車。「我看到它有一個可以坐的地方，我看到它有輪子，我看到它有東西可以讓它移動。但他們已經用發動機代替了馬。」
Rao 推測，該團隊的分析是漫長而複雜的，但其他研究人員很快就會深入研究以簡化問題。他說：「我的感覺是，未來幾年，一切都會變得更乾淨、更好。」
Spielman 說，一旦演算法得到簡化，計算機科學家可能會開始將其用作解決不同問題的演算法的子程式。「現在我們知道我們可以很快做到這一點，人們會發現各種各樣的應用程式，這是他們以前沒有想過。」
另外，該演算法對最大流問題令人眩暈的加速，讓 Spielman 對算法理論中的其他核心問題有了期待，「我們還能做些什麼？」