三十多年來，在線算法一直被科學家寄予厚望，但一篇論文的誕生讓它走下了神壇。
它的目标，簡單來說就是在沒有完整數據的情況下，通過有限的信息提前找到最佳策略。
在我們的生活中，例如股票市場的即時交易分析，還有導航路徑的實時規劃，都有在線算法的身影。
不過沒有完整數據，就意味着性能将受到限制；因此科學家們一直期待它能突破數據的桎梏，達到更高的效率。
然而就在最近，來自微軟研究院、牛津大學等機構的研究人員在進行了一場實驗之後發現，這種算法的複雜度遠遠超過了人們的期待。
他們也憑借着這篇論文，在今年的計算理論頂會 STOC 上獲得了最佳論文獎。
那麽，他們獲獎的這項研究，具體說了些什麽呢？
科學家們的 "30 年期待 "
這裏我們需要先來了解一些背景知識。
和在線算法相對的，還有離線算法，它在開始處理之前需要先接收到所有的輸入數據。
由于預先掌握了完整數據，在同等的數據規模下離線算法顯著快過在線算法
想象一下，現在要從一系列數字中找出最大值，第一種情況是直接知道所有數字，另一種是比較完前面的數才知道後面的數字是多少，顯然第一種情況的速度更快。
于是離線算法的性能被看作是一個标杆，并衍生出了 " 競争比 " 的概念。
而在過去的 30 多年裏，在線算法曾一度被寄予競争比接近 1 的厚望。
具體的體現是，關于在線算法，學界有一個經典問題，叫做k-server 問題。
k-server 問題可以這樣來描述：
給定一個度量空間和位于該空間指定位置的 k 個服務器，在該空間的不同位置中會出現一系列請求。
對于每個請求，都必須選擇一個服務器來響應該請求。
如果服務器已經在請求的位置，它可以立即響應；否則，它必須移動到請求的位置。
而 k-server 問題的最終目标，是将所有服務器移動距離的總和最小化。
舉個例子，在一公路旁有若幹家餐館，路上有 k 個空閑的外賣員，這些餐館可能随時需要外賣員上門取餐，此時外賣員的調度就可以看做是一個 k-server 問題。
而在這個過程當中，無論是系統還是外賣員在真的接到訂單之前都不知道訂單出現的時間和位置，此時的問題是如何将所有外賣員取餐所走的路程之和最小化。
直到這篇論文發表爲止，長達 30 多年的時間裏，在線算法一直被期待在解決所有k-server 問題時，複雜度都不超過 Θ ( log k ) 。
（其中 Θ 表示漸進緊确界，可簡單理解爲數量級相同）
但這篇論文的出現，讓這個期待被打破。
那麽，作者又是如何把這個期待證僞的呢？
複雜度遠超預期
注：本節中的對數符号 log，如無特别說明，底數爲 2
遞歸構建圖度量空間
爲了探究 k-server 問題的複雜度，作者構建了一個遞歸定義的圖度量空間（本質上也是 k-server 問題）。
作者首先構造一個簡單的度量空間 M ( 0 ) ，然後把多個 M ( 0 ) 按照循環的方式連成一個環 M ( 1 ) ，然後把多個 M ( 1 ) 連接成 M ( 2 ) ……以此類推，最終形成了一個可以分割成對稱的子結構的空間。
在這個度量空間上作者設計了一個随機請求序列 ρ，它會在對稱子結構之間交替選擇請求點，迫使在線算法在子結構間頻繁移動，而最優算法是固定在一個子結構。
之後，作者證明了在這個特殊構造的度量空間和請求序列上 , 任何确定性在線算法的預期消耗最低也要達到 Ω ( log ² ) 。
而具體的證明，則采用了數學歸納法。
數學歸納法
數學歸納法雖然名字裏有個歸納，實質上卻是一種嚴謹的演繹推理。
它首先驗證結論針對序列中的第一項是否成立，然後假設對第 k 項也成立，接着，隻要能證明對第 k+1 項也成立，結論就可以得到證明。
這個過程就像多米諾骨牌，隻要推倒（k+1）一塊，其他的牌自然也會随之倒下，這時同時确保第一塊有同樣的效果，整個體系就完備了。
舉個例子，我們知道數列 {a ( n ) =n} 的前 n 項和 S ( n ) =n ( n+1 ) /2，用數學歸納法證明過程如下：
首先 n=1 時，a ( n ) =1，S ( n ) =1 ( 1+1 ) /2=1，結論成立
然後假設 n=k 時結論也成立，此時 S ( k ) =k ( k+1 ) /2
那麽，當 n=k+1 時，S ( k+1 ) =S ( k ) + ( k+1 )
即 S ( k+1 ) =k ( k+1 ) /2+2 ( k+1 ) /2
提取公因子 ( k+1 ) ，這個式子又可以寫成 ( k+2 ) ( K+1 ) /2
此時 n=k+1，n+1=k+2，結論依然成立
所以 S ( n ) =n ( n+1 ) /2 得證
任意度量空間消耗下限
而具體到這項研究，作者利用随機性和對稱性定義了一個新的序列 ρ ( w ) ，并假設在度量空間 M ( w ) 中，對随機的 ρ ( w ) ，确定性算法的消耗下限爲 Ω ( w ² ) 。
首先對于 M ( 0 ) ，确定性算法的消耗下限爲 1，此時結論成立。
然後試着将 w 推廣到 w+1，構建出 M ( w+1 ) 的度量空間，它包含兩條由多個 M ( w ) 組成的對稱路徑。
在請求 ρ ( w+1 ) 上，假設此時位于左路徑，下一段位于左右路徑的概率各爲 1/2。
如果下階段位于右路徑，算法複雜度将會因爲路徑切換而升高，不是低消耗。
而如果位于左路徑，由于路徑上都是一個個 M ( w ) ，所以新增部分的消耗下限就是 Ω ( w ² ) （此爲歸納法假設）。
于是對于 w+1 段路徑，可以将每一段的消耗 Ω ( w ² ) 累加，即爲 ( w+1 ) Ω ( w ² ) ，結合 Ω 的定義，最終可以證明 M ( w+1 ) 的最低消耗爲 Ω ( ( w+1 ) ² ) ，進而證明假設成立。
回到最初的度量空間
而作者構建的 M ( w+1 ) 都是由 6 個 M ( w ) 組成，則 M ( w ) 的大小 n=|M ( w ) |=O ( 6^w ) ，取對數得 log|M ( w ) |=w · log6。
代入 Ω ( w ² ) 中，得到在 n 點度量空間中，消耗下限爲 Ω ( ( logn/log6 ) ² ) ，而當 n=k 時，消耗下限則爲 Ω ( ( logk/log6 ) ² ) 。
而 log6 爲一個 2 到 3 之間的常數，除以這樣一個數不會帶來結果的顯著改變，也就證明了 k-server 問題中消耗不低于 Ω ( log ² k ) 的結論。
當 k 足夠大時，log ² k 顯然大于 logk，因此在這樣的 k-server 問題中，實現 O ( logk ) 級别的低消耗是不可能的。
而此前人們一直認爲可以用這樣的消耗解決所有的 k-server 問題，因此反例的出現便宣告了這一設想的終結。
論文地址：
https://dl.acm.org/doi/pdf/10.1145/3564246.3585132
參考鏈接：
https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/
