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

有多快？

對于任何類型的網絡，計算速度幾乎與數學理論一樣快。

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

圖片

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

圖片

其實早在兩年前，京爺團隊所做的“前代”研究就已經在圈內走紅，曾被Quanta Magazine評為當年的計算機科學十大發現之一。

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

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

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

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

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

蘇黎世聯邦理工學院官方給出的評價是：

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

那么京爺的團隊又是如何做到這一點的呢？

迄今最快的網絡流算法

網絡流，是圖論中的一種理論與方法，研究網絡上的一類最優化問題。

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

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

并且網絡流算法在解決現實問題時有很大的應用價值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖片

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

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

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

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

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

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

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

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

關于團隊

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

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

△Rasmus Kyng

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

△Maximilian Probst

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

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