三十多年來(lái)，在線算法一直被科學(xué)家寄予厚望，但一篇論文的誕生讓它走下了神壇。

它的目標(biāo)，簡(jiǎn)單來(lái)說(shuō)就是在沒(méi)有完整數(shù)據(jù)的情況下，通過(guò)有限的信息提前找到最佳策略。

在我們的生活中，例如股市場(chǎng)的即時(shí)交易分析，還有導(dǎo)航路徑的實(shí)時(shí)規(guī)劃，都有在線算法的身影。

不過(guò)沒(méi)有完整數(shù)據(jù)，就意味著性能將受到限制；因此科學(xué)家們一直期待它能突破數(shù)據(jù)的桎梏，達(dá)到更高的效率。

然而就在最近，來(lái)自微軟研究院、牛津大學(xué)等機(jī)構(gòu)的研究人員在進(jìn)行了一場(chǎng)實(shí)驗(yàn)之后發(fā)現(xiàn)，這種算法的復(fù)雜度遠(yuǎn)遠(yuǎn)超過(guò)了人們的期待。

他們也憑借著這篇論文，在今年的計(jì)算理論頂會(huì)STOC上獲得了最佳論文獎(jiǎng)。

那么，他們獲獎(jiǎng)的這項(xiàng)研究，具體說(shuō)了些什么呢？

科學(xué)家們的“30年期待”

這里我們需要先來(lái)了解一些背景知識(shí)。

和在線算法相對(duì)的，還有離線算法，它在開(kāi)始處理之前需要先接收到所有的輸入數(shù)據(jù)。

由于預(yù)先掌握了完整數(shù)據(jù)，在同等的數(shù)據(jù)規(guī)模下離線算法顯著快過(guò)在線算法

想象一下，現(xiàn)在要從一系列數(shù)字中找出最大值，第一種情況是直接知道所有數(shù)字，另一種是比較完前面的數(shù)才知道后面的數(shù)字是多少，顯然第一種情況的速度更快。

于是離線算法的性能被看作是一個(gè)標(biāo)桿，并衍生出了“競(jìng)爭(zhēng)比”的概念。

而在過(guò)去的30多年里，在線算法曾一度被寄予競(jìng)爭(zhēng)比接近1的厚望。

具體的體現(xiàn)是，關(guān)于在線算法，學(xué)界有一個(gè)經(jīng)典問(wèn)題，叫做k-server問(wèn)題。

k-server問(wèn)題可以這樣來(lái)描述：

給定一個(gè)度量空間和位于該空間指定位置的k個(gè)服務(wù)器，在該空間的不同位置中會(huì)出現(xiàn)一系列請(qǐng)求。

對(duì)于每個(gè)請(qǐng)求，都必須選擇一個(gè)服務(wù)器來(lái)響應(yīng)該請(qǐng)求。

如果服務(wù)器已經(jīng)在請(qǐng)求的位置，它可以立即響應(yīng)；否則，它必須移動(dòng)到請(qǐng)求的位置。

而k-server問(wèn)題的最終目標(biāo)，是將所有服務(wù)器移動(dòng)距離的總和最小化。

舉個(gè)例子，在一公路旁有若干家餐館，路上有k個(gè)空閑的外賣(mài)員，這些餐館可能隨時(shí)需要外賣(mài)員上門(mén)取餐，此時(shí)外賣(mài)員的調(diào)度就可以看做是一個(gè)k-server問(wèn)題。

而在這個(gè)過(guò)程當(dāng)中，無(wú)論是系統(tǒng)還是外賣(mài)員在真的接到訂單之前都不知道訂單出現(xiàn)的時(shí)間和位置，此時(shí)的問(wèn)題是如何將所有外賣(mài)員取餐所走的路程之和最小化。

直到這篇論文發(fā)表為止，長(zhǎng)達(dá)30多年的時(shí)間里，在線算法一直被期待在解決所有k-server問(wèn)題時(shí)，復(fù)雜度都不超過(guò)Θ(log k)。

（其中Θ表示漸進(jìn)緊確界，可簡(jiǎn)單理解為數(shù)量級(jí)相同）

但這篇論文的出現(xiàn)，讓這個(gè)期待被打破。

那么，作者又是如何把這個(gè)期待證偽的呢？

復(fù)雜度遠(yuǎn)超預(yù)期

注：本節(jié)中的對(duì)數(shù)符號(hào)log，如無(wú)特別說(shuō)明，底數(shù)為2

遞歸構(gòu)建圖度量空間

為了探究k-server問(wèn)題的復(fù)雜度，作者構(gòu)建了一個(gè)遞歸定義的圖度量空間（本質(zhì)上也是k-server問(wèn)題）。

作者首先構(gòu)造一個(gè)簡(jiǎn)單的度量空間M(0)，然后把多個(gè)M(0)按照循環(huán)的方式連成一個(gè)環(huán)M(1)，然后把多個(gè)M(1)連接成M(2)……以此類(lèi)推，最終形成了一個(gè)可以分割成對(duì)稱(chēng)的子結(jié)構(gòu)的空間。

在這個(gè)度量空間上作者設(shè)計(jì)了一個(gè)隨機(jī)請(qǐng)求序列ρ，它會(huì)在對(duì)稱(chēng)子結(jié)構(gòu)之間交替選擇請(qǐng)求點(diǎn)，迫使在線算法在子結(jié)構(gòu)間頻繁移動(dòng)，而最優(yōu)算法是固定在一個(gè)子結(jié)構(gòu)。

之后，作者證明了在這個(gè)特殊構(gòu)造的度量空間和請(qǐng)求序列上,任何確定性在線算法的預(yù)期消耗最低也要達(dá)到Ω(log2??)。

而具體的證明，則采用了數(shù)學(xué)歸納法。

數(shù)學(xué)歸納法

數(shù)學(xué)歸納法雖然名字里有個(gè)歸納，實(shí)質(zhì)上卻是一種嚴(yán)謹(jǐn)?shù)难堇[推理。

它首先驗(yàn)證結(jié)論針對(duì)序列中的第一項(xiàng)是否成立，然后假設(shè)對(duì)第k項(xiàng)也成立，接著，只要能證明對(duì)第k+1項(xiàng)也成立，結(jié)論就可以得到證明。

這個(gè)過(guò)程就像多米諾骨牌，只要推倒（k+1）一塊，其他的牌自然也會(huì)隨之倒下，這時(shí)同時(shí)確保第一塊有同樣的效果，整個(gè)體系就完備了。

舉個(gè)例子，我們知道數(shù)列{a(n)=n}的前n項(xiàng)和S(n)=n(n+1)/2，用數(shù)學(xué)歸納法證明過(guò)程如下：

首先n=1時(shí)，a(n)=1，S(n)=1(1+1)/2=1，結(jié)論成立

然后假設(shè)n=k時(shí)結(jié)論也成立，此時(shí)S(k)=k(k+1)/2

那么，當(dāng)n=k+1時(shí)，S(k+1)=S(k)+(k+1)
即S(k+1)=k(k+1)/2+2(k+1)/2
提取公因子(k+1)，這個(gè)式子又可以寫(xiě)成(k+2)(K+1)/2
此時(shí)n=k+1，n+1=k+2，結(jié)論依然成立
所以S(n)=n(n+1)/2得證

任意度量空間消耗下限

而具體到這項(xiàng)研究，作者利用隨機(jī)性和對(duì)稱(chēng)性定義了一個(gè)新的序列ρ(w)，并假設(shè)在度量空間M(w)中，對(duì)隨機(jī)的ρ(w)，確定性算法的消耗下限為Ω(w2)。

首先對(duì)于M(0)，確定性算法的消耗下限為1，此時(shí)結(jié)論成立。

然后試著將w推廣到w+1，構(gòu)建出M(w+1)的度量空間，它包含兩條由多個(gè)M(w)組成的對(duì)稱(chēng)路徑。

在請(qǐng)求ρ(w+1)上，假設(shè)此時(shí)位于左路徑，下一段位于左右路徑的概率各為1/2。

如果下階段位于右路徑，算法復(fù)雜度將會(huì)因?yàn)槁窂角袚Q而升高，不是低消耗。

而如果位于左路徑，由于路徑上都是一個(gè)個(gè)M(w)，所以新增部分的消耗下限就是Ω(w2)（此為歸納法假設(shè)）。

于是對(duì)于w+1段路徑，可以將每一段的消耗Ω(w2)累加，即為(w+1)Ω(w2)，結(jié)合Ω的定義，最終可以證明M(w+1)的最低消耗為Ω((w+1)2)，進(jìn)而證明假設(shè)成立。

回到最初的度量空間

而作者構(gòu)建的M(w+1)都是由6個(gè)M(w)組成，則M(w)的大小n=|M(w)|=O(6^w)，取對(duì)數(shù)得log|M(w)|=w·log6。

代入Ω(w2)中，得到在n點(diǎn)度量空間中，消耗下限為Ω((logn/log6)2)，而當(dāng)n=k時(shí)，消耗下限則為Ω((logk/log6)2)。

而log6為一個(gè)2到3之間的常數(shù)，除以這樣一個(gè)數(shù)不會(huì)帶來(lái)結(jié)果的顯著改變，也就證明了k-server問(wèn)題中消耗不低于Ω(log2k)的結(jié)論。

當(dāng)k足夠大時(shí)，log2k顯然大于logk，因此在這樣的k-server問(wèn)題中，實(shí)現(xiàn)O(logk)級(jí)別的低消耗是不可能的。

而此前人們一直認(rèn)為可以用這樣的消耗解決所有的k-server問(wèn)題，因此反例的出現(xiàn)便宣告了這一設(shè)想的終結(jié)。

論文地址：https://dl.acm.org/doi/pdf/10.1145/3564246.3585132
參考鏈接：https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/