研究所考試

在演算法設計與分析中，許多經典問題皆假設完整輸入在演算法執行前已經取得。例如排序演算法如 Merge Sort、Quick Sort，圖論中的 Dijkstra 最短路徑演算法，以及最小生成樹的 Kruskal 與 Prim 演算法，皆屬於典型的離線演算法（offline algorithms）。這類演算法在開始運算時，已掌握全部輸入資訊，因此能以全域觀點規劃最佳策略並求得最優解。然而，在許多真實情境中，輸入資料往往隨時間逐步到達，而非事先完整給定。在此情況下，決策必須即時做出，且無法預測未來的資訊。

為了應付此類問題，線上演算法（online algorithms）因此而誕生。線上演算法在輸入逐步揭露的條件下運作，必須根據當前已知資訊立即做出不可撤回的決策。由於無法掌握未來輸入，其效能通常透過與理想的離線最佳演算法進行比較，並以競爭分析（competitive analysis）評估其在最壞情況下的表現。

在本專欄的引言中有提及，很多的演算法所面對的問題，大部分會假設在演算法執行之前，整個輸入已經被完整取得。例如排序類的演算法，在演算法開始執行前就會得到完整需要被排序的資料；找出最短路徑或最小生成樹的演算法，在演算法開始執行前也會取得完整的圖形資料。但在許多情況下，輸入並非事先提供，而是在演算法執行的過程中才逐步出現。以資料結構的概念來看，我們會想要設計一種資料結構，能夠在每次操作時間成本為O(lgn)的時間處理 n 次的搜尋、插入及刪除，有很高的概率是因為設計者預期會收到 n 個操作請求，但事前並不會知道準確會出現的操作有哪些。均攤分析（amortized analysis）也是類似的概念，透過維護表格，使其能夠根據一連串插入與刪除操作進行擴張或縮減，同時保持每次操作具有常數的均攤成本。

線上演算法（online algorithm）會隨時間逐步接收其輸入，而不像離線演算法（offline algorithm）那樣在一開始就擁有完整的輸入。線上演算法適用於許多資訊逐漸到達的情況。以最近屢創新高的股票市場來舉例，股票交易員需要在無法得知明天價格的情況下做出決策，卻仍希望獲得良好報酬。我們每天都在用的電腦和手機，作業系統必須在不知道未來需要完成哪些工作的情況下，排程已經送達的工作。便利商店和大賣場的經營者，必須在不知道未來消費者需求的情況下，決定何時訂購更多存貨。計程車司機必須在不知道未來誰會叫車的情況下，決定是否接下一筆訂單。以上提及的情況以及更多適用線上演算法的情境中，演算法決策都必須在不了解未來的前提下做出。

處理未知未來輸入有多種方法。其中一種方法是建立未來輸入的機率模型，並設計一個假設未來輸入符合該模型的演算法。這種技術在排隊理論（queuing theory）等領域中很常見，也與機器學習相關。不過，你可能無法建立一個可行的機率模型；即使可以，有些輸入也可能不符合該模型。在CLRS中，作者所介紹的方法，不對未來輸入做任何假設，而是採取一種保守策略，確保無論輸入如何，解的品質都不會差到某個不可接受的程度。簡單總結，線上演算法的目標並不是去猜對未來的結果，而是控制最差的狀況。

因此，我們採用最壞情況的方法來設計線上演算法，使其能夠對所有可能的未來輸入保證解答品質。我們將透過比較線上演算法產生的解與一個知道未來輸入的最佳演算法所產生的解，並在所有可能實例上取最壞比例，來分析線上演算法。這個方法被稱為競爭分析（competitive analysis）。它的概念有點像之前專欄提過的近似演算法：將一個可能次優演算法所回傳的解與最佳解的價值進行比較，並在所有可能實例上決定其最壞比例。如果講到這裡還霧煞煞的話，我們就直接用一個例子：搭電梯問題，來理解競爭分析是什麼概念吧！

搭電梯問題，我相信是每一位讀者在日常生活中都曾經歷過的事情。想像你來到一棟大樓，而你想要前往的樓層位在第 k 層，這時候你要選擇等電梯，還是直接走樓梯呢？為了方便起見，假設你爬樓梯的速度是每分鐘一層。電梯的速度比你爬樓梯快得多：它可以在一分鐘內上升全部k層，也就是說無論你何時決定要搭電梯，它都能在一分鐘後把你送到目的地。你所面臨的困境在於，你不知道電梯還要等多久才會到達一樓接你。你應該搭電梯還是走樓梯？該如何決定？

讓我們分析這個問題。無論如何，走樓梯都需要 k 分鐘。假設你知道電梯最多需要 B−1 分鐘才會到達，其中 B 的值遠大於 k。（你按電梯的時候它可能正往上走，然後在往下的途中可能停靠多個樓層。）按照這個情境，我們可以得知等待電梯並搭乘它上到第 k 層，所需時間介於 1 分鐘（若電梯已在一樓）到 (B−1)+1=B 分鐘（最壞情況）。雖然你知道 B 跟 k 分別為何，但你不知道這一次電梯究竟多久才會到達。在這種情況下，我們可以透過競爭分析來幫助決定應該走樓梯還是搭電梯。依競爭分析的精神，你希望無論未來如何（也就是電梯何時到達），你的等待時間都不會比一位事先知道電梯到達時間的「先知」多太多。

那我們先來看看，擁有全知視角的先知會怎麼做：若先知知道電梯會在最多 k−1 分鐘內到達，他就會等電梯；否則，他會走樓梯。設 m 表示電梯到達一樓所需的分鐘數，則先知所花費的時間可表示為函數如下：

這時候要來介紹線上演算法的評估標準，也就是競爭比率（competitive ratio）。設 U 為所有可能輸入的集合（全集），而 I 爲集合中的某一個輸入。對於最小化問題（例如本問題），若線上演算法 A 在輸入 I 上得到的解值為 A(I)，而知道未來資訊的演算法 F 在同一輸入上得到的解值為 F(I)，則演算法 A 的競爭比率為：

若演算法 A 的競爭比率為 c，則稱其為 c-competitive，跟近似演算法的近似比率表示方式非常相近。以最小化問題來說，其競爭比率至少為 1，因此我們希望線上演算法的競爭比率盡可能接近 1，也就是解法盡量靠近最佳解。

在走樓梯與搭電梯的問題中，唯一的輸入是電梯到達所需的時間。先知所使用的演算法 F 知道此資訊，而線上演算法必須在不知道電梯何時到達的情況下做決策。考慮演算法「永遠走樓梯」，它總是花費恰好 k 分鐘。我們可得競爭比率為：

透過列舉上面式子的每一項，可得競爭比率爲：

此時這個演算法的競爭比率爲 k，最大值發生在電梯立即到達時。在此情況下，走樓梯需要 k 分鐘，而最佳解只需 1 分鐘。

此時我們考慮一個完全相反的策略：「永遠搭電梯」。若電梯需 m 分鐘到達一樓，則此演算法總花費 m+1 分鐘。因此其競爭比率為：

透過列舉上面式子的每一項，可得競爭比率爲：

最大值在電梯於 B−1 分鐘後才到達時取得，與最佳策略（走樓梯）所需的 k 分鐘相比。因此，「永遠走樓梯」的競爭比率為 k；「永遠搭電梯」的競爭比率為 B/k。由於我們偏好競爭比率較小的演算法，若 k=10 且 B=300，則我們會選擇「永遠走樓梯」，其競爭比率為 10，而非「永遠搭電梯」的 30。走樓梯並不總是較好，或更常較好；只是它在最壞情況下提供較佳的保障。

然而，這兩種「永遠走樓梯」與「永遠搭電梯」的策略都相當極端。相反地，你可以「設下對沖（hedge）」，以更好地防範最壞情況。用白話文來說就是：你可以先等待電梯一段時間，若它尚未到達，再改走樓梯。那麼，等待多久算「一段時間」？假設這段時間為 k 分鐘，則此對沖策略所需時間 h(m)，可表示為：

在第二種情況下，h(m)=2k，因為你等待 k 分鐘後，再用 k 分鐘走樓梯。此時競爭比率為：

列舉此式可得競爭比率爲：

在這個情況下，競爭比率與 B 和 k 都無關。這個例子說明了線上演算法的一個常見理念：我們希望設計的演算法可以權衡利弊，以防範任何可能發生的最壞情況。起初等待電梯，可以應對電梯很快到達的情況；而最終改走樓梯，則可防範電梯遲遲不來的情況。

透過今天的專欄，我們介紹了線上演算法，其特色為並不會在最一開始就有完整輸入，而是會隨時間逐步接收輸入。透過競爭分析（competitive analysis），透過比較線上演算法產生的解與一個知道未來輸入的最佳演算法所產生的解，並在所有可能實例上取最壞比例，來分析線上演算法。透過經典的搭電梯問題，我們演示了三種策略：「永遠走樓梯」、「永遠搭電梯」以及綜合前面兩種的「權衡利弊」，透過三者的競爭比率來分析優劣。希望透過今天的專欄內容，讓各位讀者對於線上演算法的設計概念有初步認識。