---
# System prepended metadata

title: Greedy Algorithm

---

# 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：![image](https://hackmd.io/_uploads/r1Gk4n-7Ze.png)
 
 * 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)，不能分割物品
     ![image](https://hackmd.io/_uploads/B1u3SIzQ-g.png)

    
    * 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}$
        * ![image](https://hackmd.io/_uploads/BkBM7Pf7-g.png) 填表
        * 可以看出最佳解其實是 $value = 220$
   
   * 從這個問題就可以看出來0-1背包問題不適合使用Greedy Algorithm

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

    * Greedy Algorithm 
        * 永遠拿 $\frac{v_i}{w_i}$ 最大的物品，能拿多少拿多少 
        * 容量不夠拿全部就拿他的一部分->不會發生塞不下整個物品錯過更好的組合
        * ![image](https://hackmd.io/_uploads/HkYbwPf7Wl.png)

# 
### 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 (霍夫曼編碼)
![image](https://hackmd.io/_uploads/SkFGfdzXZe.png)

* $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：
![image](https://hackmd.io/_uploads/SJDOvdzXWg.png)
