頂會(huì)最佳論文覆滅科學(xué)家們30多年期待：復(fù)雜度遠(yuǎn)超預(yù)期

AIGC動(dòng)態(tài)歡迎閱讀

原標(biāo)題：頂會(huì)最佳論文覆滅科學(xué)家們30多年期待：復(fù)雜度遠(yuǎn)超預(yù)期

關(guān)鍵字：算法,度量,消耗,空間,路徑

文章來源：量子位

內(nèi)容字?jǐn)?shù)：5953字

內(nèi)容摘要：克雷西 發(fā)自 凹非寺量子位 | 公眾號(hào) QbitAI三十多年來，在線算法一直被科學(xué)家寄予厚望，但一篇論文的誕生讓它走下了神壇。它的目標(biāo)，簡(jiǎn)單來說就是在沒有完整數(shù)據(jù)的情況下，通過有限的信息提前找到最佳策略。在我們的生活中，例如股票市場(chǎng)的即時(shí)交易分析，還有導(dǎo)航路徑的實(shí)時(shí)規(guī)劃，都有在線算法的身影。不過沒有完整數(shù)據(jù)，就意味著性能將受到限制；因此科學(xué)家們一直期待它能突破數(shù)據(jù)的桎梏，達(dá)到更高的效率。然而就在最近，來自微軟研究院、牛津大學(xué)等機(jī)構(gòu)的研究人員在進(jìn)行了一場(chǎng)實(shí)驗(yàn)之后發(fā)現(xiàn)，這種算法的復(fù)雜度遠(yuǎn)遠(yuǎn)超過了人們的期待。他們也憑借著這篇論文，在今年的計(jì)算理論頂會(huì)STOC上獲得了最佳論文獎(jiǎng)。那么，他們獲獎(jiǎng)的這項(xiàng)研究，具體說了些什么呢？科學(xué)家們的“30年期待”這里我們需要先來了解一些背景知識(shí)。和在線算法相對(duì)的，還有離線算法，它在開始處理之前需要先接收到所有的輸入數(shù)據(jù)。由于預(yù)先掌握了完整數(shù)據(jù)，在同等的數(shù)據(jù)規(guī)模下離…

原文鏈接：點(diǎn)此閱讀原文：頂會(huì)最佳論文覆滅科學(xué)家們30多年期待：復(fù)雜度遠(yuǎn)超預(yù)期

聯(lián)系作者

文章來源：量子位

作者微信：QbitAI

作者簡(jiǎn)介：追蹤人工智能新趨勢(shì)，關(guān)注科技行業(yè)新突破