知識星球
（點選上方公眾號，可快速關註）
轉自：獨酌逸醉
http://www.cnblogs.com/chinazhangjie/archive/2010/11/23/1885330.html
顧名思義，貪心演演算法總是作出在當前看來最好的選擇。也就是說貪心演演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的區域性最優選擇。
當然，希望貪心演演算法得到的最終結果也是整體最優的。雖然貪心演演算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。
如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心演演算法不能得到整體最優解，其最終結果卻是最優解的很好近似。
問題一、活動安排問題
問題表述：設有n個活動的集合E = {1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。
每個活i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si
若區間[si, fi)與區間[sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當si >= fj或sj >= fi時，活動i與活動j相容。
由於輸入的活動以其完成時間的非減序排列，所以演演算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該演演算法的貪心選擇的意義是使剩餘的可安排時間段極大化，以便安排盡可能多的相容活動。
演演算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，演演算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。
例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：
演演算法greedySelector 的計算過程如下圖所示。圖中每行相應於演演算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。
若被檢查的活動i的開始時間Si小於最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。
貪心演演算法並不總能求得問題的整體最優解。但對於活動安排問題，貪心演演算法greedySelector卻總能求得的整體最優解，即它最終所確定的相容活動集合A的規模最大。這個結論可以用數學歸納法證明。
活動安排問題實現：
/* 主題：活動安排問題
* 作者：chinazhangjie
* 郵箱：chinajiezhang@gmail.com
* 開發語言：C++
* 開發環境：Vicrosoft Visual Studio
* 時間: 2010.11.21
*/
#include
#include
#include
using namespace std ;
struct ActivityTime
{
public:
ActivityTime (int nStart, int nEnd)
: m_nStart (nStart), m_nEnd (nEnd)
{ }
ActivityTime ()
: m_nStart (0), m_nEnd (0)
{ }
friend
bool operator < (const ActivityTime& lth, const ActivityTime& rth)
{
return lth.m_nEnd < lth.m_nEnd ;
}
public:
int m_nStart ;
int m_nEnd ;
} ;
class ActivityArrange
{
public:
ActivityArrange (const vector
& vTimeList) {
m_vTimeList = vTimeList ;
m_nCount = vTimeList.size () ;
m_bvSelectFlag.resize (m_nCount, false) ;
}
// 活動安排
void greedySelector ()
{
__sortTime () ;
// 第一個活動一定入內
m_bvSelectFlag[0] = true ;
int j = 0 ;
for (int i = 1; i < m_nCount ; ++ i) {
if (m_vTimeList[i].m_nStart > m_vTimeList[j].m_nEnd) {
m_bvSelectFlag[i] = true ;
j = i ;
}
}
copy (m_bvSelectFlag.begin(), m_bvSelectFlag.end() ,ostream_iterator
(cout, ” “)); cout << endl ;
}
private:
// 按照活動結束時間非遞減排序
void __sortTime ()
{
sort (m_vTimeList.begin(), m_vTimeList.end()) ;
for (vector
::iterator ite = m_vTimeList.begin() ; ite != m_vTimeList.end() ;
++ ite) {
cout << ite->m_nStart << “, “<< ite ->m_nEnd << endl ;
}
}
private:
vector
m_vTimeList ; // 活動時間安排串列 vector
m_bvSelectFlag ;// 是否安排活動標誌 int m_nCount ; // 總活動個數
} ;
int main()
{
vector
vActiTimeList ; vActiTimeList.push_back (ActivityTime(1, 4)) ;
vActiTimeList.push_back (ActivityTime(3, 5)) ;
vActiTimeList.push_back (ActivityTime(0, 6)) ;
vActiTimeList.push_back (ActivityTime(5, 7)) ;
vActiTimeList.push_back (ActivityTime(3, 8)) ;
vActiTimeList.push_back (ActivityTime(5, 9)) ;
vActiTimeList.push_back (ActivityTime(6, 10)) ;
vActiTimeList.push_back (ActivityTime(8, 11)) ;
vActiTimeList.push_back (ActivityTime(8, 12)) ;
vActiTimeList.push_back (ActivityTime(2, 13)) ;
vActiTimeList.push_back (ActivityTime(12, 14)) ;
ActivityArrange aa (vActiTimeList) ;
aa.greedySelector () ;
return 0 ;
}
貪心演演算法的基本要素
對於一個具體的問題，怎麼知道是否可用貪心演演算法解此問題，以及能否得到問題的最優解呢?這個問題很難給予肯定的回答。
但是，從許多可以用貪心演演算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質和最優子結構性質。
1、貪心選擇性質
所謂貪心選擇性質是指所求問題的整體最優解可以透過一系列區域性最優的選擇，即貪心選擇來達到。
這是貪心演演算法可行的第一個基本要素，也是貪心演演算法與動態規劃演演算法的主要區別。
動態規劃演演算法通常以自底向上的方式解各子問題，而貪心演演算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。
對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
2、最優子結構性質
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用動態規劃演演算法或貪心演演算法求解的關鍵特徵。
3、貪心演演算法與動態規劃演演算法的差異
貪心演演算法和動態規劃演演算法都要求問題具有最優子結構性質，這是2類演演算法的一個共同點。
但是，對於具有最優子結構的問題應該選用貪心演演算法還是動態規劃演演算法求解?是否能用動態規劃演演算法求解的問題也能用貪心演演算法求解?下麵研究2個經典的組合最佳化問題，並以此說明貪心演演算法與動態規劃演演算法的主要差別。
0-1揹包問題：
給定n種物品和一個揹包。物品i的重量是Wi，其價值為Vi，揹包的容量為C。應如何選擇裝入揹包的物品，使得裝入揹包中物品的總價值最大?
在選擇裝入揹包的物品時，對每種物品i只有2種選擇，即裝入揹包或不裝入揹包。不能將物品i裝入揹包多次，也不能只裝入部分的物品i。
揹包問題：
與0-1揹包問題類似，所不同的是在選擇物品i裝入揹包時，可以選擇物品i的一部分，而不一定要全部裝入揹包，1 <= i <= n。
這2類問題都具有最優子結構性質，極為相似，但揹包問題可以用貪心演演算法求解，而0-1揹包問題卻不能用貪心演演算法求解。
用貪心演演算法解揹包問題的基本步驟：
首先計算每種物品單位重量的價值Vi/Wi，然後，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入揹包。
若將這種物品全部裝入揹包後，揹包內的物品總重量未超過C，則選擇單位重量價值次高的物品並盡可能多地裝入揹包。依此策略一直地進行下去，直到揹包裝滿為止。
偽程式碼：
void Knapsack(int n,float M,float v[ ],float w[ ],float x[ ])
{
Sort(n,v,w);
int i;
for (i = 1 ; i <= n ; i++)
x[i] = 0;
float c=M;
for (i=1;i<=n;i++) {
if (w[i] > c) break;
x[i]=1;
c-=w[i];
}
if (i <= n)
x[i]=c / w[i];
}
演演算法knapsack的主要計算時間在於將各種物品依其單位重量的價值從大到小排序。因此，演演算法的計算時間上界為 O（nlogn）。
為了證明演演算法的正確性，還必須證明揹包問題具有貪心選擇性質。
對於0-1揹包問題，貪心選擇之所以不能得到最優解是因為在這種情況下，它無法保證最終能將揹包裝滿，部分閑置的揹包空間使每公斤揹包空間的價值降低了。
事實上，在考慮0-1揹包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然後再作出最好選擇。
由此就匯出許多互相重疊的子問題。這正是該問題可用動態規劃演演算法求解的另一重要特徵。實際上也是如此，動態規劃演演算法的確可以有效地解0-1揹包問題。
問題二、 哈夫曼編碼
哈夫曼編碼是廣泛地用於資料檔案壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼演演算法用字元在檔案中出現的頻率表來建立一個用0，1串表示各字元的最優表示方式。
給出現頻率高的字元較短的編碼，出現頻率較低的字元以較長的編碼，可以大大縮短總碼長。
|
a |
b |
c |
d |
e |
f |
|
|
頻率（千次） |
45 |
13 |
12 |
16 |
9 |
5 |
|
定長碼 |
000 |
001 |
010 |
011 |
100 |
101 |
|
變長碼 |
0 |
101 |
100 |
111 |
1101 |
1100 |
定長碼：3*(45+13+12+16+9+5) = 300 千位
變長碼：1*45+3*13+3*12+3*16+4*9+4*5 ＝ 224 千位
1、字首碼
對每一個字元規定一個0,1串作為其程式碼，並要求任一字元的程式碼都不是其它字元程式碼的字首。這種編碼稱為字首碼。
編碼的字首性質可以使譯碼方法非常簡單。
表示最優字首碼的二叉樹總是一棵完全二叉樹，即樹中任一結點都有2個兒子結點。
f(c)表示字元c出現的機率，dt(c)表示c的碼長
平均碼長定義為：
使平均碼長達到最小的字首碼編碼方案稱為給定編碼字符集C的最優字首碼。
2、構造哈夫曼編碼
哈夫曼提出構造最優字首碼的貪心演演算法，由此產生的編碼方案稱為哈夫曼編碼。
哈夫曼演演算法以自底向上的方式構造表示最優字首碼的二叉樹T。
演演算法以|C|個葉結點開始，執行|C|－1次的“合併”運算後產生最終所要求的樹T。
以f為鍵值的優先佇列Q用在貪心選擇時有效地確定演演算法當前要合併的2棵具有最小頻率的樹。
一旦2棵具有最小頻率的樹合併後，產生一棵新的樹，其頻率為合併的2棵樹的頻率之和，並將新樹插入優先佇列Q。經過n－1次的合併後，優先佇列中只剩下一棵樹，即所要求的樹T。
演演算法huffmanTree用最小堆實現優先佇列Q。初始化優先佇列需要O(n)計算時間，由於最小堆的removeMin和put運算均需O(logn)時間，n－1次的合併總共需要O(nlogn)計算時間。
因此，關於n個字元的哈夫曼演演算法的計算時間為O(nlogn) 。
3、哈夫曼演演算法的正確性
要證明哈夫曼演演算法的正確性，只要證明最優字首碼問題具有貪心選擇性質和最優子結構性質。
(1)貪心選擇性質
(2)最優子結構性質
實現：
/* 主題: Haffman編碼
* 作者: chinazhangjie
* 郵箱: chinajiezhang@gmail.com
* 開發環境 : Microsoft Visual Studio 2008
* 時間 : 2010.11.21
*/
#include
#include
#include
using namespace std ;
class HaffmanNode
{
public:
HaffmanNode (int nKeyValue,
HaffmanNode* pLeft = NULL,
HaffmanNode* pRight = NULL)
{
m_nKeyValue = nKeyValue ;
m_pLeft = pLeft ;
m_pRight = pRight ;
}
friend
bool operator < (const HaffmanNode& lth, const HaffmanNode& rth)
{
return lth.m_nKeyValue < rth.m_nKeyValue ;
}
public:
int m_nKeyValue ;
HaffmanNode* m_pLeft ;
HaffmanNode* m_pRight ;
} ;
class HaffmanCoding
{
public:
typedef priority_queue<HaffmanNode*> MinHeap ;
typedef HaffmanNode* HaffmanTree ;
public:
HaffmanCoding (const vector
& weight) : m_pTree(NULL)
{
m_stCount = weight.size () ;
for (size_t i = 0; i < weight.size() ; ++ i) {
m_minheap.push (new HaffmanNode(weight[i], NULL, NULL)) ;
}
}
~ HaffmanCoding()
{
__destroy (m_pTree) ;
}
// 按照左1右0編碼
void doHaffmanCoding ()
{
vector
vnCode(m_stCount–1) ; __constructTree () ;
__traverse (m_pTree, 0, vnCode) ;
}
private:
void __destroy(HaffmanTree& ht)
{
if (ht->m_pLeft != NULL) {
__destroy (ht->m_pLeft) ;
}
if (ht->m_pRight != NULL) {
__destroy (ht->m_pRight) ;
}
if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {
// cout << "delete" << endl ;
delete ht ;
ht = NULL ;
}
}
void __traverse (HaffmanTree ht,int layers, vector
& vnCode) {
if (ht->m_pLeft != NULL) {
vnCode[layers] = 1 ;
__traverse (ht->m_pLeft, ++ layers, vnCode) ;
— layers ;
}
if (ht->m_pRight != NULL) {
vnCode[layers] = 0 ;
__traverse (ht->m_pRight, ++ layers, vnCode) ;
— layers ;
}
if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {
cout << ht->m_nKeyValue << ” coding: “ ;
for (int i = 0; i < layers; ++ i) {
cout << vnCode[i] << ” “ ;
}
cout << endl ;
}
}
void __constructTree ()
{
size_t i = 1 ;
while (i < m_stCount) {
HaffmanNode* lchild = m_minheap.top () ;
m_minheap.pop () ;
HaffmanNode* rchild = m_minheap.top () ;
m_minheap.pop () ;
// 確保左子樹的鍵值大於有子樹的鍵值
if (lchild->m_nKeyValue < rchild->m_nKeyValue) {
HaffmanNode* temp = lchild ;
lchild = rchild ;
rchild = temp ;
}
// 構造新結點
HaffmanNode* pNewNode =
new HaffmanNode (lchild->m_nKeyValue + rchild->m_nKeyValue,
lchild, rchild ) ;
m_minheap.push (pNewNode) ;
++ i ;
}
m_pTree = m_minheap.top () ;
m_minheap.pop () ;
}
private:
vector
m_vnWeight ; // 權值 HaffmanTree m_pTree ;
MinHeap m_minheap ;
size_t m_stCount ; // 葉結點個數
} ;
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
淘口令：複製以下紅色內容，再開啟手淘即可購買
範品社，使用￥極客T恤￥搶先預覽（長按複製整段文案，開啟手機淘寶即可進入活動內容）
近期，北京地區正常發貨，但派件時間有所延長。
