一文詳解貪心算法

（點擊上方公眾號，可快速關注）

轉自：獨酌逸醉

www.cnblogs.com/chinazhangjie/archive/2010/11/23/1885330.html

顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。

如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。

問題一、活動安排問題

問題表述：設有n個活動的集合E = {1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。

每個活i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si < fi 。如果選擇了活動i，則它在半開時間區間[si, fi)內佔用資源。

若區間[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的規模最大。這個結論可以用數學歸納法證明。

活動安排問題實現：

 

代碼

#include <iostream>#include <vector>#include <algorithm>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<ActivityTime>& 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<bool> (cout, " "));        cout << endl ;    }
private:        void __sortTime ()     {        sort (m_vTimeList.begin(), m_vTimeList.end()) ;        for (vector<ActivityTime>::iterator ite = m_vTimeList.begin() ;                ite != m_vTimeList.end() ;                 ++ ite) {            cout << ite->m_nStart << ", "<< ite ->m_nEnd << endl ;        }    }
private:    vector<ActivityTime>    m_vTimeList ;        vector<bool>            m_bvSelectFlag ;    int    m_nCount ;    } ;
int main(){    vector<ActivityTime> 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)最優子結構性質
實現：

#include <iostream>#include <vector>#include <queue> 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<int>& 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) ;    }
        void doHaffmanCoding (){        vector<int> 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) {                        delete ht ;            ht = NULL ;        }    }    void __traverse (HaffmanTree ht,int layers, vector<int>& 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<int> m_vnWeight ;        HaffmanTree m_pTree ;    MinHeap        m_minheap ;    size_t        m_stCount ;        } ;

int main(){        vector<int> vnWeight ;    vnWeight.push_back (45) ;    vnWeight.push_back (13) ;    vnWeight.push_back (12) ;    vnWeight.push_back (16) ;    vnWeight.push_back (9) ;    vnWeight.push_back (5) ;
    HaffmanCoding hc (vnWeight) ;    hc.doHaffmanCoding () ;    return 0 ;}
覺得本文有幫助？請分享給更多人
關注「算法愛好者」加星標，修煉編程內功
好文章，我在看❤️