###### tags: `Algorithm` <style> font { font-weight: bold; color: red; } </style> # Ch04 - Greedy ## Greedy Algorithm :::info - A greedy algorithm arrives at a solution by making a sequence of choices, **each of which simply looks the best at the moment** (*locally optimal*). - Like DP, Greedy Algorithms are often to solve Optimization Problems. - **Greedy Algorithms do not guarantee an optimal solution.** - No division is require ::: **貪婪演算法**是一種在每一步選擇中都採取在當前狀態下最好或最佳 (即最有利) 的選擇，從而希望導致結果是最好或最佳的演算法。 貪婪演算法在有**最佳子結構**的問題中尤為有效。最佳子結構的意思是**局部最佳解能決定全域最佳解**。簡單地說，問題能夠分解成子問題來解決，子問題的最佳解能遞推到最終問題的最佳解。 **貪婪演算法與動態規劃的不同在於它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會儲存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。** 貪婪法可以解決一些最佳化問題，一旦一個問題可以通過貪婪法來解決，那麼貪婪法一般是解決這個問題的最好辦法。但是貪婪法**不一定出現最優的解**。 ## Steps :::info - Start with an **empty set** and **adds items** to the set in sequence until the set represents a solution to an instance of a problem. - Each Iteration consists of : - A <font>selection procedure</font> chooses the next item to add to the set. The selection is performed according to a greedy criterion that satisfies some locally optimal consideration at the time. - A <font>feasibility check</font> determines if the new set is feasible by checking whether it is possible to complete this set in such a way as to give a solution to the instance. - A <font>solution check</font> determines whether the new set constitutes a solution to the instance. ::: :::success - ***Selection procedure: 選擇程序***，根據貪婪法的標準選擇下一個符合當時情況下的最優解。 - ***Feasibility check: 可行性檢查***，確定新的選擇是否可行。 - ***Solution check: 解法檢查***，確定最終的所有選擇是否滿足實例。 ::: ## Spanning Tree - 生成樹 新建一個圖，包含圖 G 的所有點 (Vertex)，將所有的點連接在一起即為生成樹。 > **NOTE: 要用最少的邊 (Edge) 連接在一起才會是生成樹。** :::success **生成樹的性質:** 1. 一個圖 (Graph) 不只會有一個生成樹 (Spanning Tree)。 2. 同一個圖的生成樹，會有相同的點 (Vertex), 邊 (Edge) 的個數。 3. 所有的生成數，**不會出現 Cycle, loop 的結構**。 4. 如果把其中一個「邊(Edge)」拿掉就會成為無連通圖 (Disconnected Graph) 我們可以說生成樹是**最小的連接 (minimally connected)**。 5. 只要多加一個邊，就會形成 cycle, Loop，所以也可以成生成樹是 **maximally acyclic (最大無環)**。 ::: ## Minimum Spanning Trees - 最小生成樹 在**權重圖**中，最小生成樹，即是將全部「點 (Vertex)」相連，相連的「邊 (Edge)」其**權重 (Weight) 要最小**，即為最小生成樹。 > **權重的概念是距離的遠近、中間的成本等等。** ### Prim’s Algorithm :::danger **Steps:** 1. 先從 Spanning tree 中找一個頂點 V 作為起始點。 2. 找出與 V 相連且還沒有被選取的頂點裡面加權值最小的邊。 3. 加入與加權值最小的邊相連的頂點。 4. 重覆 2 找尋相連且未被選取的頂點加入 Spanning tree，直到產生了 N-1 個邊，將圖的 N 個頂點連接起來。 ::: - **Time complexity: $O(n^2)$** ![](https://imgur.com/Zm8QlCr.gif) #### Pseudocode: ```c= T = {}; TV = {0}; // start with vertex 0 and no edges while (T contains fewer than n - 1 edges) { let (u, v) be a least cost edge such that u in TV and v not in TV; if (there is no such edge) break; add v to TV; add (u, v) to T; } if (T contains fewer than n - 1 edges) printf("No spanning tree\n"); ``` ![](https://i.imgur.com/QzbWl1j.png) ==期中考可能會考把 nearest 跟 distance 寫出來== :::danger - nearest[i] = index of the vertex in Y nearest to $v_i$. - distance[i] = weight on edge between $v_i$ and the vertex indexed by nearest[i]. ::: #### 不負責任翻譯 :::danger - `nearest[i] = 1` 的意思是在 $Y$ 中最靠近 $v_i$ 的節點是 $v_1$。 - `distance[i] = L` 的意思是最靠近 $v_i$ 的節點 (也就是上述的 $v_1$) 跟 $v_i$ 的距離等於 $L$, 也就是 `W[nearest[i]][i] = W[1][i] = L`。 ::: #### code ```cpp= void prim(int n, const number W[][], set_of_edges& F) { index i, unear; number min; edge e; index nearest[2..n]; number distance[2..n]; F = ∅; for(i = 2; i <= n; i++) { // index 1 2 3 4 5 nearest[i] = 1; // nearest [- 1 1 1 1] distance[i] = W[1][i]; // distance[- 1 3 ∞ ∞] } // For all vertices, initialize v_1 to be the nearest vertex // in Y and initialize the distance from Y to be the weigth // on the edge to v_1. repeat (n - 1 times) { // Add all n - 1 vertices to Y. min = ∞; for (i = 2; i <= n; i++) { if(0 ≤ distance[i] < min){ min = distance[i]; // min = 1 vnear = i; // vnear = 2 } } // Check each vertex for being nearest to Y. e = edge connecting vertices indexed by vnear and nearest[vnear]; // nearest[vnear] = 1, vnear = 2 // e = edge(1, 2) add e to F; // F = {{1,2}} distance[vnear] = -1; // Add vertex indexed by vnear to Y. for(i = 2; i <= n; i++){ if(W[i][vnear] < distance[i]){ // index 1 2 3 4 5 distance[i] = W[i][vnear]; // distance[- -1 3 6 ∞] nearest[i] = vnear; // nearest [- 1 1 2 1] } } // For each vertex not in Y, update its distance from Y. } } ``` ![](https://imgur.com/rv54BtF.png) ### Kruskal’s Algorithm :::danger **Steps:** 1. 由小到大排序，所有「邊 (Edge)」的權重 (Weight)。 2. 從小到大開始取那些「邊 (Edge)」，前提是取到的 Edge 不能形成一個迴圈 (loop, cycle)。 3. 重複步驟 2 的動作，直到最後已經不能再取。 ::: - **Time complexity: $O(e \log e)$** - **Worst: $W(n) \in \Theta(n^2 \lg n)$** #### Pseudocode: ```c= T = {}; while (T contains less than n - 1 edges && E is not empty) { choose a least cost edge (v, w) from E; delete (v, w) from E; if ((v, w) does not create a cycle in T) add (v, w) to T; else discard (v, w); } if (T contains fewer than n - 1 edges) printf("No spanning tree\n"); ``` #### code ```cpp= void kruskal(int n, int m, set_of_edges E, set_of_edges& F){ index i, j; set_pointer p, q; edge e; Sort the m edges in E by weight in nondecreasing order; F = ∅; initial(n); // Initialize n disjoint subsets. while(number of edges in F is less than n - 1){ e = edge with least weight not yet considered; i, j = indices of vertices connected by e; p = find(i); q = find(j); if(!equal(p, q)){ merge(p, q); add e to F; } } } ``` ![](https://imgur.com/H3fTC32.gif =40%x) ### <font>Prim演算法是對圖上的節點貪心，而Kruskal演算法是對圖上的邊貪心。</font> :::warning - **Sparse graph 稀疏圖** 邊跟點的個數很靠近，edge 的條數(e)遠小於(n^2^) ==適合 Kruskal Alog== ![](https://i.imgur.com/3d0ftxn.png =200x) - **Dense graph 稠密圖** edge 的條數(e)趨近於(n^2^) ==適合 Prim Alog== ![](https://i.imgur.com/lgo4ryg.png =200x) - **Complete graph 完全連接圖** edge = node(node -1)/2 ![](https://i.imgur.com/fRYhKPl.png =200x) - **Thinking By Density:** Prim $\Rightarrow$ 跟 node 有關，跟 edge 的個數無關。 Kruskal $\Rightarrow$ 跟 edge 有關，跟 node 的個數無關。 ::: ## Single Source Shortest Paths - Dijkstra's Algorithm :::success Determine the shortest paths from one particular vertex to all the others. **問題:** 一張**有向圖**，選定一個起點，找出**起點到圖上各點的最短路徑**。 即是找出其中一棵最短路徑樹。 ::: :::danger **Approach:** - 令 `w[a][b]` 是 a 點到 b 點的距離（即是邊的權重）。 - 令 `d[a]` 是起點到 a 點的最短路徑長度，起點設為零，其他點都設為無限大。 1. 重複下面事件 n 次，以將所有點加入到最短路徑樹。 1. 尋找一個目前不在最短路徑樹上而且離起點最近的點： - 直接搜尋 `d[]` 陣列裡頭的數值，來判斷離起點最近的點。 2. 將此點加入到最短路徑樹之中。 3. 令剛剛加入的點為a點， - 以窮舉方式，找一個不在最短路徑樹上、且與a點相鄰的點b， - 把 `d[a] + w[a][b]` 存入到 `d[b]` 當中。 - 因為要找最短路徑，所以儘可能記錄越小的 `d[a] + w[a][b]`。 - （即是邊 ab 進行 relaxation） ::: #### Pseudocode: ```c= Y = {v1}; F = ∅; while (the instance is not solved) { select a vertex v from V - Y, that has a shortest path from v1, using only vertices in Y as intermediates; // selection procedure and feasibility check add the new vertex v to Y; add the edge (on the shortest path) that touches v to F; if (Y == V) the instance is solved; // solution check } ``` :::danger - <font>touch[i]</font> = index of vertex *v* in *Y* such that the edge *<v, vi>* is the last edge on the current shortest path from *v1* to *vi* using only vertices in *Y* as intermediates. - <font>length[i]</font> = length of the current shortest path from *v1* to *vi* using only vertices in *Y* as intermediates. ::: #### 渣男翻譯 :::danger - `touch[b] = a` 的意思是 $v_a \rightarrow v_b$, 也就是 $v_a$ 走向 $v_b$。 $v_a$ 是 $Y$ 裡面最外邊的節點; 而 $v_b$ 則是在 $Y$ 外邊 (也就是 $V - Y$) 最接近 $v_a$ 的節點。 - `length[i] = L` 的意思是從 $v_1$ 走到 $v_i$ 的最短路徑長度等於 $L$。 ::: #### code ```c= void dijkstra(int n, const number W[][], set_of_edges& F) { index i, vnear; edge e; index touch[2...n]; number length[2...n]; // For all verices, initialize v1 to be the last vertex on the current // shortest path from v1, and initialize length of that path to be the // weight on the edge from v1. F = ∅; for (i=2; i<=n; i++) { touch[i] = 1; length[i] = W[1][i]; } // repeat n-1 times int times = n-1; while (times--) { min = ∞; // check each vertex for having shortest path. for (i=2; i<=n; i++) { if (0 <= length[i] < min) { min = length[i]; vnear = i; } } e = edge from vertex indexed by touch[vnear] to vertex indexed by vnear; add e to F; for (i=2; i<=n; i++) { // for each vertex not in Y, update its shortest path. if (length[vnear] + W[vnear][i] < length[i]) { length[i] = length[vnear] + W[vnear][i]; touch[i] = vnear; } // add vertex indexed by vnear to Y length[vnear] = -1; } } } ``` ## Scheduling :::success - A reasonable goal would be to schedule the event in such a way as **to minimize the total time they spend both waiting and being served**. - Such a schedule is considered **optimal**. - The time spent both waiting and being served is called the ***time in the system***. ::: :::info **Example** Suppose there are three jobs and the service times for these jobs are $$ t_1 = 5,\ t_2 = 10\ and\ t_3 = 4 $$ If we schedule them in the different order, the times spent in the system for the three jobs are as follows: | Schedule | Total time in the system | | -------- | -------- | | [1, 2, 3] | 5 + (5 + 10) + (5 + 10 + 4) = 39 | | [1, 3, 2] | 5 + (5 + 4) + (5 + 4 + 10) = 33 | | [2, 1, 3] | 10 + (10 + 5) + (10 + 5 + 4) = 44 | | [2, 3, 1] | 10 + (10 + 4) + (10 + 4 + 5) = 43 | | [3, 1, 2] | 4 + (4 + 5) + (4 + 5 + 10) = 32 | | [3, 2, 1] | 4 + (4 + 10) + (4 + 10 + 5) = 37 | **$\rightarrow$ Schedule [3, 1, 2] is optimal with a total time of 32.** pseudo code ```c= sort the jobs by service time in nondecreasing order; while (the instance is not solved) { // selection procedure and feasibility check schedule the next job; // solution check if (there are no more jobs) { the instance is solved; } } ``` ::: ### Scheduling with deadlines :::success - This kind of scheduling problem occurs when each event **takes the same amount of time to complete but has a deadline**. - The goal is to schedule the events to **maximize the total profit**. ::: :::info **Example** Suppose we have the following jobs, deadlines, and profits: | *Job* | *Deadline* | *Profit* | |:-----:|:----------:|:--------:| | 1 | 2 | 30 | | 2 | 1 | 35 | | 3 | 2 | 25 | | 4 | 1 | 40 | | *Schedule* | *Total Profit* | |:----------:|:--------------:| | [1, 3] | 30 + 25 = 55 | | [2, 1] | 35 + 30 = 65 | | [2, 3] | 35 + 25 = 60 | | [3, 1] | 25 + 30 = 55 | | [4, 1] | 40 + 30 = 70 | | [4, 3] | 40 + 25 = 65 | We see that [4, 1] is optimal with a total profit of 70. pseudo code ```c= sort the jobs in nonincreasing order by profit; S = ∅; while (the instance is not solved) { select next job; if (S is feasible with this job added) { add this job to S; } if (there are no more jobs) { ths instance is solved; } } ``` ::: ## Huffman Code :::success - An encoding method to solve the **optimal binary code problem** - The **Optimal Binary Code Problem** - Find a binary code for the characters in the file so that the file is represented in the least number of bits. - A data compression problem. - A prefix code **Binary Code** - Each character of the file is represented by a codeword - Fixed length binary code - each character is represented by using the same number of bits. ::: :::info **Example:** **Character Set: {a, b, c} File: ababcbbbc** - **Code E1: a = 00, b = 01, c = 11** (Fixed length binary code) - Encoded file: <u>00</u>01<u>00</u>01<u>11</u>01<u>01</u>01<u>11</u> (18 bits) - **Code E2: a = 10, b = 0, c = 11** - Encoded file: <u>10</u>0<u>10</u>0<u>11</u>0<u>0</u>0<u>11</u> (13 bits) Clearly, code E2 is better than code E1. ::: :::success **Prefix Code** - No codeword for one character constitutes the beginning of the codeword for another character. - Advantage - We need not look ahead when paring the file. ::: :::info **Example** Code E1 and E2 are prefix codes Code E3: {a = 00, b = 0, c = 11} is not prefix code. ::: :::success **Huffman Code** Every prefix code canbe represented by a binary tree whose leaves are the characters that are to be encoded **Ex. Code E2: a = 10, b = 0, c = 11** ![](https://i.imgur.com/BTIu2tV.png =60%x) ::: ## The 0-1 Knapsack Problem (0-1 KP) :::success 將一堆物品儘量塞進背包裡面，令背包裡面的物品**總價值最高**。背包沒有容量限制，無論物品是什麼形狀大小，都能塞進背包；但是**背包有重量限制**，如果物品太重，就會撐破背包。 以數學術語來說，背包問題就是**選擇一個最理想的物品子集合，在符合重量限制的前提下、求得最大的利益**。 0/1 背包問題是經典的 **NP-complete** 問題，無法快速求得精確解，只能折衷求得近似解。然而，當數值範圍不大時，得以用**動態規劃**快速求得精確解。 ::: ### Fractional Knapsack Problem :::warning **Fractional** 是「**分數**」的意思。一個物品可以切下一部分、只取幾分之幾放進背包。 我們很容易就可以制定一個 Greedy 策略：**價值與重量的比值最高的物品，優先放進背包。** 總是用當下最好的物品填滿背包空隙，最後沒有留下任何空隙。每一份背包空間，都是最有價值的物品。 **時間複雜度 O(N)**。 N 是物品數量。 ::: ### 0-1 Knapsack Problem :::warning 「0/1」的意思是：每種物品只會放進背包**零個或一個**。一個物品要馬整個不放進背包、要馬整個放進背包。**物品無法切割**。 大家看到這個問題，第一個直覺通常是貪心法：優先挑選價值最高的物品。 然而，價值高的物品，放進背包之後，有可能留下很大的空隙，浪費背包耐重量；反而是狂塞一些零零碎碎的不值錢東西，才能獲得最多的利益。 ::: :::danger **0/1 背包問題的關鍵點在於，如何有效利用背包的剩餘重量，找出最好的物品組合方式。** :::