本文為交通大學開放式課程上課心得整理。
當我們要解決一個問題時，會先制定步驟一步一步往下走，在執行步驟時，依據當下最好的選擇來決定下一個步驟，即是貪婪演算法的概念。由於貪婪演算法做完決定之後便不會再回頭檢視選擇，因此要如何讓演算法判定當下最好的結果（最佳解），便是設計演算法時需要思考的重點。
此外，不是每個問題都會有最佳解，因此貪婪演算法的解題品質普遍較差；但在某些問題中最佳解的確存在，所以此處的另一個挑戰便是：給定一個方法，是否能以貪婪演算法找出最佳解。
貪婪演算法常用的證明方式有兩種：
・The Greedy Algorithm stays ahead：演算法執行過程中，所有決定都是最好的。
・An exchange argument：先假設有人提出最佳解，將該最佳解中不符合演算法模型的地方挖掉，替換成符合的，並證明結果一樣即可。此方法在證明中較常用到。
以下介紹幾種問題的證明：
Interval Scheduling Problem
這是一個很常見的問題，例如早期的 CPU 都是單核心，為了迅速完成使用者的指令，排程就變得很重要。
Greedy Rule
如前所述，貪婪演算法重視最佳選擇，因此如何規範選擇條件（Greedy Rule）就很重要。
選擇條件的方法有四種：
・Earliest start time：先開始的人先選
・Shortest interval：選擇占用時間最短的任務
・Fewest conflicts：與其他任務執行衝突最小者
・Earliest finish time：最早結束的（最佳解）
此處使用 Algorithm stays ahead 的證明方法：假設有一個最佳解 O 以及一個透過貪婪演算法找出的最佳解 A，將 O 與 A 各自分成幾個部分，只要能一步步證明每個部分的解 A 都優於 O 即可：
・A 的分解為 I1 到 Ik 的 part，以執行時間結束早晚為基準排序。
・O 一樣分解為 J1 到 Jm 的 part，因為不是我們自己寫出來的演算法，不確定分類條件，但一樣可以以執行時間結束早晚為基準排序。
由於 A 是以執行時間早晚來決定順序，因此 I1 一定小於等於 J1。假設 f(I r-1) ≤ f(J r-1) 成立，由於 O 是一個 compatible set，因此 J r-1 的結束時間一定小於等於 J r 的開始時間；當 I r-1 被選取的當下，J r 還在待選 set 中， 當執行到 Ir 時亦同，可以推知 f(I r) ≤ f(J)。
證明完大小關係之後，接下來要開始比較兩個集合中 k 與 m 個數的大小。這邊使用反證法：先假設 A 不是最佳解，則最佳解 O 會包含比較多的 request 數，即 m > k。根據前面的證明可以得知 f(j k) ≤ f(j k +1)，且 j k+1 一定在 j k 之後，而 m > k，因此 m 會有更多 request；而 i k 會比 j k 早結束，因此 f(i k) ≤ f(j k+1)，此時當 i k 被選取時，待選 set 中至少還有 j k − 1 在裡面，此時演算法還會繼續執行直到待選集合為空，這就代表至少要有 i k+1 的存在，與假設矛盾，因此得證 A 為最佳解。
貪婪演算法的時間複雜度會落在 O(n ** 2)，為了改善處理速度，可以再新增一個存放開始時間的 set，減少比對時間，處理完成的時間複雜度會降到 O(n log n)。
Interval Partitioning
Interval Partitioning 也稱為 Interval Coloring，對每個區隔做塗色。一樣是 CPU，當我們有複數的核心（或是複數台機器）可以同時處理問題時，要如何使用最少的資源處理完所有的程序？
這個問題的核心概念自然就是將所有要處理的程序分成最少的組別完成。在思考這個問題之前，我們先要探討另一個很像的問題：可使用的 resource 是否有下限？此時要介紹另一個概念：深度（depth）。
深度在這邊指的是所有程序之間重疊（overlap）的最大數目，也等於是 resource 的下限。
・在 O(n log n) 的時間內找到 d：由於 overlap 的程度僅與程序的開始時間以及結束時間有關，因此可以針對開始與結束的時間做排序。排序完成之後，便從頭開始掃描，將結果分別放入兩個變數中：d（深度的變化）、dmax（最後的答案）。序列掃描過程中，如果遇到 starting time 便在 d 中加一， finish time 便減一，同時將結果更新到 dmax 中。
此計算要注意一個狀況：假設在程序中有一個程序結束、同時有另一個程序開始，因為前者的結束時間與後者的開始時間相同，此時結束時間的程序排位順序必須優於開始時間，否則計算結果會出錯。
d 預告的是執行所有程序所需的下限，但在實際上是有能使用超過下限的資源去執行，要如何盡量將資源壓在下限中完成？思考流程如下：
・假設一個處理程序的深度為 d，因此需要使用 d 的資源完成執行程序
・假設處理程序為 I1 到 In，先針對 I1 到 In 以開始時間為基準做排序
・將每個程序放進適當的資源中執行，彼此互相衝突的程序必須被放進不一樣的資源中
該演算法的證明如下：
・首先假設每個程序都會進到一個執行 label ，並有一個程序 Ij 與前面的 t 個程序之間彼此執行時間衝突：由前面的描述，知道 t + 1 一定 ≤ d，由於 Ij 與 t − 1 衝突，故可知 t ≤ d − 1，代表一定有一個 label 可以放入 Ij。
・再來假設兩個程序 Ii 與 Ij 互相衝突，且 i < j，故當程式處理到 Ij 時，Ii 已經得到執行 label，同時由於 i j 互相衝突，Ij 不可能進入 Ii 所在的 label，因此 Ii、Ij 不會出現在同一 label 裡面。
綜合上述兩點，可以得知：每個執行緒都會進到某個 label 中，同時互相衝突的執行緒不會出現在同一 label，故演算法會回傳合法解；同時，由於演算法使用的資源大小設定於 d 上，而在執行此程序時，所需資源必定大於等於 d，故該演算法為最佳解。
如果演算法能在下限內執行完程序，原則上就可以保證此演算法為最佳解。
Scheduling to Minimize Lateness
這個問題也與 interval 相關，也是要對執行緒作排程，同時最小化此排程的時間延遲。在這個問題中，每個執行緒都有 deadline，演算法必須決定何時執行哪個程序，讓程序延遲執行的程度降到最小。
上圖範例的目的是取最大延遲量，即：當全部的程序都延遲一時，和只有一個程序延遲一的結果相同。
Greedy Rule
這個題目的幾個可能操作方法如下：
・Shortest interval first：先處理執行時間最短者。
・Smallest slack：假設程序的執行時間為 ti，deadline 為 di，取 di − ti 最小者。
・Earliest deadline first：從 deadline 最前面的程序開始處理（最佳解）。
這裡有幾個問題可以探討：
・No Idle Time：從上圖可以看出，演算法在處理程序時，是一個緊接著一個在執行的，中間沒有空窗時間。
假設演算法已找到一個最佳解，而最佳解執行程序中間有休息時間，將休息時間壓縮之後執行依然會是最佳解，並不會因為休息時間消失而改變。
・No Inversions：在這個問題中，我們會使用 exchange argument 的方法證明，因此這裡要先提出 inversion 的概念。在這個問題中，我們會用 deadline 先後當作標準排序，因此當某個執行緒的 deadline 比較早結束，但是在執行上卻比較晚開始時，這種狀況便稱為 inversion；演算法完成的所有排程中只要沒有 inversion 且沒有 Idle time，一定會有相同的最大延遲時間（maximum lateness）。
由此可以得知，此問題演算法可以找出一個最佳解，裡面不會有 inversion 與 Idle time，證明如下：
・假設有一個最佳解 O 沒有 Idle time 但是程序 i 與 j 有 inversion（dj < di），在此我們將這兩個程序交換，得到一個沒有 inversion 的新排程。
・i 與 j 交換之後，兩者的 lateness（di − fi、dj − fj）會縮小，此時雖然 i 因為執行時間往後移，但整體上來說 lateness 還是會縮小，故不會有影響。
貪婪演算法是 step by step 找出最佳解的演算法，能否找出最佳解的基礎來自於選擇時的判斷條件。由於大部分的情況下，無法使用單純的規則去判定最佳選擇，因此在務實上貪婪演算法的使用空間較小，但反過來說，如果能找到適合的選擇條件，貪婪演算法就能以快速的計算解決問題。
