頂會最佳論文覆滅科學家們30多年期待：復雜度遠超預期

AIGC動態歡迎閱讀

原標題：頂會最佳論文覆滅科學家們30多年期待：復雜度遠超預期

關鍵字：算法,度量,消耗,空間,路徑

文章來源：量子位

內容字數：5953字

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

原文鏈接：點此閱讀原文：頂會最佳論文覆滅科學家們30多年期待：復雜度遠超預期

聯系作者

文章來源：量子位

作者微信：QbitAI

作者簡介：追蹤人工智能新趨勢，關注科技行業新突破