計(jì)算機(jī)基礎(chǔ)問(wèn)題，最大流問(wèn)題獲突破性進(jìn)展：新算法「快得離譜」

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

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

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

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

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