算法導論【線上算法】—The Ski-Rental Problem、The Lost Cow Problem、The Secretary Problem

算法導論【線上算法】

• The Ski-Rental Problem
• • 問題描述
  • 線上算法
  • 證明
• The Lost Cow Problem
• • 問題描述
  • 線上算法
  • 類似問題—尋寶藏
• The Secretary Problem
• • 問題描述
  • 線上算法
  • The Best Possible k

The Ski-Rental Problem

問題描述

• 假設你正在上滑雪課。每節課結束後，你決定（取決于你喜歡的程度、你的骨骼狀況和天氣）是繼續滑雪還是完全停止滑雪。
• 你可以選擇以1美元一次的價格租用滑雪闆，也可以以B美元的價格購買滑雪闆。
• 你是買還是租？
• 如果你事先知道你一生中會滑雪多少次，那麼選擇租還是買就很簡單了。
• 如果你要滑雪超過 B B B次，那就在開始前購買，否則就一直租。該算法的代價為 m i n ( T , B ) min(T,B) min(T,B)。
• 這種對未來了如指掌的政策被稱為離線政策。

線上算法

• 實際上，你不知道你會滑雪多少次。你該怎麼辦？
• 線上政策是：取一個數字k，這樣在租用k−1次後，您将購買滑雪闆（就在第k次滑雪之前）。
• 如果我們取 k = B k=B k=B，那麼可以保證我們支付不會超過離線政策成本兩倍的費用
• 例如：假設B=7美元，那麼，在6次租金之後，你就買了。總付款：6+7=13$

證明

最壞情況下， k = B k=B k=B，我們選擇在滑雪次數 T = k − 1 T=k-1 T=k−1次後再也不滑雪，那麼線上算法的總費用為 B − 1 + B = 2 B − 1 B-1+B=2B-1 B−1+B=2B−1，而離線算法取得的最優解為 m i n ( T , B ) = B min(T,B)=B min(T,B)=B，此時競争比為 2 B − 1 B = 2 − 1 B \cfrac{2B-1}{B}=2-\cfrac{1}{B} B2B−1​=2−B1​，則我們說這個政策是 ( 2 − 1 B ) (2-\cfrac{1}{B}) (2−B1​)競争的

The Lost Cow Problem

問題描述

• Old McDonald失去了他最喜歡的奶牛。最後一次看到它朝着通向兩條無限道路的路口行進。沒有一位目擊者能說出奶牛是選擇了左邊還是右邊的路線。

• 

線上算法

• 線上算法是9-competitive的，換句話說：在找到奶牛之前可能經過的距離最多是最佳離線算法（知道奶牛在哪裡）距離的9倍
• 最壞的情況是，他發現奶牛的距離比他上次在這一側搜尋的距離稍遠
• 是以， O P T = 2 j + ε OPT=2j+ε OPT=2j+ε，其中 j = j= j=疊代次數， ε ε ε是某個小距離。然後

• 

• 僞代碼如下：

類似問題—尋寶藏

m m m條路編号為 1 , 2 , 3... m 1,2,3...m 1,2,3...m，從第一條路開始尋找，初始尋找距離為 d = 1 d=1 d=1，如果在這個距離内找到了寶藏則結束尋找，沒找到則尋找距離翻倍，切換至尋找下一條路徑，路徑編号對 m m m取模，保證每次尋找的路徑都是合法的，直到找到寶藏。

Treasure(m)
d = 1;current side = 1
while true do
	Walk distance d on current side
        if find treasure then
            exit
        else
            d = 2d
            current side = (current side+1)%m
            return to starting point
           

該算法的競争比為 O ( m ) O(m) O(m)

證明：

​ 最壞的情況是，發現寶藏的距離比上次在這條路上搜尋的距離稍遠一點點，是以，最優解為 O P T ： 2 j + ε OPT：2^j +ε OPT：2j+ε，其中 j j j=疊代次數， ε ε ε是某個小距離。則：

C o s t O P T = 2 j + ε > 2 j        C o s t O N = m ( 1 + 2 + 4 + . . . + 2 j + 1 ) + 2 j + ε = m ⋅ 2 j + 2 + 2 j + ε = ( 4 m + 1 ) ⋅ 2 j + ε < ( 4 m + 1 ) ⋅ C o s t O P T \begin{aligned} Cost OPT &= 2^j +ε>2^j\\ \ \ \ \ \ \ Cost ON&= m(1+2+4+...+2^{j+1})+2^j +ε\\ &= m · 2^{j+2} +2^j +ε = (4m+1)· 2^j +ε < (4m+1) · Cost OPT \end{aligned} CostOPT      CostON​=2j+ε>2j=m(1+2+4+...+2j+1)+2j+ε=m⋅2j+2+2j+ε=(4m+1)⋅2j+ε<(4m+1)⋅CostOPT​

是以競争比為 O ( 4 m + 1 ) = O ( m ) O(4m+1)=O(m) O(4m+1)=O(m)

The Secretary Problem

問題描述

• 我們有

  n

  位候選人（可能是求職者或可能的婚姻伴侶）。
• 我們的目标是選擇最好的候選人。
• 假設候選人可以從最好到最壞完全排序，沒有任何聯系。
• 候選人以随機順序依次到達。
• 我們隻能在候選人到達時确定他們的相對排名。
• 我們不能觀察絕對等級。
• 每次面試後，我們必須立即接受或拒絕申請人。
• 候選人一旦被拒絕，就不能被召回。
• 一旦候選人被錄取，我們就停止面試。

線上算法

• 已知候選人數

  n

• 線上政策在遇到第

  i

  位候選人後，我們能夠給出分數

  score(i)

  。
• 選擇一個正整數

  k<n

  ，面試并拒絕前

  k

  位候選人。
• 繼續面試剩下的

  n-k

  位，并接受第一位得分高于前

  k

  位候選人的候選人。
• 如果最高分在第一批面試的

  k

  人裡，那麼我們必須接受第

  n

  位即最後一位申請人
• 僞代碼：

  

The Best Possible k

結論：如果我們在 k = n e k=\cfrac{n}{e} k=en​的情況下實施我們的政策，我們将以至少 1 e \cfrac{1}{e} e1​的機率成功雇傭我們最合格的申請人