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

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

作者：Erica Klarreich

譯者：zzllrr小樂(lè)

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

耶魯大學(xué)的Daniel Spielman說(shuō)，新算法“快得出奇”?！拔覍?shí)際上曾經(jīng)傾向于相信......對(duì)這個(gè)問(wèn)題很好的算法不會(huì)存在?！?/span>

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

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

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

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

麻省理工學(xué)院的Aleksander M?dry說(shuō)，即使后續(xù)改進(jìn)確實(shí)隨之而來(lái)，這篇新論文也相當(dāng)于“灌籃高手” 。他說(shuō)，這“基本上是最好的”。

一次一條路徑

Peng 說(shuō)，如此多的計(jì)算機(jī)科學(xué)家研究了最大流，以至于會(huì)議上談?wù)撨^(guò)去的工作看起來(lái)像是電影結(jié)束后的演職員表。但大多數(shù)人將第一個(gè)正式算法追溯到 1956 年，當(dāng)時(shí) Lester Ford 和 Delbert Fulkerson使用所謂的“貪婪”方法解決了最大流——這種方法在每一步都使用最容易獲得的對(duì)象。

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

接下來(lái)，算法會(huì)修改這些路段的容量以反映你現(xiàn)在已經(jīng)使用了它們的一些容量：它從路段的容量中減去你發(fā)送的卡車數(shù)量，因此五車道高速公路現(xiàn)在只有容量3、雙車道橋的通行能力為零。同時(shí)，該算法在這些高速公路的反向容量上增加了 2，因此如果我們?cè)敢猓覀兛梢栽谝院蟪废渲械囊恍┝髁俊?/span>

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

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

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

為了取得進(jìn)展，計(jì)算機(jī)科學(xué)家必須采取完全不同的方法。

從組合學(xué)到微積分

到目前為止，所有這些算法都采用了組合方法，它們?cè)诿恳徊街袑ふ夷撤N類型的結(jié)構(gòu)，并使用該結(jié)構(gòu)來(lái)更新流。但在 2003 年，南加州大學(xué)的 Spielman 和Chang-Hua Teng打開(kāi)了通往完全不同的“優(yōu)化”方法的大門，在這種方法中，使用微積分技術(shù)來(lái)引導(dǎo)你找到最優(yōu)解。

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

創(chuàng)建可以確定網(wǎng)絡(luò)最大流和最小成本的超快速算法的團(tuán)隊(duì)：（從左上角順時(shí)針?lè)较颍℡ang Liu、Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng 和 Sushant Sachdeva。

研究人員很快開(kāi)始探索如何將這一進(jìn)展應(yīng)用于最大流問(wèn)題。這個(gè)想法是將我們的高速公路網(wǎng)絡(luò)想象成一個(gè)電線網(wǎng)絡(luò)，并提高沒(méi)有太多可用容量的高速公路上的電阻，以阻止電子穿過(guò)它們。因?yàn)橛辛薙pielman和Teng，我們可以快速計(jì)算出通過(guò)這些電線的電流，它就會(huì)具有高速公路上車輛最大流的粗略屬性。（它們不會(huì)完全相同，因?yàn)殡娏鲉?wèn)題對(duì)電線的容量沒(méi)有任何硬性限制。）

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

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

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

最大流算法的最快可能運(yùn)行時(shí)間將只是 m 的倍數(shù)（即m^  1.0 ），因?yàn)閮H寫(xiě)下一個(gè)網(wǎng)絡(luò)就需要m步的倍數(shù)。這被稱為線性時(shí)間。但對(duì)許多研究人員來(lái)說(shuō)，如此快速的算法似乎是不可想象的。

“沒(méi)有充分的理由相信我們可以做到這一點(diǎn)，”Spielman說(shuō)。

簡(jiǎn)化，復(fù)用，循環(huán)

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

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

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

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

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

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

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

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

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

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

Rao 預(yù)測(cè)，該團(tuán)隊(duì)的分析冗長(zhǎng)而復(fù)雜，但其他研究人員很快就會(huì)投入其中以簡(jiǎn)化事情?！拔业母杏X(jué)是，在接下來(lái)的幾年里，一切都會(huì)變得更清潔、更好，”他說(shuō)。

Spielman說(shuō)，一旦算法得到簡(jiǎn)化，計(jì)算機(jī)科學(xué)家可能會(huì)開(kāi)始將其用作解決不同問(wèn)題的算法的子程序?！艾F(xiàn)在我們知道我們可以非?？斓刈龅竭@一點(diǎn)，人們會(huì)找到他們以前沒(méi)有想到的各種應(yīng)用?！?/span>

這種對(duì)最大流問(wèn)題的令人眼花繚亂的加速讓Spielman想知道算法理論中的其他核心問(wèn)題。“我們還能做什么？”

原文鏈接：

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