迄今最快的網(wǎng)絡(luò)流算法，網(wǎng)友：幾乎與數(shù)學(xué)理論一樣快

十三 2024-06-30 14:00:04 來源：量子位

金磊 發(fā)自 凹非寺

量子位 | 公眾號(hào) QbitAI

迄今為止最快、近乎完美的網(wǎng)絡(luò)流（Network Flow）算法，來了！

有多快？

對(duì)于任何類型的網(wǎng)絡(luò)，計(jì)算速度幾乎與數(shù)學(xué)理論一樣快。

而且還是以最低成本計(jì)算最大運(yùn)輸流量的那種。

這就是來自蘇黎世聯(lián)邦理工學(xué)院計(jì)算機(jī)系Rasmus Kyng（下文簡(jiǎn)稱“京爺”）團(tuán)隊(duì)最新研究：

其實(shí)早在兩年前，京爺團(tuán)隊(duì)所做的“前代”研究就已經(jīng)在圈內(nèi)走紅，曾被Quanta Magazine評(píng)為當(dāng)年的計(jì)算機(jī)科學(xué)十大發(fā)現(xiàn)之一。

網(wǎng)絡(luò)流算法先驅(qū)Daniel A. Spielman也給出了相當(dāng)高的評(píng)價(jià)：

快得離譜，像保時(shí)捷超跑一樣。

而就在最近，他們?cè)贏CM計(jì)算理論研討會(huì)（STOC）中帶來了“進(jìn)化版”研究——

不論是網(wǎng)絡(luò)里增加或刪除了什么路徑，依舊能夠以最低成本、最大傳輸流量的“姿勢(shì)”，用幾乎線性的速度進(jìn)行計(jì)算。

就好比徒步旅行一樣，管你道路變多了還是變陡峭了，我依舊保持高速前行、順利抵達(dá)終點(diǎn)。

蘇黎世聯(lián)邦理工學(xué)院官方給出的評(píng)價(jià)是：

超快算法為未來高效計(jì)算超大型動(dòng)態(tài)變化的網(wǎng)絡(luò)奠定了基礎(chǔ)，有望改變整個(gè)研究領(lǐng)域。

那么京爺?shù)膱F(tuán)隊(duì)又是如何做到這一點(diǎn)的呢？

迄今最快的網(wǎng)絡(luò)流算法

網(wǎng)絡(luò)流，是圖論中的一種理論與方法，研究網(wǎng)絡(luò)上的一類最優(yōu)化問題。

這個(gè)問題早在1955年，由T.E.哈里斯在研究鐵路最大通量時(shí)，為了尋求兩點(diǎn)間最大運(yùn)輸量而被提出。

在1956年，L.R.福特和D.R.富爾克森等人給出了解決這類問題的算法，從而建立了網(wǎng)絡(luò)流理論。

并且網(wǎng)絡(luò)流算法在解決現(xiàn)實(shí)問題時(shí)有很大的應(yīng)用價(jià)值。

例如你在使用歐洲運(yùn)輸網(wǎng)絡(luò)的時(shí)候，希望尋找最快、最便宜的路線，將盡可能多的貨物從哥本哈根運(yùn)送到米蘭，這時(shí)候網(wǎng)絡(luò)流算法就能發(fā)揮作用了。

對(duì)于這個(gè)問題，以前計(jì)算最佳流量所需的時(shí)間甚至比處理網(wǎng)絡(luò)數(shù)據(jù)的時(shí)間要長(zhǎng)得多。

而隨著網(wǎng)絡(luò)變得越來越大，越來越復(fù)雜，相對(duì)而言，所需的計(jì)算時(shí)間比計(jì)算問題的實(shí)際規(guī)模增長(zhǎng)得快得多。

這也就是為什么我們還能看到計(jì)算機(jī)有時(shí)都無法對(duì)網(wǎng)絡(luò)中的流量進(jìn)行計(jì)算的原因。

但京爺團(tuán)隊(duì)所提出的算法，就一舉打破了這一局面——

不僅讀取網(wǎng)絡(luò)數(shù)據(jù)到解決方案所需的“額外”計(jì)算時(shí)間現(xiàn)在可以忽略不計(jì)，即便是重新設(shè)計(jì)路由（Route）還是添加新路由，都可以忽略不計(jì)。

原則上，所有計(jì)算方法都面臨著必須多次迭代分析網(wǎng)絡(luò)的挑戰(zhàn)，以此來找到最佳流量和最低成本路線。

在京爺團(tuán)隊(duì)之前，研究人員傾向于在兩種關(guān)鍵策略之間做選擇：

• 一種方法是以鐵路網(wǎng)絡(luò)為模型，在每次迭代中對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行計(jì)算，并對(duì)交通流量進(jìn)行修改。
• 另一種方法則是受電網(wǎng)中電力流的啟發(fā)，在每次迭代中計(jì)算整個(gè)網(wǎng)絡(luò)，但對(duì)網(wǎng)絡(luò)每個(gè)部分的修改流量使用統(tǒng)計(jì)平均值。

京爺團(tuán)隊(duì)的做法則是——成年人不做選擇題，二者的優(yōu)勢(shì)統(tǒng)統(tǒng)都要，組合打造新方法：

我們的方法基于許多小的、高效的和低成本的計(jì)算步驟，這些步驟加在一起比幾個(gè)大的計(jì)算步驟要快得多。

這在開發(fā)幾乎線性時(shí)間算法方面發(fā)揮了關(guān)鍵作用。

最新的這項(xiàng)研究，提出了一系列針對(duì)增量圖（incremental graphs）問題的幾乎線性時(shí)間算法。

（增量圖指的是隨時(shí)間變化而動(dòng)態(tài)變化的有向圖，主要通過邊的插入操作來改變。）

論文中提出的算法主要解決以下幾個(gè)問題：

• 環(huán)檢測(cè)（Cycle Detection）：檢測(cè)圖中是否存在環(huán)。
• 強(qiáng)連通分量維護(hù)（Strongly Connected Component Maintenance, SCCs）：維護(hù)圖中的強(qiáng)連通分量。
• 單源最短路徑（s-t Shortest Path）：計(jì)算圖中單源到單目標(biāo)的最短路徑。
• 最小成本流（Minimum-Cost Flow）：在滿足容量限制的情況下，找到成本最小的流。

論文的主要技術(shù)貢獻(xiàn)是提出了一種確定性數(shù)據(jù)結(jié)構(gòu)，能夠在完全動(dòng)態(tài)圖中，對(duì)于每次更新，以攤銷的幾乎線性時(shí)間返回一個(gè)近似最小比率環(huán)。

結(jié)合Brand-Liu-Sidford（STOC 2023）的內(nèi)點(diǎn)方法框架，論文給出了第一個(gè)決定增量圖中最小成本流達(dá)到給定閾值的算法。

除此之外，團(tuán)隊(duì)還使用和設(shè)計(jì)了新的數(shù)學(xué)工具，進(jìn)一步加快了他們的算法速度。

結(jié)果顯示，論文的算法在理論上提供了對(duì)增量圖問題的有效解決方案，這些算法在時(shí)間復(fù)雜度上顯著優(yōu)于以往的算法。

然而，像京爺團(tuán)隊(duì)這種為解決以前無法有效計(jì)算的非常大規(guī)模問題奠定的基礎(chǔ)，也還只是這些顯著更快的網(wǎng)絡(luò)流算法的影響之一。

更深層一些的，它們還改變了計(jì)算機(jī)計(jì)算復(fù)雜任務(wù)的方式。

正如加州大學(xué)伯克利分校的一個(gè)國(guó)際研究小組所評(píng)價(jià)的那般：

在過去的十年里，在理論計(jì)算機(jī)科學(xué)的基礎(chǔ)問題上，為了獲得可證明的快速算法，在理論基礎(chǔ)上發(fā)生了一場(chǎng)革命。

關(guān)于團(tuán)隊(duì)

這項(xiàng)研究有三位來自蘇黎世聯(lián)邦理工學(xué)院的作者。

其中的京爺，Rasmus Kyng是蘇黎世聯(lián)邦理工學(xué)院計(jì)算機(jī)科學(xué)系的助理教授，研究重點(diǎn)是圖問題和凸優(yōu)化的快速算法、概率和差異理論、細(xì)粒度復(fù)雜性理論以及機(jī)器學(xué)習(xí)中的應(yīng)用。

△Rasmus Kyng

另外一位研究貢的主要獻(xiàn)者是Maximilian Probst博士，他是京爺小組的高級(jí)助理，主攻方向是圖算法、優(yōu)化和數(shù)據(jù)結(jié)構(gòu)。

△Maximilian Probst

除此之外，這項(xiàng)研究中還有兩位華人作者，他們分別是來自CMU的Li Chen，以及普林斯頓的Yang P. Liu。

若是對(duì)這項(xiàng)研究感興趣，可戳下方鏈接進(jìn)一步了解。

參考鏈接：
[1]https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html
[2]https://dl.acm.org/doi/10.1145/3618260.3649745
[3]https://news.ycombinator.com/item?id=40829459
[4]https://inf.ethz.ch/news-and-events/spotlights/infk-news-channel/2023/07/frontiers-of-science-awards-for-rasmus-kyng-and-maximilian-probst.html