Algorithm - Ch3 貪婪演算法 Greedy Algorithm

Chapter 3 貪婪演算法 Greedy Algorithm

3.1 貪婪演算法簡介

貪婪演算法(Greedy algorithm)是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體上最優(global optimization)加以考慮，他所做出的僅是在某種意義上的局部上最優的解(local optimization)。貪心演算法不是對所有問題都能得到整體最優解，但對範圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。

有些最佳化問題僅用很簡單的一個貪婪演算法就可解決，例如

Activity – selection problem : find maximum independent set in interval graph
Huffman codes
Min spanning tree problem : Kruskal’s algorithm and Prim’s algorithm (見Graph Algorithm)
Fractional knapsack problem

有些問題用貪婪演算法做雖然不一定能找到整體最佳解，卻能很有效率的找到一個不錯的近似解(常用來當作heuristic找NP-hard問題的近似解)

greedy set-covering algorithm (heuristic)
Approximate-Subset-Sum problem (Knapsack-problem)

[補充] 貪婪演算法可以獲得整體最佳解的充分必要條件是它必須具備一種稱為擬陣(matriod)的數學結構。其實應該說，貪婪演算法的正確性的來源正是擬陣。

一個關於有限集合 E 的擬陣是一個 (E,U) 對，U 是一個系統E的子集，滿足下列條件:

$\phi \in U$
$A \subseteq B , B \in U \Rightarrow A \in U$
$A ,B \in U 且\mid A \mid < \mid B \mid \Rightarrow \exists x \in B \setminus A 且 A \cup {x} \in U$

$\mid A \mid$是集合A的基數。例如 $A=\{a,b,c\}，\mid A \mid = 3 。$

3.2 經典貪婪演算法問題

活動選擇問題 (The activity – selection problem)

假設有n個活動提出申請要使用同一個資源，而這資源在同一時間點時最多只能讓一個活動使用，問題是：從這 n 個活動選一組數量最多，且可以用這個資源執行活動的集合。

正式定義題目 : We are given n activities $a_1,..., a_n$ where i-th activity $a_i = [s_i , f_i)$ starts at time $s_i$ and finishes at time $f_i$. They require the same resource (for example, one lecture hall). Two activities are $a_i$ and $a_j$ are compatible if $[s_i, f_i) ∩ [s_j , f_j ) = ∅$. The activity-selection problem (ASP) is to select a maximum size subset of mutually compatible activities.
解法 : Greedy choice. Select an activity with minimum $f_i$. Remove it and incompatible activities. Continue until no more activities left.
複雜度分析 : $O(nlogn)$，花在排序上。
概念補充

把撞期的行程，表示成圖，稱作 Interval Graph ，有著很特別的數學性質。工作排程問題等價於在interval graph中找maximum independent set。
在general graph中找max independent set是NP-hard問題。

霍夫曼編碼 (Huffman code)

霍夫曼編碼是一種編碼方式，是一種用於無損資料壓縮的熵編碼（權重編碼）演算法。出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字串的平均長度、期望值降低，從而達到無失真壓縮資料的目的。

正式定義題目 : Optimal code problem. Given an alphabet C of n characters and frequency of each character, find optimal prefix code so that the compressed file has minimum length. Huffman algorithm constructs the optimal tree T. The characters are the leaves of T.
解法 : select two vertices x and y of lowest frequency and replace them by a vertex z so that x and y are the children of z and the frequency of z is the sum of frequencies of x and y.
複雜度分析 : 使用binary min-heap資料結構 (Heap介紹詳見資料結構筆記)

建heap花費 $O(n)$ 的時間
每次 $ExtractMin()$ 和 $Insert()$ 花費 $O(log n)$ 的時間，這個動作重複做n次
因此整個演算法花費 $O(nlogn)$ 的時間

Reference

wiki - 擬陣

http://zh.wikipedia.org/wiki/%E6%8B%9F%E9%98%B5%E6%93%AC%E9%99%A3%E6%98%AF%E4%B8%80%E5%80%8B%E6%95%B8%E5%AD%B8%E7%B5%90%E6%A7%8B

wiki - interval graph

http://en.wikipedia.org/wiki/Interval_graph#Efficient_recognition_algorithms

CS6363: Design and Analysis of Computer Algorithms Prof. Sergey Bereg

http://www.csie.ntu.edu.tw/~b92109/course/CompAlg/slide8-greedy.pdf

Pages

2015年4月23日星期四