那個比影子還快的人——拉斯穆斯·金和他的團隊開發了一種超快算法，看起來將改變整個研究領域。金團隊的開創性工作涉及所謂的網絡流算法，該算法解決了如何在網絡中實現最大流量同時最小化傳輸成本的問題。

想象一下，您正在使用歐洲交通網絡，并尋找最快、最便宜的路線，以便將盡可能多的貨物從哥本哈根運送到米蘭。在這種情況下，Kyng 的算法可以用于計算任何類型網絡(無論是鐵路、公路、水路還是互聯網)的最佳、成本最低的交通流量。他的算法執行這些計算的速度非?？?，以至于它可以在計算機讀取描述網絡的數據時提供解決方案。

網絡計算速度很快

在 Kyng 之前，沒有人能夠做到這一點——盡管研究人員已經研究這個問題大約 90 年了。以前，計算最佳流量所花的時間比處理網絡數據所花的時間要長得多。隨著網絡變得越來越大、越來越復雜，所需的計算時間相對而言比計算問題的實際規模增長得更快。這就是為什么我們也看到網絡中的流量問題太大而計算機甚至無法計算的原因。

Kyng 的方法消除了這個問題：使用他的算法，計算時間和網絡規模以相同的速率增加——有點像徒步旅行，無論路有多陡峭，都始終保持相同的步伐?？匆幌略紨祿湍苤牢覀円呀浫〉昧硕啻蟮倪M步：直到 2000 年，還沒有一種算法的計算速度能超過 m 1.5，其中 m 代表計算機需要計算的網絡中的連接數，僅僅讀取一次網絡數據就需要 m 時間。2004 年，解決問題所需的計算速度成功降低到 m 1.33。使用 Kyng 的算法，讀取網絡數據后得出解決方案所需的“額外”計算時間現在可以忽略不計。

就像保時捷和馬車賽跑一樣

蘇黎世聯邦理工學院的研究人員由此開發出了理論上最快的網絡流算法。兩年前，Kyng 和他的團隊在一篇開創性的論文中展示了他們概念的數學證明?？茖W家將這些新穎的、幾乎最佳的快速算法稱為“近乎線性時間算法”，理論計算機科學家社區對 Kyng 的突破既驚訝又熱情。

Kyng 的博士生導師、耶魯大學應用數學和計算機科學教授 Daniel A. Spielman 本人也是該領域的先驅和資深人士，他將這種“快得離譜”的算法比作保時捷超越馬車。他們的論文不僅獲得了 IEEE 計算機科學基礎年度研討會 (FOCS) 2022 年最佳論文獎，還在 ACM 的計算期刊《通訊》上重點介紹，科普雜志《Quanta》的編輯 將 Kyng 的算法評為2022 年計算機科學十大發現 之一 。

蘇黎世聯邦理工學院的研究人員此后改進了他們的方法，并開發了進一步的近線性時間算法。例如，第一個算法仍然專注于固定的靜態網絡，這些網絡的連接是定向的，這意味著它們就像城市道路網絡中的單行道一樣。今年發布的算法現在還能夠計算隨時間逐步變化的網絡的最佳流量。閃電般的快速計算是解決高度復雜且數據豐富的網絡的重要一步，這些網絡會動態且非?？焖俚刈兓?，例如生物學中的分子或大腦，或人類的友誼。

用于改變網絡的閃電般快速的算法

周四，Kyng 團隊的一名成員 Simon Meierhans 在溫哥華舉行的 ACM 計算理論年度研討會 (STOC) 上介紹了一種新的近乎線性時間算法。該算法解決了隨著新連接的增加而逐漸變化的網絡的最小成本最大流問題。此外，在 10 月份被 IEEE 計算機科學基礎研討會 (FOCS) 接受的第二篇論文中，ETH 研究人員開發了另一種算法，該算法也處理被移除的連接。

具體來說，這些算法會在添加或刪除連接時識別出最短路線。在現實世界的交通網絡中，瑞士此類變化的例子包括自 2023 年夏季以來幾個月內圣哥達基線隧道完全關閉，然后部分重新開放，或者最近發生的山體滑坡摧毀了 A13 高速公路的部分路段，而 A13 高速公路是圣哥達公路隧道的主要替代路線。

面對這樣的變化，計算機、在線地圖服務或路線規劃器如何計算米蘭和哥本哈根之間成本最低、速度最快的連接?Kyng 的新算法還能在近乎線性的時間內為這些不斷增加或減少變化的網絡計算出最佳路線——速度如此之快，以至于每個新連接的計算時間(無論是通過重新路由還是創建新路線而增加)都可以忽略不計。

但究竟是什么使得 Kyng 的計算方法比其他任何網絡流算法都快得多呢?原則上，所有計算方法都面臨著這樣的挑戰：必須多次迭代分析網絡，才能找到最佳流量和最低成本路線。在此過程中，它們會逐一分析哪些連接是開放的、關閉的或由于達到容量極限而擁塞的。

計算整體?還是部分?

在 Kyng 之前，計算機科學家傾向于在兩種關鍵策略之間做出選擇來解決此問題。其中一種策略以鐵路網絡為模型，涉及在每次迭代中計算整個網絡部分，并修改交通流量。第二種策略——受電網中的電力流啟發——在每次迭代中計算整個網絡，但對網絡每個部分的修改流量使用統計平均值，以加快計算速度。

Kyng 的團隊現在將這兩種策略各自的優勢結合在一起，以創建一種全新的組合方法。“我們的方法基于許多小的、高效的和低成本的計算步驟，這些步驟加在一起比幾個大步驟要快得多，”Kyng 團隊的講師兼成員 Maximilian Probst Gutenberg 說，他在開發近乎線性時間的算法中發揮了關鍵作用。

簡單回顧一下這門學科的歷史，可以為 Kyng 的突破增添另一個意義：網絡中的流問題是 20 世紀 50 年代借助算法系統解決的第一批問題之一，流算法在理論計算機科學成為一門獨立的研究領域方面發揮了重要作用。數學家 Lester R. Ford Jr. 和 Delbert R. Fulkerson 開發的著名算法也源于這一時期。他們的算法有效地解決了最大流問題，該問題旨在確定如何在不超過各個路線容量的情況下通過網絡運輸盡可能多的貨物。