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

牛頓家的計算機

2022年8月16日 10:54

計算機科學家組成的科研團隊，為計算機領域中經典的最大流問題提出了一種速度極快的算法。最大流問題是一種組合最優化問題，討論如何充分利用裝置的能力，使得運輸的流量最大以取得最好的效果。

計算機基礎問題，最大流問題獲突破性進展：新算法「快得離譜」的圖1

這個問題在網絡流理論中非常基礎。「新算法快的離譜。其實，我本來堅信這個問題不可能存在這么高效的算法，」來自耶魯大學的 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，因此，如果我們愿意，我們可以稍后撤銷部分流量。

然后，該算法找到一條從洛杉磯到紐約的新路徑，該路徑可以容納一些卡車，沿著該路徑發送盡可能多的卡車，并再次更新容量。經過有限數量的這些步驟后，從洛杉磯到紐約的道路將無法容納更多的卡車，到這里算法就完成了：我們只要將構建的所有流量合并，就可以通過獲得網絡最大可能的流量。

計算機基礎問題，最大流問題獲突破性進展：新算法「快得離譜」的圖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 的進步是「關鍵時刻」。

計算機基礎問題，最大流問題獲突破性進展：新算法「快得離譜」的圖3

創建確定網絡最大流量和最小成本的超快速算法團隊成員 (從左上角順時針開始):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 對算法理論中的其他核心問題有了期待，「我們還能做些什么？」

文章來源：機器之心
免責聲明：本文系網絡轉載，版權歸原作者所有。如涉及版權，請聯系刪除！

登錄后免費查看全文

立即登錄