動機
離線優化者在行動之前已知道整個輸入。線上算法則必須隨著資訊陸續到來而作出選擇,而當未來與其預期不同時,某個選擇可能變得代價高昂。將線上成本與同一完整輸入上的最優成本比較,便給出了度量這種劣勢的精確方法。租滑雪裝備問題(ski-rental problem)把這個問題單獨抽出來:在活動持續期間可以每日租用,也可以一次過付費購買,但事前並不知道最後一日何時來臨。
競爭保證是針對所有可能輸入長度的最壞情況陳述。它並不預測實際的日數,也不假設日數服從任何概率分佈。本單元使用購買成本為整數的離散版本;其他的時間與成本約定會給出不同的常數。
定義
定義 7.1.1
(離散的滑雪租買問題)
固定整數 。共有 日,其中時間範圍 對線上算法是未知的。在實際出現的每一日開始時,算法得知這一日存在;若尚未購買,則當日要麼以成本 租用,要麼以成本 購買。購買之後不再產生任何費用。時間範圍可以在任何一日之後結束。離線算法事先知道 。
定義 7.1.2
(離線最優與競爭比)
在這個模型中,離線最優成本為 :要麼租滿 日,要麼在第一日購買。若時間範圍已知,則遲些購買不會比第一日購買更好,因為這會增加租金。對於線上算法 ,其競爭比定義為 在所有正整數時間範圍上的上確界。此定義中不容許有加性項。
定義 7.1.3
(閾值算法)
閾值算法在首 日(若這些日子出現)租用,並在第 日開始時購買(若該日出現)。當 時,它立即購買。算法在為第 日付費之前已得知該日存在,但並不知道之後是否還有下一日。
定理
定理 7.1.4
(閾值算法)
對每個整數 ,在上述模型中閾值算法的競爭比為 。
定理 7.1.5
(與之匹配的確定性下界)
在此模型中,每個確定性線上算法的競爭比至少為 。因此,就這個競爭比定義而言,閾值算法在確定性算法中是最優的。
證明思路
證明
(閾值算法的比值)
若 ,閾值算法每日都租用,付出 。若 ,它支付 的租金,再支付 購買,合共 。離線最優成本為 ,故比值為 。 時達到這個值,所以這就是精確的最壞情況比值。
證明
(購買日迫使出現壞的時間範圍)
對於下界,固定任意一個確定性算法。它在無限持續的輸入上的行動決定了它購買的第一日 (若它確實會購買)。在那一日之前它必須租用。若它從不購買,則對於任意大的 ,其成本為 ,而離線最優成本為 ;其比值沒有上界。否則,考慮固定的時間範圍 。算法在那一日購買,因為它所觀察到的歷史與無限持續輸入上的歷史相同。它付出 。
若 ,則 ,比值為 。若 ,則離線最優成本為 ,比值為 。這也包括 的情況。因此,對於確定性算法的每一種購買日選擇,都存在一個時間範圍,使其比值至少達到所聲稱的值。下界是在檢視了該確定性算法之後才構造時間範圍的;這是一個最壞情況的存在性論證,並不是說算法知道自己的時間範圍。
證明透視
從永不終止的輸入讀出購買日
下界證明有一個不明顯的步驟:它先從算法在永不終止的輸入上的行為讀出購買日 ,然後才選取時間範圍。這是合理的,因為確定性算法在見過第 日之後,無論雪季在第 日後結束還是繼續,行動都完全相同。證明接著需要在 處分情況,因為離線最優 在那裏改變形式: 時一直租用最優, 時立即購買最優。兩種情況下,比值 都至少為 ,僅在 時取等號。永不購買的算法另行處理:它的比值無界。這個論證只建立了一個方向:對任意算法給出一個壞的時間範圍,而閾值規則的上界則必須對每個時間範圍都成立。
例題詳解
例題 7.1.6
(時間範圍在購買之前結束)
設 ,。閾值規則租用三次,成本為 。離線最優成本為 ,故比值為一。算法不會僅僅因為計劃在第五日購買便去購買;那一日必須真的出現。
例題 7.1.7
(閾值日恰為最後一日)
設 ,。算法租用四日,並在第五日購買,合共付出 。離線優化者立即購買或租滿五日,兩種方式都付出 。比值為 ,這正是該規則的最壞情況。算法知道第五日已經來臨,但在作出當日的決定時無法知道這是否為最後一日。
例題 7.1.8
(買得太早或太遲)
對 ,在第 日購買的算法,當 時付出 ,而離線最優成本為 ;比值為 。在第 日購買的算法,當 時付出 ,而離線最優成本為 ;比值為 。兩者都超過閾值比 。
常見錯誤
反例模式
知道當前是第幾日並不等於知道時間範圍
在第五日開始時,時間範圍 與 的歷史完全相同。線上算法無法讓第五日的行動取決於最終會出現哪一個時間範圍。若賦予它這種資訊,就會悄悄地把這個決策變成離線決策。
常見錯誤
(比較不同時間範圍上的成本)
競爭比比較的是同一時間範圍上的成本。把長時間範圍上的線上成本除以另一個短時間範圍上的離線成本,是沒有意義的。
常見錯誤
(把比值界當作在每個輸入上都最優)
比值的界並不表示算法在每個輸入上都是最優的:在閾值日,差距是實際存在的,儘管它是有界的。對 、,算法付出 ,而最優成本為 。
為甚麼閾值能平衡兩種風險
假設某個確定性規則計劃在第 日購買。對於恰好在那一日結束的時間範圍,該規則要支付之前所有的租金以及購買費用。若 ,離線最優做法本應是一直租用,因此比值為 。當 向 增大時,該表達式減小。若 ,離線優化者本應立即購買,比值變為 ,它隨 增大而增大。兩個表達式在 處相交。這解釋了該規則:買得太早,有在時間範圍結束前夕才付出購買價格的風險;買得太遲,則會累積不必要的租金。
這個論證利用時間範圍 為每個購買日推出一個下界。要確定閾值規則的精確比值,仍須像第一個定理那樣分析所有時間範圍。僅在某一個精心選取的時間範圍上取值,只能給出某個特定算法最壞情況比值的下界。反過來,檢驗許多樣本時間範圍也無法建立普遍的上界;以 為界的情況劃分涵蓋了每個正整數時間範圍。
例題 7.1.9
(比較小購買價格下每一個確定性閾值)
取 。第一日購買時,當 比值為 。第二日購買時,當 比值為 。第三日購買時,對每個 比值為 ,而對較短的時間範圍比值為一。在任意第 日購買時,當 比值至少為 。從不購買的比值沒有上界。因此第三日是最佳的確定性閾值,其比值與定理一致。
下面的互動圖讓你改變購買價格 與購買日 ,並顯示每個 的精確最壞比值 ,其最小值 出現在 。
選擇購買日
固定購買價格 B。此規則在第 1、…、D − 1 日租用,並在第 D 日開始時購買(若該日出現)。請對每個 D 比較它在所有時間範圍上的最壞比值 cost/OPT。
| D | 最壞比值 (D − 1 + B)/min(D, B) | 四捨五入小數 | 主要風險 | 最小值 |
|---|---|---|---|---|
| 1 | 3 | 3.000 | 買得太早 | 否 |
| 2 | 2 | 2.000 | 買得太早 | 否 |
| 3 | 5/3 | 1.667 | 兩者平衡 | 是 |
| 4 | 2 | 2.000 | 租得太久 | 否 |
| 5 | 7/3 | 2.333 | 租得太久 | 否 |
| 6 | 8/3 | 2.667 | 租得太久 | 否 |
| 7 | 3 | 3.000 | 租得太久 | 否 |
| 8 | 10/3 | 3.333 | 租得太久 | 否 |
| 9 | 11/3 | 3.667 | 租得太久 | 否 |
| 從不 | 無上界 | ∞ | 從不購買 | 否 |
| T | 規則成本 | OPT(T) = min(T, B) | 比值 | 達到最壞比值 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 否 |
| 2 | 2 | 2 | 1 | 否 |
| 3 | 5 | 3 | 5/3 | 是 |
| 4 | 5 | 3 | 5/3 | 是 |
| 5 | 5 | 3 | 5/3 | 是 |
| 6 | 5 | 3 | 5/3 | 是 |
| 7 | 5 | 3 | 5/3 | 是 |
| 8 | 5 | 3 | 5/3 | 是 |
| 9 | 5 | 3 | 5/3 | 是 |
- 此 D 的最壞比值
- 5/3
- 所有 D 中的最佳比值
- 5/3
- 主要風險
- 兩者平衡
- T 時規則成本
- 5
- T 時 OPT
- 3
- T 時比值
- 5/3
D = 3 的最壞比值:(3 − 1 + 3)/min(3, 3) = 5/3,在 T = 3 時達到。最佳的 D = B = 3,比值為 2 − 1/3 = 5/3。 T = 3 時:規則成本 5,OPT 3,比值 5/3。
為何 D = B 是最小值
當 T < D 時規則付出 T,故當 T ≤ B 時比值為 1,當 T > B 時比值為 T/B ≤ (D − 1)/B。當 T ≥ D 時規則付出 D − 1 + B,而 OPT(T) = min(T, B) 在 T = D 時最小,所以上確界為 (D − 1 + B)/min(D, B)。
若 D ≤ B,該值等於 1 + (B − 1)/D,隨 D 增大而遞減(買得太早)。若 D ≥ B,該值等於 (D − 1 + B)/B,隨 D 增大而遞增(租得太久)。兩者僅在 D = B 相遇,此時值為 (2B − 1)/B = 2 − 1/B。
表中列出時間範圍 1 至 max(3B, D);對有限的 D,更長的時間範圍其成本與比值和表中最後一列相同,因此上確界是精確的。模型為本單元所採用、購買價格為整數且不含加性常數的版本。
下界中的對手知道甚麼
對於確定性算法,在給定歷史上的行動是固定的。在無限持續的輸入上,算法要麼在某一日購買,要麼永遠租用。這個假想的輸入是確定其購買日的一種便利方法;用來見證下界的有限時間範圍是在此之後才選取的。直至那一日為止,有限輸入與無限輸入的歷史完全相同,所以算法的行動也完全相同。對該特定的確定性算法而言,下界所用的輸入是一個有效的、固定的有限序列。
該論證並不假設真實的對手能夠看到未來的隨機種子。事實上,它並沒有為隨機化算法建立匹配的下界。隨機化算法可能在不同的隨機結果下選擇不同的購買日,因此不一定存在單一的確定性 能描述它的所有運行。分析必須說明輸入是否獨立於隨機選擇而固定、所取的是甚麼期望,以及使用甚麼基準。若不加這些限定便重複使用確定性證明,會混淆不同的模型。
競爭比也不是對時間範圍取的平均。時間範圍的某個分佈可能令某種策略在期望意義下具吸引力,但那將是另一個目標。例如,若決策者確定地知道 且 ,則租用是最優的;若確定地知道 非常大,則立即購買是最優的。競爭性規則不作這類分佈假設,並在這兩類時間範圍上都控制其損失。
時間與建模的選擇
事件發生的次序決定了定理。在我們的模型中,算法先得知當前這一日存在,然後選擇租用或購買,之後才得知是否還有更多的日子。因此它不會為不存在的一日付費,但它可以在最後一個實際存在的日子購買。若規則必須在得知當日是否存在之前便作出承諾,或者購買只從翌日起生效,則成本表達式會改變。針對某一種約定寫出的證明,在未重新核對事件次序之前,不得照搬到另一種約定上。
整數假設同樣重要。這裏的閾值日字面上就是 。若購買成本不是整數,就必須選擇一個整數日並比較鄰近的幾種可能;把 換成非整數的日子並不是有效的算法。更一般地,每日租金 可以透過把所有成本除以 來歸一化,但所得的購買與租金之比不一定是整數。明確的整數假設避免了取整問題,而不是悄悄地解決它。
該模型只容許購買至多一次,且此後擁有物品不再產生費用。若購買的物品會損耗、有每日的運作成本或可以轉售,則線上算法與離線最優都會改變。這類變體仍可能是有用的線上問題,但公式 需要新的理據。基準必須體現與算法相同的規則與成本,只是它知道時間範圍。
所提出競爭比的一份證書
要驗證上界 ,需在每一類可能的輸入上計算線上與離線成本,並在每一類中證明 。對於閾值規則,以 為界的劃分已經足夠,因為兩側的公式分別變成常數或簡單形式。要說明 對該特定算法也是必要的,需給出一個使等號成立的時間範圍。這裏任何 都達到 。
對所有確定性算法的下界更強:它必須從任意算法出發,而不只是預先選好的另一個閾值。在這個簡單的問題中,購買之前唯一可能的行動是租用,算法觀察到的僅是日子的流逝。因此它在持續輸入上的確定性行為決定了一個購買日,或者從不購買的行為。這一觀察證明了把任意確定性策略化歸為定理中各情況的合理性。在更豐富的線上問題中,歷史包含更多資訊,因此單一閾值可能無法描述每一種策略。
總結
租用推遲了承諾,購買則為未來的成本設定了上限。在這個離散模型中,平衡點出現在第 日,給出精確的比值 。對手可以利用算法的確定性購買日,構造出與之匹配的下界時間範圍。
練習
快速檢查
(對 ,分別計算 與 時閾值算法的成本與比值。)
解答 · 答案
當 時,它付出 ,最優成本為 ,比值為一。當 時,它付出 ,最優成本為 ,比值為 。
快速檢查
(當 時會發生甚麼事?)
解答 · 答案
閾值是第一日,所以它立即購買,成本為一。對每個正的時間範圍,離線最優成本都是一;比值為一。
快速檢查
(某確定性算法在 時於第 日購買。利用時間範圍 計算其比值。)
解答 · 答案
它付出 ,最優成本為 ,故比值為 。
快速檢查
(為甚麼從不購買的算法沒有有限的競爭比?)
解答 · 答案
在時間範圍 上它的成本為 ,而當 時最優成本為 。比值 無界增長。