最經(jīng)典的算法問題之一是計(jì)算兩點(diǎn)之間的最短路徑。這個(gè)問題更復(fù)雜一點(diǎn)的版本是當(dāng)路線穿過一個(gè)不斷變化的網(wǎng)絡(luò)時(shí)——無論是公路網(wǎng)還是互聯(lián)網(wǎng)。40年來，研究人員一直在尋找一種算法，為這個(gè)問題提供最佳解決方案。

當(dāng)我們前往一個(gè)新的地方時(shí)，大多數(shù)人都會(huì)讓計(jì)算機(jī)算法幫助我們找到最佳路線，無論是通過汽車的GPS，還是公共交通工具和手機(jī)上的地圖應(yīng)用程序。盡管如此，有時(shí)提議的路線與現(xiàn)實(shí)并不完全一致。這是因?yàn)榈缆肪W(wǎng)絡(luò)、公共交通網(wǎng)絡(luò)和其他網(wǎng)絡(luò)不是一成不變的。最好的路線可能突然變成最慢的路線，例如由于道路施工或事故導(dǎo)致大擁堵。

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

“我們已經(jīng)開發(fā)了一種算法，我們現(xiàn)在有數(shù)學(xué)證明，它比目前所有其他算法都要好——即使我們展望1000年后的未來，它也將是最接近最優(yōu)算法。”伍爾夫-尼爾森副教授說。研究結(jié)果FOCS 2020大會(huì)上公布。

在這種情況下，最優(yōu)指在給定的網(wǎng)絡(luò)中花費(fèi)盡可能少的時(shí)間和盡可能少的計(jì)算機(jī)內(nèi)存來計(jì)算最佳路由的算法。這不僅適用于公路和交通網(wǎng)絡(luò)，也適用于互聯(lián)網(wǎng)或任何其他類型的網(wǎng)絡(luò)。

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

傳統(tǒng)的算法假設(shè)一個(gè)圖是靜態(tài)的，這在現(xiàn)實(shí)世界中很少是真的。當(dāng)這類算法在動(dòng)態(tài)網(wǎng)絡(luò)中使用時(shí)，每當(dāng)圖中出現(xiàn)小的變化時(shí)，它們都需要重新運(yùn)行——這浪費(fèi)了時(shí)間。

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

譯/前瞻經(jīng)濟(jì)學(xué)人APP資訊組

參考資料：

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

https://arxiv.org/abs/2004.04496



關(guān)注【深圳科普】微信公眾號(hào)，在對話框：
回復(fù)【最新活動(dòng)】，了解近期科普活動(dòng)
回復(fù)【科普行】，了解最新深圳科普行活動(dòng)
回復(fù)【研學(xué)營】，了解最新科普研學(xué)營
回復(fù)【科普課堂】，了解最新科普課堂
回復(fù)【科普書籍】，了解最新科普書籍
回復(fù)【團(tuán)體定制】，了解最新團(tuán)體定制活動(dòng)
回復(fù)【科普基地】，了解深圳科普基地詳情
回復(fù)【觀鳥知識(shí)】，學(xué)習(xí)觀鳥相關(guān)科普知識(shí)
回復(fù)【博物學(xué)院】，了解更多博物學(xué)院活動(dòng)詳情