北京
一個(gè)用了41年的算法，被一群清華人給破了。
從1984年到現(xiàn)在，Dijkstra算法一直是計(jì)算最短路徑的"標(biāo)準(zhǔn)答案"。你每天用的Google Maps導(dǎo)航、外賣平臺(tái)的路徑規(guī)劃、物流系統(tǒng)的配送路線，底層都是它在支撐。
但問題是，這個(gè)算法有個(gè)理論上的天花板。去年，算法界的傳奇人物Robert Tarjan還專門拿了個(gè)獎(jiǎng)，證明Dijkstra在數(shù)學(xué)上已經(jīng)是理論最優(yōu)，沒法再快了。
全世界最聰明的幾顆腦袋，都默認(rèn)這道"排序屏障"繞不過去。
清華團(tuán)隊(duì)換了個(gè)思路：找最短路徑，干嘛非要把所有點(diǎn)都排個(gè)序？
他們把Bellman-Ford的邏輯和遞歸部分排序的方法拼在一起，搞出了一個(gè)新算法，復(fù)雜度降到了O(m log^{2/3} n)。
官方意義上，確實(shí)比Dijkstra更快。
放在小圖里，你感覺不到差別。但在網(wǎng)頁(yè)級(jí)別的超大規(guī)模圖、全球物流網(wǎng)絡(luò)這種場(chǎng)景下，這個(gè)差距是真實(shí)存在的。
明天早上你的GPS導(dǎo)航不會(huì)突然變快，但整個(gè)最短路徑問題的底層邏輯，已經(jīng)在很多領(lǐng)域發(fā)生了根本性的變化。
這件事的意義不在于"快了多少"，而在于證明了一件事：那些被認(rèn)為"不可能突破"的理論邊界，可能只是因?yàn)榇蠹乙恢痹谕粭l路上走。
換個(gè)方向，路就出來了。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
林子說事
