最經典的算法問題之一是計算兩點之間的最短路徑。這個問題更復雜一點的版本是當路線穿過一個不斷變化的網絡時——無論是公路網還是互聯網。40年來，研究人員一直在尋找一種算法，為這個問題提供最佳解決方案。

當我們前往一個新的地方時，大多數人都會讓計算機算法幫助我們找到最佳路線，無論是通過汽車的GPS，還是公共交通工具和手機上的地圖應用程序。盡管如此，有時提議的路線與現實并不完全一致。這是因為道路網絡、公共交通網絡和其他網絡不是一成不變的。最好的路線可能突然變成最慢的路線，例如由于道路施工或事故導致大擁堵。

在這種情況下，一般人可能想不到導航建議背后的復雜數學問題。而正在使用的軟件則試圖解決經典算法“最短路徑”問題的一個變體，即動態網絡中的最短路徑。40年來，研究人員一直在尋找一種算法，以最優地解決這一數學難題?，F在，哥本哈根大學計算機科學系的克里斯蒂安·伍爾夫-尼爾森(Christian Wulff-Nilsen)與兩位同事成功地破解了這個難題。

“我們已經開發了一種算法，我們現在有數學證明，它比目前所有其他算法都要好——即使我們展望1000年后的未來，它也將是最接近最優算法?！蔽闋柗?尼爾森副教授說。研究結果FOCS 2020大會上公布。

在這種情況下，最優指在給定的網絡中花費盡可能少的時間和盡可能少的計算機內存來計算最佳路由的算法。這不僅適用于公路和交通網絡，也適用于互聯網或任何其他類型的網絡。

研究人員用所謂的動態圖來表示一個網絡。在這種情況下，圖是一個網絡的抽象表示，它由邊(例如道路)和節點(例如表示交叉點)組成。當一個圖形是動態的，這意味著它可以隨著時間而改變。新的算法處理由刪除的邊組成的變化——例如，如果等效的一段道路因道路施工而突然變得擁堵。

傳統的算法假設一個圖是靜態的，這在現實世界中很少是真的。當這類算法在動態網絡中使用時，每當圖中出現小的變化時，它們都需要重新運行——這浪費了時間。

克里斯蒂安·伍爾夫-尼爾森(Christian Wulff-Nilsen)指出:“我們生活在一個數據量以驚人的速度增長的時代，而硬件的發展根本跟不上。為了管理我們產生的所有數據，我們需要開發更智能的軟件，需要更少的運行時間和內存。這就是為什么我們需要更智能的算法?！?他希望在實踐中使用這種算法或其背后的一些技術是可能的，但他強調這是理論證據，首先需要實驗。

譯/前瞻經濟學人APP資訊組

參考資料：

https://techxplore.com/news/2021-03-classic-math-problem-scientists-superb.html

https://arxiv.org/abs/2004.04496



關注【深圳科普】微信公眾號，在對話框：
回復【最新活動】，了解近期科普活動
回復【科普行】，了解最新深圳科普行活動
回復【研學營】，了解最新科普研學營
回復【科普課堂】，了解最新科普課堂
回復【科普書籍】，了解最新科普書籍
回復【團體定制】，了解最新團體定制活動
回復【科普基地】，了解深圳科普基地詳情
回復【觀鳥知識】，學習觀鳥相關科普知識
回復【博物學院】，了解更多博物學院活動詳情