電腦基礎問題，最大流問題獲突破性進展：新演算法「快得離譜」

這個問題在網路流理論中非常基礎。 「新演算法快的離譜。其實，我本來堅信這個問題不可能有這麼有效率的演算法，」來自耶魯大學的 Daniel Spielman 說。

自 20 世紀 50 年代以來，人們一直在研究最大流量，當時研究最大流是為了建模研究前蘇聯鐵路系統。 「對它的研究甚至比電腦科學理論還要古老，」來自Google加州山景城研究中心的 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 年，Google的 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 對演算法理論中的其他核心問題有了期待，「我們還能做些什麼？」#######

以上是電腦基礎問題，最大流問題獲突破性進展：新演算法「快得離譜」的詳細內容。更多資訊請關注PHP中文網其他相關文章！