計算機(jī)科學(xué)家組成的科研團(tuán)隊，為計算機(jī)領(lǐng)域中經(jīng)典的最大流問題提出了一種速度極快的算法。最大流問題是一種組合最優(yōu)化問題，討論如何充分利用裝置的能力，使得運(yùn)輸?shù)牧髁孔畲笠匀〉米詈玫男Ч?/blockquote>

這個問題在網(wǎng)絡(luò)流理論中非?；A(chǔ)?！感滤惴斓碾x譜。其實(shí)，我本來堅信這個問題不可能存在這么高效的算法，」來自耶魯大學(xué)的 Daniel Spielman 說道。
自 20 世紀(jì) 50 年代以來，人們一直在研究最大流量，當(dāng)時研究最大流是為了建模研究前蘇聯(lián)鐵路系統(tǒng)。 「對它的研究甚至比計算機(jī)科學(xué)理論還古老，」來自谷歌加州山景城研究中心的 Edith Cohen 這樣說。
這個問題通向很多應(yīng)用：互聯(lián)網(wǎng)數(shù)據(jù)流、航空公司日程安排，甚至包含將求職者與空缺職位進(jìn)行匹配。這篇新論文既處理了最大流量問題，也處理了更一般的問題，即處理最大流同時還希望最小化成本。多年來，這兩個問題激發(fā)了算法技術(shù)的許多重大進(jìn)步。Spielman 說：“這幾乎就是我們一直耕耘算法領(lǐng)域的原因?！?/span>
新算法在「近似線性」的時間內(nèi)解決了這兩個問題，就是說該算法的運(yùn)行時間基本與記錄網(wǎng)絡(luò)細(xì)節(jié)所需的時間正比。對于所有可能的網(wǎng)絡(luò)，解決這些問題的其他算法都無法達(dá)到如此快的速度。加州大學(xué)伯克利分校的 Satish Rao 表示，這個結(jié)果讓他跳了起來：「簡直太棒了?！?/span>
Spielman 則認(rèn)為，我們已經(jīng)找到如此快的算法，現(xiàn)在是時候著手思考解決之前沒有想過的各種應(yīng)用問題了。
目前，新方法主要是理論上的提升，因?yàn)樗惴ㄋ俣鹊奶嵘€只適用于比現(xiàn)實(shí)世界中遇到的大得多的網(wǎng)絡(luò)，對于這些網(wǎng)絡(luò)，最大流量問題已經(jīng)可以很快地得到答案（至少在不考慮代價最小化的情況下）。加拿大滑鐵盧大學(xué)的 Richard Peng 預(yù)計，新算法可能在一年內(nèi)得到實(shí)際應(yīng)用，他是該算法的六位創(chuàng)造者之一。
有研究人員認(rèn)為，在未來幾年里，計算機(jī)科學(xué)家可能會找到方法使其更實(shí)用，甚至可能更快。
麻省理工學(xué)院的 Aleksander M?dry 說，未來即使有所改進(jìn)，但這篇新論文也是「扣籃大賽中最精彩的扣籃」。他說，這基本上是最好的」。
一次一條路徑
Richard Peng 表示，很多計算機(jī)科學(xué)家在研究最大流問題，以至于在會議上討論過去的工作就像過電影最后的鳴謝部分。但大多數(shù)人都同意第一個形式化算法是 1956 年由 Lester Ford 和 Delbert Fulkerson 應(yīng)用貪心算法求解最大流，這種方法在每一步都使用最容易得到的對象。
你可以這樣理解這種方法：首先，設(shè)想一個高速公路網(wǎng)絡(luò)，你希望在給定的時間內(nèi)將盡可能多的送貨卡車從洛杉磯運(yùn)送到紐約市。Ford 和 Fulkerson 的算法從選擇從洛杉磯到紐約的一條路徑開始，并沿著這條路徑安排盡可能多的卡車。該方法通常不會利用該特定道路上所有道路的全部通行能力：如果道路的是五車道公路，但它通過一架兩車道的橋梁，那么你在任何時候都只能啟動兩輛卡車。
接下來，該算法修改這些路段的通行能力，以反映現(xiàn)在使用了部分路段的通行能力：它從路段的通行能力中減去發(fā)送的卡車數(shù)量，因此五車道公路現(xiàn)在通行能力是 3，而雙車道橋的通行能力為零。同時，該算法在反向方向上為這些公路的通行能力增加了 2，因此，如果我們愿意，我們可以稍后撤銷部分流量。
然后，該算法找到一條從洛杉磯到紐約的新路徑，該路徑可以容納一些卡車，沿著該路徑發(fā)送盡可能多的卡車，并再次更新容量。經(jīng)過有限數(shù)量的這些步驟后，從洛杉磯到紐約的道路將無法容納更多的卡車，到這里算法就完成了：我們只要將構(gòu)建的所有流量合并，就可以通過獲得網(wǎng)絡(luò)最大可能的流量。

Ford 和 Fulkerson 的算法并不試圖在這一過程中做出聰明的選擇。如果它選擇了一條切斷其他有用路徑的路徑，那是算法之后要處理的問題。在該算法發(fā)表后的幾十年里，研究人員試圖通過讓算法做出更明智的選擇來加速運(yùn)行時間，例如總是使用最短的可用路徑或可用容量最大的路徑。 1970 年，Yefim Dinitz 發(fā)現(xiàn)了一種在一步中使用網(wǎng)絡(luò)中所有最短路徑的有效方法。這一算法在低容量網(wǎng)絡(luò)中的運(yùn)行時間，由 Shimon Even 和 Robert Tarjan 證明為 m^1.5 (m: 網(wǎng)絡(luò)中的鏈接數(shù)，相比之下，F(xiàn)ord-Fulkerson 算法在低容量網(wǎng)絡(luò)中需要多個 m^2）。
近 30 年后，Rao 和 Andrew Goldberg 對高容量網(wǎng)絡(luò)得出了類似的結(jié)果。但沒有人能擊敗 m^1.5 指數(shù)。這篇新論文的作者之一、多倫多大學(xué)的蘇珊特?薩赫德瓦（SushantSachdeva）說：「進(jìn)入 21 世紀(jì)……m^1.5 的壁壘根深蒂固?！篂榱巳〉酶筮M(jìn)展，計算機(jī)科學(xué)家必須尋找完全不同的方法。
從組合到微積分
到目前為止，所有這些算法都采用了組合方法，即在每個步驟中尋找某種類型的結(jié)構(gòu)，并使用該結(jié)構(gòu)來更新流。但在 2003 年，南加州大學(xué)的 Spielman 和 ShangHua Teng 開啟了一扇完全不同的「優(yōu)化」方法之門，在這種方法中，使用微積分技術(shù)為指導(dǎo)尋找最優(yōu)解。
Spielman 和 Teng 開發(fā)了一種快速優(yōu)化算法，該算法解決的不是最大流量問題，而是一個密切相關(guān)的問題，即通過每根具有給定電阻的導(dǎo)線網(wǎng)絡(luò)找到能量最低的電流。Sachdeva 說，Spielman 和 Teng 的進(jìn)步是「關(guān)鍵時刻」。

創(chuàng)建確定網(wǎng)絡(luò)最大流量和最小成本的超快速算法團(tuán)隊成員 (從左上角順時針開始):Yang Liu、 Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng、Sushant Sachdeva。
研究人員很快開始探索如何將這一進(jìn)展應(yīng)用于最大流問題?？梢园压肪W(wǎng)想象成由電線組成的網(wǎng)絡(luò)，在沒有太多可用容量的公路上增加電阻，阻止電子穿過公路。由于 Spielman 和 Teng 的工作，我們可以快速計算通過這些電線的電流，這個模型具有通過高速公路的最大車輛流量的粗略屬性。（它們不會完全相同，因?yàn)殡娏鲉栴}對導(dǎo)線的容量沒有任何硬性限制。）
然后，在產(chǎn)生了這個初始流量之后，我們可以像 Ford 和 Fulkerson 的組合算法一樣重新調(diào)整容量。接下來，可以重置每條導(dǎo)線的電阻，以反映這些變化的量，并解決新生成的電路問題。
與一次改變一個網(wǎng)絡(luò)塊的組合方法不同，Spielman 和 Teng 的優(yōu)化方法每次完成整個網(wǎng)絡(luò)的掃描。這使得每一步都更加有效，因此達(dá)到最大值需要的總步驟更少。2008 年，谷歌的 Samuel Daitch 和 Spielman 使用了這種方法，基本上與之前的最大流量 m^1.5 的界限相近。在 2013 年，M?dry 進(jìn)一步推進(jìn)了該方法，以突破低容量網(wǎng)絡(luò)的 m^1.5，將運(yùn)行時間提高到大約 m^1.43 的倍數(shù)?！高@太令人震驚了，」Rao 表示。
接下來的幾年里，研究人員進(jìn)一步擴(kuò)展了這種方法，但他們的結(jié)果仍停留在 m^1.33。他們開始懷疑這個指數(shù)是否是一個基本極限。
對于最大流算法來說，最快的可想象運(yùn)行時間應(yīng)該是 m 倍（即 m^1.0），因?yàn)閷懴乱粋€網(wǎng)絡(luò)需要 m 個步驟的倍數(shù)。這被稱為線性時間。但對許多研究人員來說，這樣一個極快的算法似乎是不可想象的?！笡]有任何充分的理由，能讓我們相信能做到這一點(diǎn)，」Spielman 說到。
縮小、重用、回收
這篇新論文的作者認(rèn)為，Daitch 和 Spielman 的方法有更多的優(yōu)點(diǎn)。M?dry 曾用它來減少解決最大流問題所需的步驟數(shù)，但這種減少是有代價的：在每一步中，整個網(wǎng)絡(luò)都必須重寫，并且必須從頭開始解決電力流問題。
這種方法將 Spielman 和 Teng 的算法視為黑盒 —— 不管算法內(nèi)部在做什么。六位研究人員決定深入研究該算法的核心，并根據(jù)最大流量問題調(diào)整其各個組成部分。他們懷疑，這些組件甚至可能讓他們解決更難的「最低成本問題，在這個問題是尋找最便宜的方式來運(yùn)輸給定數(shù)量的材料。計算機(jī)科學(xué)家早就知道，任何最小成本算法都可以解決最大流問題。
與其他優(yōu)化方法一樣，研究人員提出了流的「能量」概念即鏈接成本和容量的函數(shù)。將流量從昂貴的低容量鏈路轉(zhuǎn)移到廉價的高容量鏈路會降低系統(tǒng)的總能量。
為了弄清楚如何快速地將流移向低能狀態(tài)，研究人員將這種優(yōu)化方法與舊的組合觀點(diǎn)相結(jié)合。后者一次只更改網(wǎng)絡(luò)的一部分，提供了重用前面步驟中的一些工作的可能性。
在每一步中，算法都會尋找一個可以減少能量的循環(huán)，即開始和結(jié)束是同一個點(diǎn)的路徑?；鞠敕ê芎唵危杭僭O(shè)你創(chuàng)建了一條從芝加哥到紐約的收費(fèi)公路，然后你發(fā)現(xiàn)有一條更便宜的高速公路。這時把紐約添加進(jìn)循環(huán)，沿著昂貴的道路運(yùn)行到芝加哥，然后沿著較便宜的路線返回，形成一個循環(huán)，從而替換掉昂貴的路徑，從而降低了流量的總成本。
加拿大維多利亞大學(xué)的 Valerie King 說，這種方法使用的步驟比「電氣方法」多得多，所以乍一看聽起來「像是在倒退」。為了進(jìn)行補(bǔ)償，算法必須在每一步都以難以置信的速度找到優(yōu)質(zhì)的循環(huán)，比檢查整個網(wǎng)絡(luò)所需的速度還要快。
這就是 Spielman 和 Teng 的算法的工作原理。他們的算法提供了一種使用「低延伸生成樹」的新方法，這種樹是算法的關(guān)鍵，它可以捕獲網(wǎng)絡(luò)的許多最顯著的特征。給定這樣一個樹，通過在樹外添加一個鏈接，總是可以構(gòu)建至少一個良好的循環(huán)。因此，擁有一個低伸縮的生成樹可以大大減少需要考慮的循環(huán)數(shù)。
即便如此，為了讓算法快速運(yùn)行，團(tuán)隊也無法在每一步都構(gòu)建一個全新的生成樹。相反，他們必須確保每個新周期在生成樹中只產(chǎn)生較小的漣漪效應(yīng)，以便重用以前的大部分計算。該論文作者之一、斯坦福大學(xué)研究生 Yang Liu 表示，實(shí)現(xiàn)這種控制水平是「核心難點(diǎn)」。
最終，研究人員創(chuàng)建了一種在「幾乎線性」時間內(nèi)運(yùn)行的算法，這意味著當(dāng)用越大的網(wǎng)絡(luò)時，它的運(yùn)行時間越接近 m。
該算法借鑒了 Spielman 和 Teng 的許多想法，并將它們結(jié)合在一起，形成了一種全新的東西。Spielman 說，如果你只見過馬拉的車，那么現(xiàn)在的算法就像是汽車?！肝铱吹剿幸粋€可以坐的地方，我看到它有輪子，我看到它有東西可以讓它移動。但他們已經(jīng)用發(fā)動機(jī)代替了馬?！?/span>
Rao 推測，該團(tuán)隊的分析是漫長而復(fù)雜的，但其他研究人員很快就會深入研究以簡化問題。他說：「我的感覺是，未來幾年，一切都會變得更干凈、更好?！?/span>
Spielman 說，一旦算法得到簡化，計算機(jī)科學(xué)家可能會開始將其用作解決不同問題的算法的子程序。「現(xiàn)在我們知道我們可以很快做到這一點(diǎn)，人們會發(fā)現(xiàn)各種各樣的應(yīng)用程序，這是他們以前沒有想過。」
另外，該算法對最大流問題令人眩暈的加速，讓 Spielman 對算法理論中的其他核心問題有了期待，「我們還能做些什么？」
原文鏈接：https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/

*博客內(nèi)容為網(wǎng)友個人發(fā)布，僅代表博主個人觀點(diǎn)，如有侵權(quán)請聯(lián)系工作人員刪除。