# Lecture 04: Greedy algorithm

> 課程內容 : 交通大學開放式課程 交大電機 江蕙如教授
> 參考書目 : Algorithm Design(2006), J. Kleinberg and E. Tardos

## Content

* [Interval scheduling: the greedy algorithm stays ahead](#Interval-scheduling-the-greedy-algorithm-stays-ahead)
* [1. The greedy algorithm stays ahead](#1-The-greedy-algorithm-stays-ahead)
* [Interval partitioning](#Interval-partitioning)
* [1. Greedy](#1-Greedy)
* [2. Optimality](#2-Optimality)
* [Scheduling to minimize lateness: an exchange argument](#Scheduling-to-minimize-lateness-an-exchange-argument)
* [1. Greedy for minimize lateness](#1-Greedy-for-minimize-lateness)
* [2. Exchange argument](#2-Exchange-argument)
* [Shortest paths](#Shortest-paths)
* [1. Implement](#1-Implement)
* [The minimum spanning tree problem](#The-minimum-spanning-tree-problem)
* [1. Kruskal's algorithm](#1-Kruskals-algorithm)
* [2. Prim's algorithm](#2-Prims-algorithm)
* [3. Reverse-delete algorithm](#3-Reverse-delete-algorithm)
* [Implement Kruskal's algorithm: union-find](Implement-Kruskals-algorithm-union-find)
* [1. Union-Find data structure](#1-Union-Find-data-structure)
* [2. Implement Kruskal's algorithm](#2-Implement-Kruskals-algorithm)

## Greedy algorithm

貪婪演算法(greedy algorithm)是一種短視近利的方法，每個步驟都會做一個決定，並根據當下情況選擇最好的解，且做完決定之後不會再回頭修改。

Greedy algorithm 幾乎適用於所有問題，且大多是用 loop 實作，但有時候得到的不見得是最佳解(Ex: 與 DP 相關的問題)。

證明 greedy algorithm 是最佳解法比較困難，有兩種常見證明方式(但第 2 種較常用):

* Stays ahead
* 證明 greedy algorithm 的選擇方法會一路領先
* Exchange argument
* 最佳解集中可能有部分不合 greedy algorithm，所以把不符合 greedy 的刪掉並加入符合 greedy 的解

## Interval scheduling: the greedy algorithm stays ahead

以 interval scheduling problem 為例(類似 CPU 排程)

> Question description:
> * Given
> * 給定 $n$ 個 interval/request 的集合 $\{1, 2, ..., n\}$
> * 每個 interval $i$ 都有一個開始時間 $s(i)$ 與結束時間 $f(i)$
> * Goal
> * 找到一個最大且不重疊的 interval set

如下圖所示， greedy algorithm 的最佳解為 $\{2, 5, 8\}$。


因為 greedy algorithm 在每個當下都會選擇一個最佳解，而最佳解的選擇標準(criterion)稱為 greedy rule。

以 interval scheduling 為例:

* 使用一個 simple rule/greedy rule 選擇第一個 interval $i_1$
* 一旦 $i_1$ 被選擇，刪除其他與 $i_1$ 重疊的 interval
* 直到看過所有的 interval 為止

在 interval scheduling 中，simple/greedy rule 有 4 種選擇方式

* 最早開始的先選(earliest start time)
* 佔用時間最短的先選(shorest interval)
* 最少重疊的先選(fewest conflict)
* 最早結束的先選(earliest finish time)

最好的 greedy rule 是第 4 種，前三個都能夠找到反例(如下圖)，因為越早結束的 request/interval 能夠越早釋放資源。

根據第 4 個 greedy rule 所設計的 greedy algorithm 如下:

1. 先依照 finish time 排序
2. 選擇最早結束的 interval $i_r$
3. 扣掉與 $i_r$ 重疊的(not compatible)
4. 重回第 2. 步

> [!Tip] **Algorithm:** interval scheduling
> 

第 5 行刪除重疊 interval 時，只要刪除下一個會與 $i_r$ 重疊的即可，不用急著搜索整個 interval set 刪除全部可能重疊的，因為這些剩餘重疊部分會在之後的 interval 討論中被刪除。

### 1. The greedy algorithm stays ahead

假設 $O$ 是一個最佳解集合，$A$ 是透過 greedy algorithm 找到的解集合，只要證明 $|A| = |O|$ 就可說明 greedy algorithm 找到的方法是最佳解。

Greedy algorithm 的 stays ahead 性質說明過程中的每個選擇都會不斷領先直到演算法結束，可用此性質說明 greedy algorithm 的解是最佳解。

> [!Note] **Thm.** The greedy algorithm stays ahead
> Let $A = \{i_1, ..., i_k\}$ be the output of the greedy algorithm in the order they were add. Let $O = \{j_1, j_m\}$ be the optimal solution in the ascending order of start/finish time.
>
> Then for all indices $r \le k$, we have $f(i_r) \le f(j_r)$.

**Proof by mathmatical induction:**

* 已知 $r = 1$ 時，$f(i_1) \le f(j_1)$
* 貪婪解集 $A$ 是基於 greedy algorithm 挑選出來的集合，所以 $i_1$ 會是所有 interval 中最早結束的
* 最佳解集 $O$ 中的 $j_1$ 只能保證在某個解中是最早結束的
* 假設 $r - 1$ 時 $f(i_{r-1}) \le f(j_{r-1})$
* 因為 $O$ 是最佳解集合，所以 $O$ 中的所有 interval 都不會重疊，所以可知 $f(j_{r-1}) \le s(j_r)$
* 因此 $f(i_{r-1}) \le f(j_{r-1}) \le s(j_r)$
* 這表示當我們根據選擇將 $i_{r-1}$ 加到 $A$ 且刪除與 $i_{r-1}$ 重疊的 interval 後，還會有一個 $j_r \in R$ 的開始時間大於 $i_{r-1}$ 的結束時間
* 當選擇 $i_r$ 後可得 $f(i_r) \le f(j_r)$

> [!Note] **Thm.** The greedy algorithm returns an optimal set A

**Proof:** 暫略

## Interval partitioning
類似 interval scheduling 的問題，但考慮多個 resource。

> Question description
> * Given
> * 給定 $n$ 個 request/interval 的集合 $\{i_1, i_2, ..., i_n\}$
> * 每個 interval $i_r$ 都有一個開始時間 $s(i)$ 與結束時間 $f(i)$
> * Goal
> * 將這些 interval 分割成的重疊子集，且每個子集對應到一個 reosurce
> * 最小化重疊子集的個數

以下圖左為例，將這些 interval 分割後最少可由 3 個不同的 resource 完成(下右圖)，每個 resource 對應到一種顏色。


因為 interval 互有重疊，所以要考慮重疊情況時至少會需要多少個 resource 才可以完成重疊時的 interval。

> [!Note] **Def.** Depth
> 深度(depth)指的是在某個時間點會經過的最大 interval 數量 i.e., 最大重疊數。以上圖左為例， $depth = 3$。

雖然 $depth = d$ 是完成 interval partition 所需要的花費的最少資源下限(lower bound)，但其實 $depth = d$ 同時也是此問題的最佳解(optimal)

### 1. Greedy

將 resource 編號(label)為 $\{1, 2, ..., d\}$，且分配不同的 resource/label 給重疊的 interval。

* Greedy rule
* 盡量使用現有資源 $\{1, 2, ..., d\}$
* 分配資源時選擇可用資源中最早結束的

> [!Tip] **Algorithm:** Interval partition
> 

第 3 行到第 5 行是 greedy rule 的部分，以下一個 interval 的開始時間 $s(I_j)$ 與已經分配的 label 的結束時間 $f(label_i)$ 比較

* 若 $s(I_j) \ge f(label_i)$ 表示 $I_j$ 與 $label_i$ 沒有重疊，可以使用 $label_i$
* 若 $s(I_j) < f(label_i)$ 表示 $I_j$ 與 $label_i$ 重疊，選擇其他 label 使用

<!--p.17圖重繪-->

### 2. Optimality

為何這個 greedt rule 能保證最佳解？

> [!Note] **Thm.**
> The greedy algorithm assigns every interval a label, and no two overlapping intervals receive the same label

**Proof**:
(1) Claim: 所有 interval 都會被標到/分配到一個 resource

* 假設 interval $I_j$ 與前 $t$ 個 interval 重疊 $\{I_1, I_2, ..., I_t, I_j\}$
* 表示這 $t + 1$ 個 interval 會同時經過某個時間點，並設此時間點為 $s(I_j)$
* 根據 depth 的定義可知 $t + 1 < d \Rightarrow t < d - 1$
* 表示至少有一個 label/resource 還沒用到可以分配給 $I_j$

(2) Claim: 不會有任意兩個重疊的 interval 被分到同樣的 label/resource

* 假設任意兩個 interval $I_i$ 與 $I_j$ 且 $i < j$
* 當考慮 $I_j$ 的時候(line 2)，根據 algorithm 的流程此時 $I_i$ 已經被排除(line 3)
* 因此不會有兩個重疊的 interval 分到相同的 label/reosurce

因為是用 $depth = d$ 作為 lower bound 假設，所以最佳解就是 $d$。

## Scheduling to minimize lateness: an exchange argument

再次以 interval scheduling 為例，但對每個 request/interval 添加 deadline

> Question description
> * Given
> * 給定一個 resource 以及 $n$ 個 request/interval 的集合 $\{1, 2, ..., n\}$
> * 每個 interval/request $I_i$ 都有一個長度 $t_i$ 與 deadline $d_i$
> * Goal
> * 對所有 interval 排程，使得所有 interval 不重疊且最小的延遲(lateness)時間
> * Lateness $L_i = max\{0, f(i)-d_i\}$

如下圖，每個 interval(綠) 都有一個對應的 deadline，經過排程後的 interval(紅) 的最大延遲時間是 = 1


### 1. Greedy for minimize lateness

考慮 3 種 greedy rule:

* 容易完成的先做(shortest interval first)
* 以 interval 的長度 $t_i$ 排序後依序完成
* 越級的先做(smallest slack)
* 以 $d_i - t_i$ 的值排序後依序完成
* 越趕的先做(earliest deadline first)
* 以 $d_i$ 排序後依序完成

解果是第 3 種才可得到最佳解，前兩個 greedy rule 的反例如下圖


> [!Tip] **Algorithm:** Minumize lateness
> 

在第 4 行與第 5 行的時候可以保證這個 greedy rule 中所有的 interval 不會有 idle time，因為 interval $I_i$ 的開始時間 $s(i) = f$ 是前一個 interval $I_{i-1}$ 的結束時間。


### 2. Exchange argument

> [!Note] Exchange argument
> Gradually transform an optimal solution to the one found by the greedy algorithm without hurting its quality.

假設有一組 optimal solution，可以透過交換(exchange)的方式將其一步一步替換成符合 greedy rule 的解。透過 minimize lateness 問題和以下 3 個定理說明 exchange argument 是對的。

以 minimize lateness problem 和我們使用的 greedy rule: earliest deadline first 為例，最佳解中不符合 greedy rule 的情況稱為 inversion: 給定兩個 interval $i$ 與 $j$ 使得

* $i$ 比 $j$ 先執行 $s(i) < s(j)$
* 但 $i$ 的 deaeline 卻比較晚 $d_j < d_i$

> [!Note] **Thm.** No inversions
> All schedule without inversions and without idle time have the same maximum latness

**Proof:**
對兩個沒有 idle time 和 inversion 的不同排程方法，在相同的 deadline 之下每組 deadline 中 interval 的順序可能不同。因為 interval 是連續安排的，所以同組 deadline 中 interval 的順序不會影響 lateness，因此可以任意交換位置

> [!Note] **Them.** Optimality
> There is an optimal schedule with no inversions and no idle time

**Proof:** 暫略

> [!Note] **Thm.** optimality: exchange argument
> The greedy schedule S is optimal

**Proof:** 暫略

> [!Caution]
> 但這邊的證明方式都有點不明所以，看不太懂到底要說明什麼事情以前每個證明間的前後關係

## Shortest paths

> Question description
> * Given
> * 給定一個 directed graph $G = (V, E)$
> * 每個 edge $e = (u, v) \in E$, 有一個長度/時間/成本 $l_e \ge 0$
> * 給定一個起點 $s$
> * Goal
> * 找出從起點 $s$ 到其他點的最短距離

Greedy rule: 從起點開始出發，每一次的路徑選擇都去尋找與目前圖中的節點距離最短的邊長。
依照這個方法找到的最短路經稱為 Dijkstra's algorithm

> [!Tip] **Algorithm:** Dijkstra's algorithm
> * `S` 表示已經算好最短距離的點，不會再改變
> * `d(u)` 表示從 `s` 到 `u` 的最短距離，每個點都有一個 `d(u)` 值計算完 `d(u)` 值的節點 `u` 會加入 `S` 中
> * 初始狀況只會有一個起點 $s \in S$，且 `d(s) = 0` 表示自己到自己的距離
> 

Line 3 與 Line 4 是 Dijkstra's algorithm 的精華，也是實現 greedy rule 的方法。

* 選定一個點 $v \notin S$
* 從 $S$ 中的某個點 u 出發，透過一條 edge $e = (u, v)$ 到達選定的節點 $v$
* 若 $s$ to $v$ 的距離($d(u)+l_e$)有最小值
* 把 $v$ 加到 $S$ 中
* 更新 $d(v)$ 值

以下圖為例，從 $s$ 點開始出發:

<img src="https://hackmd.io/_uploads/SkT0Zuaqkx.png" width=400>

* s to u: 找到點 $u$ 使得 $d(s) + l_{(s, u)}$ 有最小值 1，此持 $d(u) = 1$
* u to x: 找到點 $x$ 使得 $d(x) + l_{(u, x)}$ 有最小值 2，此時 $d(x) = 2$
* x to y: 找到點 $y$ 使得 $d(x) + l_{(x, y)}$ 有最小值 3，此時 $d(y) = 3$
* x to z: 找到點 $z$ 使得 $d(x) + l_{(x, z)}$ 有最小值 4，此時 $d(z) = 4$
* 因為 y 沒有下一個相鄰節點

依此類推可以建構出從 $s$ 到所有點的最短距離

> [!Warning]
> Dijkstra's algorithm 的前提是所有 edge 都必須是非負的權重。

### 1. Implement

但 Line 3 與 Line 4 的實作細節上太麻煩。原始版本是以 edge 出發對 edge 最佳化取最小值，但複雜度太高。所以改成從點的角度出發。

必須 maintin 每個尚未選入 $S$ 的節點 $v$ 的 $d'(v)$ 值，且 $d'(v)$ 值會隨著迭代過程不斷下降。一開始假設所有點的 $d'(v) = \infty$，每次迭代過程中挑最小 $d'(v)$(使用 min priority queue/min heap)。見下圖。

(深色節點表示已經確認最小距離的節點)

* 每個點中的數字 = 當下從起點到它的距離，且此距離會存在 min heap 中
* 每此從 min heap 中取出一個最小距離為 $d'(u)$ 的節點 u 並更新 $d(u) = d'(u)$
* 再對此最小距離節點 $u$ 的相鄰節點 $v$ 更新 $d'(v)$ 距離，更新後的 $d'(v)$ 再放入 min heap 中

## The minimum spanning tree problem

> Question description
> * Given
> * 給定一個 undirected graph $G = (V, E)$
> * 對每一個 edge $e = (u, v) \in E$ 使得
> * edge 的長度/權重/成本 c_e \ge 0
> * Goal
> * 找到一個 $E$ 的子集 $T \subseteq E$ 使得
> * Subgraph $(V, T)$ 是 connected 且
> * 總成本 $\Sigma_{e \in E}\ c_e$ 最小

如下圖所示，原圖是一個 connected cycle graph，只取某些 edges 後可找到一個 subgraph 覆蓋所有點且 edge 的總長度最小。此子圖稱為 minimum spanning tree (MST)。


建構 minumum spanning tree 有 3 種方式，每種方式都是依照 greedy algorithm 找到的最佳解，但 greedy rule 不同:

* Prim's algorithm
* Kruskal's algorithm
* Reverse-delete

### 1. Kruskal's algorithm

Step-by-step:

* 從 $T = \{\}$ 開始
* 將 edges 依照 cost 由小到大排序，並從 cost 小的開始連接
* 每次將一個 edge 插入至 T 中且不會形成 cycle

<img src="https://hackmd.io/_uploads/B1D5Usgjye.png" width=500>

(數字編號表示加入邊的順序，綠色線段表示加入過程會形成 cycle 所以刪除，最後的 MST 為紅色連線)

> [!Tip] **Algorithm:** Kruskal
> * 將 edge 依照遞增排序$\{e_1, ..., e_m\}$
> * $T = \{\} \in E$
> 

每個點屬於不同的 tree，加 edge 的過程只要把產生 cycle 就可以把 edge 加入至 T。

> [!Important] Kruskal's algorithm v.s. Prim's algorithm
> Kriskal's algorithm 加入 edges 的過程中，每個節點可視為一個小樹，連接 edge 的過程相當於把多個小樹合併成一個大樹。

### 2. Prim's algorithm

Step-by-step:

* 從任意節點 $s$ 開始，將節點 $s$ 視為一個小樹 $T$
* 從 $s$ 開始往外擴張讓 $T$ 成長
* 每次迭代的過程從現在的小樹 $T$ 往外看尋找最小 cost 的 edges
* 且 edge 的其中一個節點必須落在 $T$ 之中


> [!Tip] **Algorithm:** Prim
> * `S` 儲存已經探索過的節點
> * edge $e = (u, v)$ 的權重為 $c_e$，其中 $u \in S$
> 

因為 Prim's algorithm 與 Dijkstra;s algorithm 本質上是相同的方法，所以修改 Dijkstra's algorithm 的某些地方即可變成 Prim's algorithm。

與 Dijkstra's algorithm 的差別是不需要考慮從起點 $s$ 開始的路徑，只要找當下 tree 跟哪個節點距離最近即可。

> [!Important] Kruskal's algorithm v.s. Prim's algorithm
> 與 Kruskal's algorithm 相比 Prim's algorithm 在過程中只有一個樹，每次增加一個節點讓樹慢慢長大，最後形成一個大樹。

### 3. Reverse-delete algorithm

Step-by-step:

* 從 $T = E$ 開始
* 將 edges 依照 cost 由大到小排序，並從 cost 大的開始刪除
* 每次刪除 edge 的過程不會形成 disconnected graph

<!-- p.55圖 -->

> [!Important]
> 前兩種都是加入 edge/node 使 subgraph 慢慢長大，但 reverse-delete 是反向操作，把不重要的 edge 拔掉。實作上前兩個比較容易。

## Implement Kruskal's algorithm: union-find

### 1. Union-Find data structure

Union-Find 是一種判斷 graph 是不是互斥集合的方法，能夠將兩個互斥的 graph 合併成一個更大的 graph。

* Disjoint sets: 彼此間互斥(disjoint)的集合
* 每個 set 都有一個代表點(representative)，通常是根節點(root)
* 可用代表點判斷兩個集合是不是屬於同一個 disjoint set
* Operations
* `Find(u)`: 尋找包含節點 `u` 的集合的代表點，通常是不斷的往上找 parent/root node
* `Union(A, B)`: 將兩個互斥集合 `A` 與 `B` 合併
* 通常是小的合併至大的集合
* 合併的過程就是重選代表點，將小集合的節點指向大集合的 root


### 2. Implement Kruskal's algorithm

Kruskal's algorithm 的實作可以用 Union-Find 進行，因為判斷新增加的 edge/node 會不會產生 cycle 的過程其實就是檢查兩個 node 的代表點是否相同。

> [!Tip] **Algorithm:** Kruskal
> 

* Line 3
* 初始化每個節點都是一個 disjoint set
* Line 4
* 每個 edge 的兩節點分別各做一次 `find(u)` 與 `find(v)` 判斷代表點是否相同
* 若 `find(u) != find(v)` 表示節點 `u` 和 `v` 分屬不同的 disjoint set，可以合併
* 若 `find(u) != find(v)` 表示節點 `u` 和 `v` 屬於相同的 disjoint set，合併會形成 cycle
* Line 5
* 將兩個 disjoint set 合併 `union(u, v)`