Greedy Algorithm

Activity-selection problem: 目的：安排最多的相容活動。 , n 個活動. 對任一活動 i , Start time：Si finish time：fi 任二活動 i , j 可相容表示此兩種活動不重疊。即 or

Greedy-Activity-Selector(S,f)： Algorithm： Complexity： Thm：上述演算法可產生最多的相容活動。 假設 , 此可由 quicksort 達到 ~ Greedy-Activity-Selector(S,f) { n = length(S) ; A = {1} ; j=1; for i=2 to n do if then return A }

Greedy 方法之要素： 1. Globally optimal solution 可由選擇 local optimal solution 獲得。 2. 一最佳解包含子問題之最佳解。 ( 此與 Dynamic Programming 類似 )

0-1 knapsack problem：( NP complete ) Goal：to carry as much value as possible. Fractional knapsack problem： n items n items i-th item： worth dollars weight units A person can carry W units. 同上，每一件東西可只取部分 ( 如 1/4, …. ) 依序由大而小排列 Example：W=50 item1： 取 item1 , item2 及 item2： 2/3 的 item3. item3：

Huffman codes： 若用 fixed-length codeword： 總共有 45 000 Frequency (x1000) Fixed-length codeword variable-length b 13 001 101 c 12 010 100 d 16 011 111 e 9 1101 f 5 1100 若用 fixed-length codeword： 總共有 若用 variable-length codeword： 總共有

Prefix codes： No codeword is also a prefix of some other codes. 字首 T： 100 1 a : 45 55 1 cost of the tree T. 25 30 1 1 c : 12 b : 13 d : 16 14 1 f : 5 e : 9

Constructing a Huffman code： b : 13 d : 16 a : 45 (b) c : 12 b : 13 14 1 f : 5 e : 9 d : 16 a : 45 (c) 14 1 f : 5 e : 9 d : 16 25 1 c : 12 b : 13 a : 45 25 1 c : 12 b : 13 14 1 f : 5 e : 9 30 d : 16 (d) a : 45 (f) (同前頁：T) 55 1 (e) a : 45 14 1 f : 5 e : 9 30 d : 16 25 c : 12 b : 13 55 a : 45 55 1 14 1 f : 5 e : 9 30 d : 16 25 1 c : 12 b : 13

Example：” A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS source： 11 3 3 1 2 5 1 2 6 2 4 5 3 1 2 4 3 2 A B C D E F G I L M N D P R S T U 60 1 11 1 23 5 6 N I 3 2 F G 12 O B A 37 1 1 2 C P 5 3 T 10 E 21 11 16 1 8 8 1 1 4 4 4 4 1 S M 1 2 2 2 2 U L D R 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1

A Huffman tree is a binary tree of integers with these two properties: Each internal node is the sum of of its children Its weighted external path length is minimal

Algorithm: Generating a Huffman code Input: a sequence of characters output: a bit code for the input characters Postconditions: the bit code has the unique prefix property and is optimal Tally the frequencies of the input characters Load the letter-frequency pairs into a min priority queue Coalesce the pairs into a Huffman tree Encode the character at each leaf with the bit sequence along root-to-leaf path

Huffman(C)： Algorithm： Complexity： Huffman(C) { // Q：priority queue for i=1 to n-1 do { z = allocate-Node() ; x = left(z) = Extract-min(Q) ; y = right(z) = Extract-min(Q) ; f(z) = f(x) + f(y) ; Insert(Q , z) ; } return Extract-min(Q) ; }

Lemma 17.2： C ：字母 , C ：字元 , c：出現 次. 令 且 為最小的兩個. C 令 且 為最小的兩個. C 存在一最佳的 prefix-free code, 使 x,y 之碼等長且只差最後一個 bit. Proof： T ( optimal ) T’ T’’ C = = 同理

Lemma 17.3： 令 T：full binary tree representing an optimal prefix code over . C leaves T’ represents an optimal prefix code for C’. Proof： 對任一 C 若 T’ 不是 C’ 的最佳 prefix code. 則可找到 T’’ 使 B(T’’) < B(T’) T 是 C 之最佳之 prefix code.

Thm： Huffman 之演算法可產生最佳之 prefix code. Proof： 由 lemma 17.2 , 17.3. Example： 若用 { 0 , 1 , 2 } 來編碼，試將上述方法一般化以求得最佳之編碼方法。

Matroids： Graphic matroid： 1. S：有限非空集合 2. X：為 S 的部分集合所形成之集合 ( 即 X 的元素為集合 ) 並滿足：若 且 則 3. 若 且 則存在 使得 Graphic matroid： 且 A：acyclic. independent subset ( hereditary property ) ( exchange property ) Example：Matric matroid if rows in I are linearly independent. 為一 graph. ( i.e. A forms a forest )

Thm 17.5： 若 G 為一 undirected graph 則 為 一 matroid. Proof： 1. E：finite 2. is hereditary, acyclic graph 之部分仍為 acyclic. 3. 假設 A,B 為 G 中之 forests. 且 A：包含 個 trees. B：包含 個 trees. ( B 的樹較少 ) ( 但有較大顆的 ) 故在 B 中有一樹 T 包含 A 中的 2顆樹的vertices. 亦即 T 中存在一 edge (u,v) 使得 u 和 v 分佈在 A 中的兩顆樹. 故將 (u,v) 加到 A 中 不會產生 cycle. 故 由 1. 2. 3. 定理得證.

Thm 17.6： All maximal independent subsets in a matroid have the same size. Proof： , A is maximal if it has no extension. 即不存在 使得 假設 A：maximal independent subset. B：maximal independent subset 且 存在 使得 A 為 maximal.

Greedy algorithms on a weighted matroid Definition： Greedy algorithms on a weighted matroid Problem： , weight function：w(x) for each Given , find has maximal possible weight. Example：Minimum Spanning Tree ：weight function defined on E; . Define , and Let A be a maximal independent set in X. Then A corresponds to a spanning tree in G.

Algorithm： 若 則上述需 步驟。 Greedy(M,w) { Sort S[M] into nonincreasing order by weight w ; For each , taken in nonincreasing order by weight w(x) ; do if then Return A } 若 則上述需 步驟。

Lemma 17.7： 令 為一加權 ( weight ) matroid. S 依加權函數 w, 排列由大到小. 令 x 為 S 中第一個使 之independent元素 ( 但此 x 並不一定存在 ). 若此 x 存在，則存在一最佳( 即 w(A) 最大 ) 之 A Proof： 若沒有上述 x 存在，則 為唯一的 independent set. Why ? 現假設 B 為一非空之 optimal subset. 若 , 則取 A 等於 B 故得證. 若 , 則 B 中之元素的 weight 不會比 x 之 weight 大. 假設 但已知 令 由 exchange property, 可將 A 擴充至 而且 A 仍保持 為 independent. 取 B 為 optimal A 為 optimal 且含 x.

Thm 17.8： 令 為任一 matroid. 若 且 x 不為 之 extension, 則 x 不為任一 independent set 之 extension. Proof： 假設 x 為 A 之 extension 但不為 之 extension. independent. x 為 A 之 extension. independent. 由假設 x 不是 之 extension.

Thm 17.9(Matroids optimal-substructure)： 令 x 為 Greedy 演算法中第一個被選入的元素. 尋找 M 中包含 x 之 maximum-weight independent subset 可以 被轉化為尋找 matroid 之 maximum weight ind. Set. Proof： 若 且 且 A：maximum weighted 反之若 則 又 故由 M 中含 x 之 maximum-weight solution 可找到 M’ 之 maximum-weight solution. 反之亦然. 給定 , 則 Greedy(M,w) 可以找到 optimal solution. Proof：

A task-scheduling problem： S={1,2,…..,n} n unit-time tasks. Deadlines： task i 需在 di 前完成. Penalties： 若 task i 不能在 di 前完成，則罰 wi 若 task i 能在 di 前完成著無 penalty. 目標：安排一執行順序使 penalty 最小. Example： 1 4 60 2 70 3 40 50 30 5 6 10 7 20 Schedule：< 2 4 1 3 7 5 6 > penalty 20+30=50.

Def： 在一 schedule 中： late task：if it finishes after its deadline. early task：if it finishes before its deadline. Early-first form：early tasks precede the late tasks. Canonical form：same as early-first form and the early tasks are scheduled in order of nondecreasing deadlines. a set A of task is independent：若存在一 schedule 使得 A 中無 late schedule. 故任一 schedule 中之 early tasks 形成一 independent set. 令 X 表所有 independent set 之集合. 如何判定一 tasks 集合是否為 independent？ k k+1 j k k+1 i 若 i j i,j：early task t=1,2,…,n ，令 Nt(A) 表 A 中之 tasks 其 deadline t.

Lemma 17.11： 令 A：tasks 所形成之集合. 則下列序列等價 1. A：independent. 2. For t=1,2,…n， 3. 若 A 中之 tasks 依 deadlines ( nondecreasing ) 排序，則無 late task. Proof： 若 , 則 A 中存在 late task. 故 顯然.

Thm 17.12： S={ unit tasks with deadline } (S,X) is a matroid. X={ independent sets of tasks } Proof： clearly. 由上述 independent set 之定義知其滿足 matroid 之第 2 個條件。 且

Solution by Greedy Algorithm Sort w1,….., wn in decreasing order Check A  {i}  X ? Time complexity: O(n*n).

1 2 3 51 51 51 NYT NYT 2 a NYT 2 a 2 a 1 49 50 49 50 51 49 50 (a) (aa) 1 r 47 48 (aar) 2 1 48 4 50 a r 49 51 45 46 NYT d 47 4 51 2 2 a 49 50 1 r 1 48 47 1 d 1 46 45 (aard) NYT (aardv) 1 v 4 43 44 51 5 2 a 2 51 50 a 2 49 3 r 1 2 47 r 1 48 2 d 1 3 d 45 46 1 1 NYT 1 v (aardv) (aardv) 43 44 NYT 1 v

Adaptive Huffman Coding：( dynamic ) Encoding： start Read in symbol Is this the first appearance of the symbol Yes No Send code for NYT node followed by Index in the NYT list Code is the path from The root node to the corresponding node Call update procedure Node number max in block? No Yes stop

Adaptive Huffman Coding：( dynamic ) Decoding： start Go to root Of the tree Is the node an external node? No Read bit and go to corresponding node Yes Is the node the NYT node? Yes Read e bits Is the e-bit number p less than r? No Read e bits Yes Read one more bit Yes Is this the last bit? Call update procedure Decode the (P+1) element in NYT list stop

Updating： start First appearance for symbol? NYT gives birth to new NYT and External node Yes No Increment weight Of external node and old NYT node Go to symbol external node Node number max in block? Go to old NYT node Switch node with highest numbered node in block No Yes Go to symbol external node Is this the root node? Go to parent node Yes No stop