# Greedy Algorithm 貪婪演算法
### Greedy Algorithm 貪婪演算法
> 一種優化問題的策略：每一步都做「當下看起來最優」的選則
* 永遠選則當下最優選項
* 做局部最優解，去導向全局最優
* 用來處理最佳化問題，跟動態規劃類似
* 對某些問題來說動態規劃大材小用，問題有貪婪選擇性質，用Greedy Algorithm更簡單快速
* 並不能保證最終得到的是最優解
#
### Activity-Selection 活動選擇問題

* 有 $N$ 個活動同時競爭一個資源，而且一個資源一次只能給一個活動使用
* $e.g.$ 會議室使用的排程、機器使用的排程
* 活動的集合 $S=\{ a_1,a_2,...,a_n\}$
* 每一個活動 $a_i$ 有開始時間 $s_i$ 跟結束時間 $f_i$
* $0\le s_i<f_i<\infty$
* $a_i$ 在結束時不需要資源-> $[\; s_i,f_i\; )$
* 使用資源點的時間為 $t_{ai}\; \therefore s_i\le t_{ai}<f_i$
* 兩個不同的活動 $a_i$ , $a_j$ 時間上不能重疊
* 問題敘述：
* 從活動中選出大小最大，活動比此互相不重疊的子集合。
* Example：

* Optimal Substructure 最佳子結構
* Define $S_{ij}=\{\ a_k\in S:f_i\le s_k<f_k\le s_j\; \}$
* 代表活動 $a_i$ 結束後活動 $a_j$ 開始前能安排的所有活動
* $S=S_{0,n+1}$
* 原問題可以視為用兩個假活動把邊界包起來
* $a_0=[\ -\infty,0\ )$ , $a_{n+1}=[\ \infty,\infty+1\ )$
* $S_{ij}$ 的範圍是 $0\le i,\ j\le n+1$
* 活動結束時間 $f$ 由小到大排好
* $f_0\le f_1\le f_2\le ...\le f_n\le f_{n+1}\Rightarrow S_{ij}=\varnothing \text{ if }i\ge j$
* $0\le i<j\le n+1$ 的情況下 $S_{ij}$ 才有可能活動，在其中要找出最大相容子集合
* 其他情況下 $S_{ij}$ 都是空集合
* 假設 $S_{ij}$ 的某個解包含活動 $a_k$ -> $S_{ij}\text{ 的解}=\{S_{ik}\text{ 的解}\}\cup \{a_k\}\cup \{S_{ki}\text{ 的解}\}$
* $S_{ik}$ 代表在 $a_i$ 結束後 $a_k$ 開始前可選的活動
* $S_{kj}$ 代表在 $a_k$ 結束後 $a_j$ 開始前可選的活動
* $\text{所選的活動數量}=S_{ik}+1+S_{kj}$
* 若 $S_{ij}$ 的最優解包含 $a_k$ 那它在 $S_{ik},S_{kj}$ 內用到的子解也必須各自最優
* 設 $A_{ij}$ 為 $S_{ij}$ 的最優解，$A_{ij}=A_{ik}\cup\{a_k\} \cup A_{kj}$
* 整個問題最優解就是 $S_{0,n+1}$ 的最優解

* 遞迴關係式：
* 定義 $c[i][j]$ 為在 $S_{ij}$ 中可選最多幾個相容活動
* $i\ge j$ => $S_{ij}=\varnothing$ => $c[i][j]=0$
* $c[i][j]=\begin{cases} \;0\; &\text{if }S_{ij}=\varnothing\;,\\
max_{i<k<j,a_k\in S_{ij}}\{\ c[i][k]+c[k][j]+1\ \} &\text{if }S_{ij}\not= \varnothing\ .\end{cases}$

* 轉換成Greedy Algorithm
* 令 $a_m$ 是其中最早結束的活動，$a_m$ 一定存在某個最優解中
* 選了最早結束的活動 $a_m$ ，$S_{im}$ 就不用管了 <- 沒有能插在$i,m$之間的活動
* 最優解需處理子問題數從 $2$ -> $1$，需考慮的選擇數從 $j-i-1$ -> $1$(最早結束的那個)
* 從頂向下解 $S_{ij}$ 先選 $S_{ij}$ 中結束最早的 $a_m$ (Greedy Choice)，再解剩下的 $S_{mj}$

* 遞迴&迭代方式實現 Greedy Algorithm
* 時間複雜度都是 $\Theta(n)$
* 輸入的活動都要依序結束時間遞增排序
* Activity Selection Process
* 找出最佳子結構
* 寫出遞迴關係式
* 證明在任意遞迴階段都存某個最優解會做出貪婪選擇=>所以貪婪選擇永遠安全
* 證明完貪婪選擇後只會有一個子問題
* 根據上述結論寫出遞迴版本的Greedy Algorithm
* 再改寫成迭代版本
#
### Streamlining Steps
> 把DP思維精簡成Greedy

* 在建立子結構的時候就要朝向：能做貪婪選擇，並且只留下 $1$ 個子問題。
* 證明存在最優解會做貪婪選擇 (所以是安全的)_
* 證明貪婪選擇+子問題最優解會得到原問題的最優解
#
### Greedy-Choice Property
> 全局最優解可以透過每步做局部最優(貪婪)選擇得到
> 只看當下最好的選擇，不先看子問題解的結果 (與DP相反，DP會先算子問題才做選擇)

比較 Dynamic Programming & Greedy Algroithm 兩者

* Dynamic Programming 動態規劃
* 選擇依賴子問題解；先解決子問題；通常 `Bottom-up`

* Greedy Algorithm 貪婪演算法
* 選擇只依賴目前已做的決策；先做選擇再處理剩餘；通常 `top-down`
#
### Greedy Algorithm vs. Dynamic Programming (Knapsack Problem)

* 0-1 背包問題
> 有$n$個物品，第$i$個物品的價值(value)是$v_i$、重量(weight)是$w_i$
背包的最大承重是 $W$
目標是挑出一個子集合使得總重量$\le W$，且總價值最大
每次遇到一個物品只能選擇不拿(0)、拿走(1)，不能分割物品

* Greedy Algroithm 執行結果
* 以當下價值最高 or $\frac{v_i}{w_i}$ 去做選擇

| Item | value | weight | $\frac{v_i}{w_i}$ |
| -------- | ----- | ------ | ----------------- |
| $item 1$ | $60$ | $10$ | $6$ |
| $item 2$ | $100$ | $20$ | $5$ |
| $item 3$ | $120$ | $30$ | $4$ |

用 $\frac{v_i}{w_i}$ 去做的話會先拿 $item1$ -> 背包空間剩 $40$
再拿 $item2$ -> 背包空間剩 $20$
$item3$ -> 背包放不下不能拿，總價值是 $60+100=160$

* Dynamic Programming 執行結果

* $dp[i][w] =
\begin{cases}
0, & i=0 \text{ 或 } w=0 \\[6pt]
dp[i-1][w], & w < w_i \\[6pt]
\max\big(dp[i-1][w],\; dp[i-1][w-w_i]+v_i\big), & w \ge w_i
\end{cases}$
*  填表
* 可以看出最佳解其實是 $value = 220$

* 從這個問題就可以看出來0-1背包問題不適合使用Greedy Algorithm

* Fractional knapsack 分數背包問題
> 跟0-1背包很像，但允許物品可以只拿一步
> 例如某物品10kg，可以只拿3kg，價值也按照比例拿30%

* Greedy Algorithm
* 永遠拿 $\frac{v_i}{w_i}$ 最大的物品，能拿多少拿多少
* 容量不夠拿全部就拿他的一部分->不會發生塞不下整個物品錯過更好的組合
* 

#
### Binary Character Code
* Fixed-length code
* 對所有的character都用同樣長度的bit去表達

* Variable-length code
* 給使用頻率高的character更短的codewords
* 使用頻率低的character相對較長的codewords
* 平均每個字使用的bit就變少了

#
### Prefix (Free) Code
> 沒有任何一個字碼是另一個字碼的開頭 (prefix)
* Encoding 編碼
* 把每個字元的碼字直接串起來 $e.g., abc=0・101・100=0101100$
* Decoding 解碼
* 從頭辨識第一個碼字->轉回字元->對剩餘位元重複
* $e.g.,001011101=0．0．101．1101=aabe$
#
### Binary Tree Representation (用二元樹表示編碼)
* 葉節點對應字元
* 字碼可以視為從根(root)走到該字元節點的路徑
* $0$ -> 左子樹 ， $1$ -> 右子樹
* 一個檔案的最優編碼一定可以用 `Full binary tree` 來表示 (Huffman找這棵樹)
* 字母表的大小為 $|C|$ 則葉子有 $|C|$ 個，內部節點有 $|C|-1$ 個
* 成本：所需的位元總數 ， $B(T) = \displaystyle \sum_{c \in C} f(c)\, d_T(c)$
* $f(c)$ 、 $d_T(c)$ -> 字元 $c$ 的葉深度 => 碼字長度
#
### Huffman Code (霍夫曼編碼)

* $C：$ 含 $n$ 個字元的集合，每個字元有頻率 $f[c]$
* $Q：$ 以頻率 $f$ 為key 的 `min-priority queue`
* 時間複雜度：$O(n\log n)$
* 流程：
1. 將字元表大小->$n$
2. 將頻率->$Q$
3. loop做$n-1$次
4. 建立一個新的節點$z$
5. 將$Q$中最小的節點$x$->$z$的左子樹
6. 將$Q$中第二小的節點$y$->$z$的右子樹
7. $z$ 節點的頻率 $=左子樹頻率+右子樹頻率
8. 把新節點$z$放回$Q$
9. loop做完後只剩下最後一個節點，`return` 回去成為樹的 `root`
* Example：