歡迎光臨
每天分享高質量文章

詳解貪心演算法

(點擊上方公眾號,可快速關註)

轉自:獨酌逸醉

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_stCount1) ;

__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恤¥搶先預覽(長按複製整段文案,打開手機淘寶即可進入活動內容)

近期,北京地區正常發貨,但派件時間有所延長。

赞(0)

分享創造快樂