Chapter 4 -- Greedy algorithms ( 2 )

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

Interval Partition

Scenario

\(Let\ \{I(i)=\big[s(i),f(i)\big)\mid i=1,2,3,\cdots,n\}\ is\ a\ set\ of\ requests\ interval.\) \(Partition\ these\ requests\ into\ a\ minimum\ number\ of\ compatible(no\ overlap)\ subsets.\) 給定一個區間，以及 \(n\) 個子區間，試圖將這個子區間分成最少的子集合，子集合內的子區間互不重疊。

要處理這個問題前，我們先定義 \(depth\) 這個名詞。 \(depth\) 指的就是在這些 requests 中，在同一個時間點上最多有幾個 requests 重疊。

（這邊我認為課程中江蕙如教授並沒有講得很清楚，究竟 \(depth\) 指的是同一時間最多重複的 requests 數量? 還是就整個時間軸來看重複率最多的那個重複數量? 舉例來說，如果整個時間軸掃過去，有一個時間點出現了 4 個requests 重複，但有四個時間點出現了 3 個 requests 重複，那 \(depth\) 應該是 3還是4 ?就後面的討論來看，\(depth\) 應該是 4）

Claim : \(depth\) is the least number of partition subset

Proof :

Suppose that \(depth=d\) \(\therefore \exists I_1,I_2,\cdots,I_d\) ，這些子區間會在某一個時間點互相重疊。 \(\Longrightarrow\) 這些子區間就必須要被分配到不同的 subsets 中。 \(\Longrightarrow\) 我們至少就需要 \(d\) 個 subsets。

現在我們有幾個問題 :

  • 我們能不能用 \(O(n\log n)\) 的複雜度找出 \(d\) ?
  • \(d\) 是我們想要找的答案的下界，那有沒有可能 \(d\) 就是答案 ? 怎麼找 ?

如果這兩個問題都能解決，那我們勢必可以確定這樣找出來的答案 \(d\) 一定是最優解。

如何用 \(O(n\log n)\) 的時間複雜度找出 \(depth\) ?

1
2
3
4
5
1. 首先將所有子區間按照 start time 進行排序
2. 製造一個序列 S，是將 start time 與 finish time 混合排序
3. 初始化 d=0 , d-max=0
4. 依照 S 中的順序，遇到 Start time 則 d=d+1，遇到 finish time 則 d=d-1
   並且將至今遇到的最大 d 保存在 d-max 中

整個過程大概可以用下圖來表示

這樣的過程我們可以計算總時間複雜度 :

Step 1. \(O(n\log n)\) Step 2. \(O((2n)\log (2n))=O(n\log n)\) Step 3. \(O(1)\) Step 4. \(O(n)\)

總時間複雜度則為 \(O(n\log n)\)，而且整個複雜度不與所佔的時間總長度相關，即使今天有 request 站了一百萬個時間單位都不影響整個複雜度。

\(d\) 就是最小的 partition number of subsets

1
2
3
4
5
6
7
8
Interval-Partitioning(R):
1.將所有子區間針對 start time進行排序 = {I(1),I(2),...,I(n)}
2.找出 depth = d，並且創造一個 Label set L = {L(1),L(2),...,L(d)}
3.for j from 1 to n :
    排除所有與 I(j) 衝突的 Label
    if 存在不與 I(j) 衝突的 L(i) : 
        將 I(j) 配給 L(i)
    else 先擱置 I(j)

我們一樣用動畫來呈現整個流程較為清楚 :

Correctness of Algorithm

每一個子區間都一定會有 Label

仔細看看上面的 procedure 其實最後一步的 else 似乎不會碰到 ? 的確，這是整個演算法的一個防呆措施，但其實根本不會有「配不到 label」 的情況發生。

假設我們在整個演算法過程中檢查到 \(I(i)\) 這個子區間，而它與前面的 \(t\) 個子區間都有重疊到。根據我們一開始找出來的 \(depth\ d\) 我們可以知道 \(t+1\leq d\)。 ( \(I(i)\) 跟前面 \(t\) 個子區間重疊的深度一定不會超過 \(d\) )

\(\Longrightarrow t\leq d-1\) \(\Longrightarrow\) 檢查到 \(I(i)\) 時一定至少有一個 label 可以跟它搭配 \(\Longrightarrow\) \(I(i)\) 一定可以配到 label，因此 else 的步驟一定不會發生。

每一個 subset 內的子區間必然不會 overlap

\(\forall\) overlapping \(I(i)\) and \(I(j)\) W.L.O.G. ,\(i<j\)

從我們提出的演算法來看，當我們在 \(I(j)\) 這個 iteration 時，\(I(i)\) 已經被處理過了，而且也已經有了一個 Label。此時，在這個 iteration 中的第一步，我們會先排除掉所有衝突的 Label，而 \(I(i)\) 的 Label 勢必會被排除，因此 \(I(j)\) 也絕對不會跟 \(I(i)\) 配在同一個 Label 裡面。

從以上的說明發現，這樣的演算法一定可以做出一個 \(d\) 個 partition subsets ，而且這樣的結果一定是最優解。

Scheduling to Minimize Lateness

Scenario

\(Let\ \{I(i)\ with\ lenth\ t(i)\ and\ deadline\ d(i)\mid i=1,2,3,\cdots,n\}\ is\ a\ set\ of\ requests\ interval.\) \(Scheduling\ these\ requests\ without\ overlapping\ and\ minimize\ maximum\ lateness.\) \(Lateness : I(j)=max\{0,f(i)-d(i)\}\)

給定一個區間，以及 \(n\) 個子區間，這些子區間沒有限定 strat time 及 finish time，但有限制其長度及 deadline，試圖將這個子區間安排順序使這些子區間完全不重複，並且盡可能使延遲 ( finish time 超過 deadline) 最小化。

Criterion ( Greedy Rule )

我們這個問題也一樣先找出 Greedy Rule :

  1. 最短區間優先 ? 若有兩個區間 \(I_1\) : deadline=100, lenth=1 ; \(I_2\) : deadline=10, lenth=10，若以最短區間優先，則我們會先排序 \(I_1\) 再來排序 \(I_2\)，但這樣很明顯地會產生 Lateness=9。但我們排序的方式為 \(I_2\), \(I_1\) ，則 Lateness=0。
  2. 最短餘裕優先 ? 若有兩個區間 \(I_1\) : deadline=2, lenth=1 ; \(I_2\) : deadline=10, lenth=10，我們以最短餘裕優先的方式進行，排序的方式會是 \(I_2,I_1\)，產生的 Lateness=9。但若我們排序方式改為 \(I_1,I_2\) ，則 Lateness可以壓到 1。
  3. Deadline 最早優先 ?

相較於 Interval Scheduling 的 Greedy Rule，這個 Greedy Rule 相對來說比較貼近直覺。

1
2
3
4
5
6
7
8
Min-Lateness(R,s):
// f=solution schedule finish time ; s=start time of the schedule
1. 先將所有子區間依照 deadline 進行 ascending 排序
2. 初始化 f = s
3. for i from 1 to n do
      將 I(i) 分配到 schedule 中，s(i)=f, f(i)=f+t(i)
      f=f(i)
4. return { (s(i),f(i)] | i=1,2,...,n }

這樣的演算法中，我們並不限定必須要從 time=0 開始進行 scheduling，所以我們可以任意給定一個 start time s。

再來比較重要的一個概念是，這個演算法可以確保最後輸出的 solution 中間不會有閒置時間 ( idle time )，但是事實上，一個合理的 optimal solution 是可以容許有 idle time 的。

Correctness of Algorithm

Claim : 一定存在一個最優解中間沒有 idle time

假設我們手中有一個含有 idle time 的 optimal solution，那麼顯而易見的，我們可以將這接閒置時間進行壓縮，讓每一個子區間的頭尾相連，這樣的解也一定會是 optimal solution。

Claim : 任何沒有 inversion 及 idle time 的 schedule，必然擁有相同的 Maximum Lateness

首先我們先定義 inversion : 如果在 schedule 中存在兩個子區間 \(I(i),I(j)\) 滿足 \(s(i)<s(j)\) 但 \(d(j)<d(i)\) 者稱之。白話一點說，一般我們會按照 deadline 來安排順序，deadline 比較早的，我們就會比較早排序，它的 start time 也會比較早，但 inverstion 就是排列順序與 deadline 順序相反的子區間。

兩個沒有 inversion 及 idle time 但卻不同的 schedule 中，不同的部分只會出現在 「相同 deadline,卻不同 start time」的子區間中。如果真的有可能會出現不同的 Lateness 也會出現在這部分。

因此，我們現在只考慮這樣子的 deadline \(d\)，以及有相同 deadline \(d\) 的這些區間。

因為這些區間最後排序的 start time 與總長度勢必都一樣，但又具有相同的 deadline \(d\)，所以不管最後一個被排序的子區間是哪一個，它的 finish time 與 deadline \(d\) 的時間差一定會一樣。

Claim : 一定有一個 optimal solution 沒有 idle time 及 inversion

  1. 一定存在 optimal solution 沒有 idle time : Clearly.
  2. 一定存在 optimal solution 沒有 inversion

假設現在有一個帶有 inversion 的 optimal solution，我們只需考慮出現 inversion 的區間 finish time 都在它們的 deadline 之後。

( 如果 finish time 都在它們的 deadline 之前，就沒有 Lateness 的問題，我們只要直接將兩個區間調換位置即可，不會影響 optimal solution )

考慮到上述的狀況，當我們針對 inversion 的子區間進行調換時，Lateness 勢必會改變，但絕對不會大於原本 inversion 的 Lateness。

所以如果原本已經是 optimal solution，經過這樣的子區間調換後，他也依舊會是 optimal solution。

Theorem : The Min-Lateness(R,s) Algorithm schedule S is optimal.

假設，我們可以找到一個 optimal schedule \(O\) \(\Longrightarrow\) \(Max-Lateness(O)\) is minimal. W.L.O.G. 假設 \(O\) 無 idle time

(Case 1.) 如果 \(O\) 無 inversions : 那麼 \(O\) 與 \(S\) 同樣都是沒有 idle time 且不具 inversions 的 schedules，則兩者具有相同的 max lateness，\(\Longrightarrow Max-Lateness(S)=Max-Lateness(O)\) is minimal.

(Case 2.) 如果 \(O\) 有 inversions : 我們可以經由不斷的 inversion 區間的對調產生一個 Schedule \(O'\)，但從之前的證明過程我們可以知道 \(Max-Lateness(O')\leq Max-Lateness(O)\) \(\Longrightarrow O\) is not optimal. \((\rightarrow\leftarrow)\)

補充

Interval-Graph

前面介紹的三種問題型態，都跟 interval 有關，而其中 interval-partition 又跟 graph 有某種程度上的關聯性。那我們能不能將 interval 問題 轉換為 graph 問題 ?

事實上是可以的。我們將每一個 interval 都視為一個 node，如果有 overlap 的兩個 node 我們就給予一條 edge，這樣便可以將interval 問題 轉換為 graph 問題來去處理。

然而，並非所有 interval 問題都可以藉由 graph 來簡化問題，一般我們在生活中遇到的問題都是複雜且困難的，要想利用 graph 配合 greedy algorithm 來處理基本上都是不可行。

但是，簡單的問題上，或許我們可以從這樣的角度來嘗試看看，畢竟 greedy algorithm 的想法很直覺而且比較簡單。

從時間管理 ( Time-management ) 角度來看 interval 問題

在上圖中，你會怎麼安排你的工作優先順序呢 ?

一般人的做法 (包含我) 或許第一時間是這樣安排的 :

\[ I > III > II > IV \]

但在一般時間管理的角度來看，這樣的安排比較適當 :

\[ I > III > IV > II \]

差別在於 \(II\) 跟 \(IV\) 的順序不同。 時間管理專家 (我沒聽清楚名稱) 認為，如果先從事輕且急的工作，把重且緩的工作排程放在後面，最後這些重且緩的工作會演變成為又重又急的工作，這將在後面造成非常大的時間壓力。