Quanta Magazine：研究人員實現(xiàn)了網(wǎng)絡流“出奇快”的算法

大數(shù)據(jù)文摘授權轉(zhuǎn)載自zzllrr小樂

作者：Erica Klarreich

譯者：zzllrr小樂

一個計算機科學家團隊針對計算機科學中最古老的問題之一提出了一種速度顯著加快的算法：最大流（maximum flow）。該問題是如果網(wǎng)絡中的鏈路有容量限制，有多少材料可以通過網(wǎng)絡從源頭流到目的地。

耶魯大學的Daniel Spielman說，新算法“快得出奇”?！拔覍嶋H上曾經(jīng)傾向于相信......對這個問題很好的算法不會存在?！?/span>

最大流自 1950 年代以來一直被人們研究，當時它是為研究蘇聯(lián)鐵路系統(tǒng)而制定的。“它可能比計算機科學的理論還要古老，”加利福尼亞州山景城谷歌研究中心的 Edith Cohen 說。這個問題有很多應用：互聯(lián)網(wǎng)數(shù)據(jù)流、航空公司調(diào)度，甚至將求職者與空缺職位匹配。新論文處理了最大流和你還希望最小化成本的問題的更一般版本。多年來，這兩個問題激發(fā)了算法技術許多極大的進步?！八鼈儙缀蹙褪俏覀儞碛兴惴I域的原因，”Spielman說。

新算法在“幾乎線性”的時間內(nèi)解決了這兩個問題，這意味著算法的運行時間大致與首先寫下網(wǎng)絡細節(jié)所需的時間量成正比。對于所有可能的網(wǎng)絡，沒有其他算法能夠接近于以這種速度運行這些問題。這個成果讓他“上躥下跳” ，加州大學伯克利分校的Satish Rao說?！疤婷盍??！?/span>

現(xiàn)在我們知道我們可以非?？焖俚刈龅竭@一點，人們會發(fā)現(xiàn)各種各樣的應用程序，他們只是以前沒有考慮過。

目前，這主要是理論上的進步，因為速度改進只適用于遠大于我們在現(xiàn)實世界中遇到的網(wǎng)絡，最大流問題已經(jīng)可以相當快地解決（至少，如果他們不涉及最小化成本）。但該算法的六位創(chuàng)造者之一、加拿大滑鐵盧大學的Richard Peng預測，新算法的某些部分可能會在一年內(nèi)看到實際應用。研究人員表示，在未來幾年，計算機科學家可能會找到使其更實用甚至更快的方法。

麻省理工學院的Aleksander M?dry說，即使后續(xù)改進確實隨之而來，這篇新論文也相當于“灌籃高手” 。他說，這“基本上是最好的”。

一次一條路徑

Peng 說，如此多的計算機科學家研究了最大流，以至于會議上談論過去的工作看起來像是電影結束后的演職員表。但大多數(shù)人將第一個正式算法追溯到 1956 年，當時 Lester Ford 和 Delbert Fulkerson使用所謂的“貪婪”方法解決了最大流——這種方法在每一步都使用最容易獲得的對象。

要理解這種方法，請想象一個高速公路網(wǎng)絡，你希望在給定的時間內(nèi)將盡可能多的送貨卡車從洛杉磯運送到紐約市。Ford 和 Fulkerson 的算法首先選擇從洛杉磯到紐約的一條路徑，并沿該路徑安排盡可能多的卡車。這通常不會利用該特定路徑上所有道路的全部容量：如果你的路徑的一部分是一條五車道的高速公路，但它通向一座兩車道的橋梁，那么你在任何時候都只能發(fā)出兩輛卡車。

接下來，算法會修改這些路段的容量以反映你現(xiàn)在已經(jīng)使用了它們的一些容量：它從路段的容量中減去你發(fā)送的卡車數(shù)量，因此五車道高速公路現(xiàn)在只有容量3、雙車道橋的通行能力為零。同時，該算法在這些高速公路的反向容量上增加了 2，因此如果我們愿意，我們可以在以后撤消其中的一些流量。

然后，該算法會找到一條從洛杉磯到紐約的新路徑，該路徑可以容納一些卡車，沿該路徑發(fā)送盡可能多的卡車，并再次更新容量。經(jīng)過有限次的這些步驟，從洛杉磯到紐約的路徑將無法容納更多卡車，然后我們就完成了——我們只需將我們構建的所有流組合起來，我們就有了通過這個網(wǎng)絡最大可能的流。

Ford 和 Fulkerson 的算法并沒有嘗試在此過程中做出明智的選擇。如果它選擇了一條切斷其他有用路線的路徑，那只是它以后處理的問題。在該算法發(fā)表后的幾十年里，研究人員試圖通過讓算法做出更明智的選擇來加快運行時間——例如始終使用最短的可用路徑或具有最大可用容量的路徑。

1970 年，Yefim Dinitz找到了一種有效的方法，可以一步使用網(wǎng)絡中的所有最短路徑。這創(chuàng)建了一種算法，其在低容量網(wǎng)絡中的運行時間由 Shimon Even 和Robert Tarjan顯示為m^1.5的倍數(shù)，其中m是網(wǎng)絡中的鏈接數(shù)。（相比之下，F(xiàn)ord-Fulkerson 算法在低容量網(wǎng)絡中采用m2的倍數(shù)。）差不多 30 年后，Rao 和現(xiàn)在在亞馬遜工作的 Andrew Goldberg 對高容量網(wǎng)絡產(chǎn)生了類似的結果。但是沒有人能擊敗 1.5 的指數(shù)。“進入 2000 年代……這個m^ 1.5的屏障已加固。新論文的作者之一、多倫多大學的Sushant Sachdeva說。

為了取得進展，計算機科學家必須采取完全不同的方法。

從組合學到微積分

到目前為止，所有這些算法都采用了組合方法，它們在每一步中尋找某種類型的結構，并使用該結構來更新流。但在 2003 年，南加州大學的 Spielman 和Chang-Hua Teng打開了通往完全不同的“優(yōu)化”方法的大門，在這種方法中，使用微積分技術來引導你找到最優(yōu)解。

Spielman 和 Teng 開發(fā)了一種快速優(yōu)化算法，該算法解決的不是最大流問題，而是一個密切相關的問題，即通過每個具有給定電阻的導線網(wǎng)絡找到能量最低的電流。Sachdeva 說，Spielman和Teng的進步是“一個關鍵時刻”。

創(chuàng)建可以確定網(wǎng)絡最大流和最小成本的超快速算法的團隊：（從左上角順時針方向）Yang Liu、Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng 和 Sushant Sachdeva。

研究人員很快開始探索如何將這一進展應用于最大流問題。這個想法是將我們的高速公路網(wǎng)絡想象成一個電線網(wǎng)絡，并提高沒有太多可用容量的高速公路上的電阻，以阻止電子穿過它們。因為有了Spielman和Teng，我們可以快速計算出通過這些電線的電流，它就會具有高速公路上車輛最大流的粗略屬性。（它們不會完全相同，因為電流問題對電線的容量沒有任何硬性限制。）

然后，在產(chǎn)生了這個初始流后，你重新調(diào)整容量，就像在 Ford 和 Fulkerson 的組合算法中一樣。接下來，你重置每根電線的電阻以反映這些變化的容量并解決這個新的電氣問題，依此類推。

與一次更改網(wǎng)絡的一部分的組合方法不同，Spielman 和 Teng 的優(yōu)化方法一次涵蓋整個網(wǎng)絡。這使得每一步都更加強大，因此你需要更少的總步數(shù)來達到最大值。2008 年，Google 的 Samuel Daitch 和 Spielman使用這種方法基本上匹配了之前的m^ 1.5最大流界限。然后在 2013 年，M?dry 進一步推動了這一方法，突破了低容量網(wǎng)絡的m^  1.5障礙，將運行時間加快到m^ 1.43左右的倍數(shù)?！斑@令人震驚，”Rao說。

在接下來的幾年里，研究人員進一步推廣了這種方法，但他們被困在了m ^ 1.33上。他們開始懷疑這個指數(shù)是否是一個基本極限。

最大流算法的最快可能運行時間將只是 m 的倍數(shù)（即m^  1.0 ），因為僅寫下一個網(wǎng)絡就需要m步的倍數(shù)。這被稱為線性時間。但對許多研究人員來說，如此快速的算法似乎是不可想象的。

“沒有充分的理由相信我們可以做到這一點，”Spielman說。

簡化，復用，循環(huán)

但這篇新論文的作者認為，Daitch和Spielman的方法可以榨出更多的汁液。M?dry 曾使用它來減少解決最大流問題所需的步驟數(shù)量，但這種減少是有代價的：在每一步，都必須重寫整個網(wǎng)絡，并從頭開始解決其電流問題。

這種方法將Spielman和Teng的算法視為一個黑匣子——算法在內(nèi)部做什么并不重要。六名研究人員決定深入挖掘算法的核心，并根據(jù)最大流問題調(diào)整其各種組件。他們懷疑，這些組件甚至可以讓他們解決更難的“最低成本”問題，在這個問題中，你正在尋找最便宜的方法來路由給定數(shù)量的材料。計算機科學家早就知道，任何最小成本算法也可以解決最大流問題。

與其他優(yōu)化方法一樣，研究人員提出了流“能量”的概念——一個考慮鏈接成本和容量的函數(shù)。將流從昂貴的低容量鏈路轉(zhuǎn)移到廉價的高容量鏈路會降低系統(tǒng)的總能量。

為了弄清楚如何快速將流移向低能量狀態(tài)，研究人員將這種優(yōu)化方法與舊的組合觀點相結合。后者一次只更改網(wǎng)絡的一部分，提供了重用之前步驟中的一些工作的潛力。

在每一步，算法都會尋找一個循環(huán)——一條在同一點開始和結束的路徑——可以減少能量?；鞠敕ê芎唵危合胂笠幌?，你創(chuàng)建了一條將卡車從芝加哥沿收費公路運送到紐約的流，但隨后你發(fā)現(xiàn)有一條更便宜的高速公路可用。增加從紐約開始的循環(huán)，沿著昂貴的道路運行到芝加哥，然后沿著更便宜的路線返回，有效地取消了昂貴的路徑并用更便宜的路徑取而代之，從而降低了流的總成本。

加拿大維多利亞大學的Valerie King說，這種方法比電路方法使用了更多的步驟，因此乍一看“聽起來像是在倒退” 。作為補償，算法在每一步都必須非常快地找到一個好的循環(huán)——比僅僅檢查整個網(wǎng)絡所需的速度還要快。

這就是 Spielman 和 Teng 算法的內(nèi)部工作原理。他們的算法提供了一種使用“低拉伸生成樹”（low-stretch spanning tree）的新方法——一種捕獲網(wǎng)絡中許多最顯著特征的內(nèi)部主干。給定這樣一棵樹，你總是可以通過從樹外部添加一個鏈接來構建至少一個良好的循環(huán)。因此，擁有低拉伸生成樹會大大減少你需要考慮的循環(huán)數(shù)。

即使這樣，為了讓算法快速運行，團隊也無法在每一步都構建一個全新的生成樹。相反，他們必須確保每個新循環(huán)在生成樹中只引起輕微的漣漪效應，以便他們可以重用之前的大部分計算。論文作者之一、斯坦福大學研究生Yang Liu說，達到這種控制水平是“核心難點” 。

最終，研究人員創(chuàng)建了一種在“幾乎線性”時間內(nèi)運行的算法，這意味著當你看到越來越大的網(wǎng)絡時，它的運行時間接近m的某個倍數(shù)。這是一場“巡回演出”，M?dry 說。

該算法使用了 Spielman 和 Teng 工作中的許多想法，但它將它們組合在一起形成了全新的東西。Spielman說，如果你只看過馬車，看算法就像遇到汽車一樣?！拔铱吹剿幸粋€可以坐的地方，我看到它有輪子，我看到它有一些東西可以讓它移動。但他們已經(jīng)用發(fā)動機代替了馬?！?/span>

Rao 預測，該團隊的分析冗長而復雜，但其他研究人員很快就會投入其中以簡化事情?！拔业母杏X是，在接下來的幾年里，一切都會變得更清潔、更好，”他說。

Spielman說，一旦算法得到簡化，計算機科學家可能會開始將其用作解決不同問題的算法的子程序?！艾F(xiàn)在我們知道我們可以非常快地做到這一點，人們會找到他們以前沒有想到的各種應用?！?/span>

這種對最大流問題的令人眼花繚亂的加速讓Spielman想知道算法理論中的其他核心問題?！拔覀冞€能做什么？”

原文鏈接：

https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/