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

有多快？

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

而且還是以最低成本計算最大運輸流量的那種。

圖片

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

圖片

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

網(wǎng)絡流算法先驅Daniel A. Spielman也給出了相當高的評價：

快得離譜，像保時捷超跑一樣。

而就在最近，他們在ACM計算理論研討會（STOC）中帶來了“進化版”研究——

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

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

蘇黎世聯(lián)邦理工學院官方給出的評價是：

超快算法為未來高效計算超大型動態(tài)變化的網(wǎng)絡奠定了基礎，有望改變整個研究領域。

那么京爺?shù)膱F隊又是如何做到這一點的呢？

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

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

這個問題早在1955年，由T.E.哈里斯在研究鐵路最大通量時，為了尋求兩點間最大運輸量而被提出。

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

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

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

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

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

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

但京爺團隊所提出的算法，就一舉打破了這一局面——

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

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

在京爺團隊之前，研究人員傾向于在兩種關鍵策略之間做選擇：

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

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

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

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

最新的這項研究，提出了一系列針對增量圖（incremental graphs）問題的幾乎線性時間算法。

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

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

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

圖片

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

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

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

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

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

更深層一些的，它們還改變了計算機計算復雜任務的方式。

正如加州大學伯克利分校的一個國際研究小組所評價的那般：

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

關于團隊

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

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

△Rasmus Kyng

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

△Maximilian Probst

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

若是對這項研究感興趣，可戳下方鏈接進一步了解。