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

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

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

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

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

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

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

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

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

參考資料：

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

https://arxiv.org/abs/2004.04496



關(guan) 注【深圳科普】微信公眾(zhong) 號，在對話框：
回複【最新活動】，了解近期科普活動
回複【科普行】，了解最新深圳科普行活動
回複【研學營】，了解最新科普研學營
回複【科普課堂】，了解最新科普課堂
回複【科普書(shu) 籍】，了解最新科普書(shu) 籍
回複【團體(ti) 定製】，了解最新團體(ti) 定製活動
回複【科普基地】，了解深圳科普基地詳情
回複【觀鳥星空体育官网入口网站】，學習(xi) 觀鳥相關(guan) 科普星空体育官网入口网站
回複【博物學院】，了解更多博物學院活動詳情