第16章 貪心算法
-
- 定義及原理
- 活動選擇問題
-
- 問題描述及分析
- 遞歸實作
-
- 代碼實作
- 疊代實作
-
- 代碼實作
- 赫夫曼編碼
定義及原理
和動态規劃算法相比，貪心算法是一種更簡單、更高效的算法。它在每一步都住處當時看起來最佳的選擇，也就是說，它總是做出局部最優的選擇，寄希望于這樣的選擇能導出全局最優解。
貪心算法并不能保證得到最優解，但是對于一些問題，确實可以得到最優解。
一個貪心算法能夠求解一個最優化問題的兩個關鍵因素是：貪心選擇性質和最優子結構。
貪心選擇性質即可以通過做出局部最優選擇來構造全局最優解。
最優子結構性質，即一個問題的最優解包含其子問題的最優解。
活動選擇問題
問題描述及分析
假定有一個n個活動的集合S={a1，a2，……，an}。這些活動都使用同一個資源，而這個資源在同一時間隻能被一個活動使用(比如教室)。每一個活動ai有一個開始時間si和一個結束時間fi。開始時間早于結束時間。即活動在時間[si，fi)區間内執行。是以隻要兩個活動的執行區間不重疊，就相容。
用Sij表示在ai結束之後開始，且在aj開始之前結束的那些活動的集合。用c[i, j]表示集合Sij的最優解的大小。推出公式如下：
有這個公式，我們接下來可以很容易的設計一個帶備忘的遞歸算法，或者使用自底向上法求解。但是此問題采用貪心選擇可以更高效的求解。
貪心選擇：選擇符合邏輯的、最早結束的活動。
遞歸實作
代碼實作
/**
* 遞歸求解
*
* @param s 活動開始時間 下邊為0表示一個虛拟的活動a0，開始時間和結束時間都是0
* @param f 活動結束時間，且已按結束時間，從前到後，排序
* @param k S<sub>k<sub/> 表示在a<sub>k<sub/>結束後開始的任務合集
* @param n 問題規模
* @return 最多可進行的活動數量，如有需要，可以獲得活動id
*/
public static int recursive(int[] s, int[] f, int k, int n)
{
int m = k + 1;
// 找到最先結束的活動
while (m <= n && s[m] < f[k])
m++;
if (m <= n)
{
return recursive(s, f, m, n) + 1;
}
else
{
return 0;
}
}
疊代實作
使用疊代代替遞歸
代碼實作
/**
* 疊代求解
*
* @param s 活動開始時間 下邊為0表示一個虛拟的活動a0，開始時間和結束時間都是0
* @param f 活動結束時間，且已按結束時間，從前到後，排序
* @return
*/
public static List greedy(int[] s, int[] f)
{
int k = 0;
List result = new ArrayList<Integer>();
for (int m = 1; m < s.length; )
{
if (s[m] >= f[k])
{
result.add(m);
m = k;
}
}
return result;
}
赫夫曼編碼
赫夫曼編碼可以有效地壓縮資料。
由圖可知，變長編碼可以達到比定長編碼更好的壓縮率。
赫夫曼設計了一個貪心算法來構造最優字首碼（沒有任何碼字（二進制串）是其他碼字的字首），即赫夫曼編碼。
構造過程如下圖所示：