Chapter 4 -- Greedy algorithms ( 1 )

發表於 更新於 分類於 ， 閱讀次數： Disqus：

Greedy algorithm

當我們在設計演算法時，往往都是一個一個步驟累積而成，而每一個步驟往往都必須要對某些狀況做決定。Greedy Algorithm 在每一個步驟都選擇「當下」「最好」的決定。也就是說，Greedy Algorithm 在每一步驟下都必須要去試著最優化我們所訂定的規範 (criterion)。而且，這樣的演算法不會回頭、不會反悔、不會猶豫。

這樣短視近利的方式，直覺且快速，因此適用於各種問題上。雖然說在某些問題上，Greedt Algorithm 可能可以得到最佳解，但大部分狀況，solution 都不會是最好的。

因此如何證明 Greedy Algorithm 在這一小部分問題上的確可以得到最佳解，將是最大的挑戰之一。一般來說，我們可以利用下列兩種方式來進行證明 :

  1. The Greedy Algorithm stays ahead. 利用 Greedy Algorithm 可以一路最佳化。
  2. The exchange argument. 預設有一個最佳解，將其中與 Greedy Algorithm 不符的 criterions 交換，試圖證明這樣交換後仍然可得最優解。

Interval Scheduling

Scenario

\(Let\ \{I(i)=\big[s(i),f(i)\big)\mid i=1,2,3,\cdots,n\}\ is\ a\ set\ of\ requests\ interval.\) \(Find\ a\ compatible(no\ overlap)\ requests\ with\ maximim\ size.\) 給定一個區間，以及 \(n\) 個子區間，試圖在這個區間中找出最多不重複的子區間。

Criterion ( Greedy Rule )

前面有提到，Greedy Algorithm 在每一步驟下都必須要去試著最優化我們所訂定的規範 (criterion)，在 Interval Scheduling 問題來說，就是先選出一個在當下比較「好的 interval」，刪除掉 overlap 的選擇，之後再選擇一個「好的 interval」.....，一值重複下去。

或許我們可以思考一下，最好的 interval 的可能有哪些 :

  1. 最早開始 ?
  2. 最短區間 ?
  3. 最少衝突 ?
  4. 最晚結束 ?

上面四種方式，最直覺的大概數「最少衝突」這一種狀況，在這並非最優解。Greedy Algorithm 在選取條件上，往往不是那麼直覺，這也是比較需要花時間思考的部分。

最早結束的 interval 才是每一輪選擇的最好條件，因為大區間的起始固定，因此越早結束的子區間也強制其長度，另一方面也可以越早將資源放出來給其他子區間來使用。

1
2
3
4
5
6
7
8
9
Interval-Scheduling(R)
# R是當下可選擇的requests set,而 A 是我們選擇的 requsts set
1. A=∅
2. while R is not empty then do
       choose I(i) with minimum f(i)
       A=A+{I(i)}
       X={ I(j)| I(j) is not compatible with I(i) }
       R=R-{I(i)}-X
3. return A

Greedy Algorithm 在演算法中很容易實現，主要也是因為其架構幾乎都是一個 loop。

Correctness of Algorithm

Compatible

因為我們每一次個 loop 都會刪除 overlap 的選擇，再去下一個 loop 中挑選一個 request 放進 \(A\) 中，因此我們可以確定 \(A\) 中的 requests 必然都是 compatible。

Maximum set

Cliam : \(O\) is an optimal solution, then \(|A|=|O|\)

  1. 這裡我們先提出一個引理 : \(A=\{I(i_1),I(i_2),\cdots,I(i_n)\}\) and \(O=\{I(j_1),I(j_2),\cdots,I(j_m)\},where\ f(j_u)\leq f(j_v)\ when\ u\leq v\Longrightarrow \forall\ k\leq n,\ f(i_k)\leq f(j_k)\)

Step1. \(k=1\Longrightarrow f(i_1)\leq f(j_1)\) 成立 (\(\because i_1\) 是所有 requests 中結束時間最早的)

Step2. 假設 \(k=r\) 時亦成立 \(\Longrightarrow f(i_r)\leq f(j_r)\) \(\because I(j_r)\) 與 \(I(j_{r+1})\) 為 compatible ，且 \(I(i_r)\) 與 \(I(i_{r+1})\) 為 compatible \(\therefore I(i_r)\) 與 \(I(i_{r+1})、I(j_{r+1})\) 均為 compatible \(\Longrightarrow\) 在 \(r+1\) 這個 loop 中，\(R\) 裡面同時存在 \(I(i_{r+1})、I(j_{r+1})\) \(\Longrightarrow f(i_{r+1})\leq f(j_{r+1})\)

  1. Suppose to the contrary that \(A\) is not optimal solution. \(\Longrightarrow |A|=n<m= |O|\) \(\Longrightarrow \exists\ I(j_{n+1})\in O\subseteq R\) s.t. \(I(j_{n+1})\)與\(I(j_{n})\) compatible， 且\(f(i_n)<s(j_{n+1})\) \(\Longrightarrow\) 當 \(I(i_n)\) 被挑出來放進 \(A\) 後，\(R\) 裡面至少還有一個 \(I(j_{n+1})\)，整個 loop 不會結束。 \(\Longrightarrow |A|\geq n+1\) (\(\rightarrow\leftarrow\))

Complexity

我們在進行上面的演算法時，由於我們必須要比較 finish time，所以我們會先對 \(R\) 做一次排序，複雜度為 \(O(n\log n)\) (課程還沒講過這部分，暫時先了解即可)。

之後我們每一次 loop 挑出排序後的 \(R\) 最前面的 interval 後，都必須要重複查找 \(R\) 中是否有 overlap 的 intervals 進行刪除，總共的複雜度是 \(O(n^2)\)。(裡面必然有一些 interval 會在不同 loop 中被重複查找)

由於排序的複雜度不可避免，我們便想這邊利用一些方式來減少整個 loop 的複雜度，讓整個演算法複雜度壓到只有排序這邊產生的 \(O(n\log n)\) 。

概念就是 每一次對 \(R\) 進行 overlap interval 刪除時，不要全部刪除

  • 先建立一個 \(S\) 用來儲存每一個 interval 的 start time。
  • 每一輪從 \(R\) 挑出最前面我們要的 interval \(I(i_k)\) 後，按照 \(R\) 排序，僅刪除 \(s(i_l)<f(i_k)\) 的 interval \(I(i_l)\)，遇到 \(s(i_l)>f(i_k)\) 即停止。這樣可以確保所有的 intervals 在全部 loop 結束時只會被查找過一次。也就是說，整個 loop 查找完所花的時間複雜度只有 \(O(n)\)。

下列動畫可以試著解釋這整個演算法流程 :

這樣不但可以減少每一個 loop 的檢索時間，還可以確保前面該刪除沒刪除的 intervals 一定會在後面的 loop 被刪掉。

藉由這樣的方式，我們便可以將整體的時間複雜度壓到只剩下 \(O(n\log n)\)。