關(guān)于貪心算法詳解

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

當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。

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

基本思路：

1. 建立數(shù)學(xué)模型來描述問題。

⒉.把求解的問題分成若干個(gè)子問題。

⒊.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。

⒋.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。

實(shí)現(xiàn)該算法的過程：

⒈.從問題的某一初始解出發(fā);

2. while 能朝給定總目標(biāo)前進(jìn)一步 do

3.求出可行解的一個(gè)解元素;

4.由所有解元素組合成問題的一個(gè)可行解。從問題的某一初始解出發(fā)

背包問題

有一個(gè)背包，最多能承載150斤的重量，現(xiàn)在有7個(gè)物品，重量分別為[35, 30, 60, 50, 40, 10, 25]，它們的價(jià)值分別為[10, 40, 30, 50, 35, 40, 30]，應(yīng)該如何選擇才能使得我們的背包背走最多價(jià)值的物品？

把物品一個(gè)個(gè)的往包里裝，要求裝入包中的物品總價(jià)值最大，要讓總價(jià)值最大，就可以想到怎么放一個(gè)個(gè)的物品才能讓總的價(jià)值最大，因此可以想到如下三種選擇物品的方法，即可能的局部最優(yōu)解：

1：每次都選擇價(jià)值最高的往包里放。

2：每次都選擇重量最小的往包里放。

3：每次都選擇單位重量價(jià)值最高的往包里放。

4：選擇價(jià)值最高的，按照制訂的規(guī)則（價(jià)值）進(jìn)行計(jì)算，順序是：4 2 6 5 。

最終的總重量是：130；最終的總價(jià)值是：165。

2：選擇重量最小的，按照制訂的規(guī)則（重量）進(jìn)行計(jì)算，順序是：6 7 2 1 5 。

最終的總重量是：140；最終的總價(jià)值是：155?？梢钥吹剑亓績?yōu)先是沒有價(jià)值優(yōu)先的策略更好。

3:選擇單位密度價(jià)值最大的，按照制訂的規(guī)則（單位密度）進(jìn)行計(jì)算，順序是：6 2 7 4 1。

最終的總重量是：150；最終的總價(jià)值是：170。

可以看到，單位密度這個(gè)策略比之前的價(jià)值策略和重量策略都要好。

單源最大路徑問題

給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。

Dijkstra算法是解單源最短路徑問題的貪心算法。

其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。

初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長度。

Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度。

例如，對(duì)下圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列在下表中。

Dijkstra算法的迭代過程：

算法的正確性和計(jì)算復(fù)雜性

(1)貪心選擇性質(zhì)

(2)最優(yōu)子結(jié)構(gòu)性質(zhì)

(3)計(jì)算復(fù)雜性

對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要O(n)時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n)時(shí)間。算法的其余部分所需要時(shí)間不超過O(n^2)。

代碼實(shí)現(xiàn)(來自于第四個(gè)參考鏈接)：

#include #include #include using namespace std ;
class BBShortestDijkstra{public:  BBShortestDijkstra (const vector<vector<int> >& vnGraph)     :m_cnMaxInt (numeric_limits<int>::max())   {    m_vnGraph = vnGraph ;    m_stCount = vnGraph.size () ;    m_vnDist.resize (m_stCount) ;    for (size_t i = 0; i < m_stCount; ++ i) {      m_vnDist[i].resize (m_stCount) ;    }  }    void doDijkatra (){    int nMinIndex = 0 ;    int nMinValue = m_cnMaxInt ;    vector<bool> vbFlag (m_stCount, false) ;    for (size_t i = 0; i < m_stCount; ++ i) {      m_vnDist[0][i] = m_vnGraph[0][i] ;      if (nMinValue > m_vnGraph[0][i]) {        nMinValue = m_vnGraph[0][i] ;        nMinIndex = i ;      }    }
    vbFlag[0] = true ;    size_t k = 1 ;    while (k < m_stCount) {      vbFlag[nMinIndex] = true ;      for (size_t j = 0; j < m_stCount ; ++ j) {        // 沒有被選擇        if (!vbFlag[j] && m_vnGraph[nMinIndex][j] != m_cnMaxInt ) {          if (m_vnGraph[nMinIndex][j] + nMinValue            < m_vnDist[k-1][j]) {            m_vnDist[k][j] = m_vnGraph[nMinIndex][j] + nMinValue ;          }          else {            m_vnDist[k][j] = m_vnDist[k-1][j] ;          }        }        else {          m_vnDist[k][j] = m_vnDist[k-1][j] ;        }      }      nMinValue = m_cnMaxInt ;      for (size_t j = 0; j < m_stCount; ++ j) {        if (!vbFlag[j] && (nMinValue > m_vnDist[k][j])) {          nMinValue = m_vnDist[k][j] ;          nMinIndex = j ;        }      }      ++ k ;    }
    for (int i = 0; i < m_stCount; ++ i) {      for (int j = 0; j < m_stCount; ++ j) {        if (m_vnDist[i][j] == m_cnMaxInt) {          cout << "maxint " ;        }        else {          cout << m_vnDist[i][j] << " " ;        }      }      cout << endl ;    }  }private:   vector<vector<int> >  m_vnGraph ;  vector<vector<int> >  m_vnDist ;  size_t m_stCount ;  const int m_cnMaxInt ;} ;
int main(){  const int cnCount = 5 ;  vector<vector<int> > vnGraph (cnCount) ;  for (int i = 0; i < cnCount; ++ i) {    vnGraph[i].resize (cnCount, numeric_limits<int>::max()) ;  }  vnGraph[0][1] = 10 ;  vnGraph[0][3] = 30 ;  vnGraph[0][4] = 100 ;  vnGraph[1][2] = 50 ;  vnGraph[2][4] = 10 ;  vnGraph[3][2] = 20 ;  vnGraph[3][4] = 60 ;
  BBShortestDijkstra bbs (vnGraph) ;  bbs.doDijkatra () ;}

貪心算法三個(gè)核心問題

第一個(gè)問題：為什么不直接求全局最優(yōu)解?

1.原問題復(fù)雜度過高；

2.求全局最優(yōu)解的數(shù)學(xué)模型難以建立；

3.求全局最優(yōu)解的計(jì)算量過大；

4.沒有太大必要一定要求出全局最優(yōu)解，“比較優(yōu)”就可以。

第二個(gè)問題：如何把原問題分解成子問題？

1、按串行任務(wù)分

時(shí)間串行的任務(wù)，按子任務(wù)來分解，即每一步都是在前一步的基礎(chǔ)上再選擇當(dāng)前的最優(yōu)解。

2、按規(guī)模遞減分

規(guī)模較大的復(fù)雜問題，可以借助遞歸思想（見第2課），分解成一個(gè)規(guī)模小一點(diǎn)點(diǎn)的問題，循環(huán)解決，當(dāng)最后一步的求解完成后就得到了所謂的“全局最優(yōu)解”。

3、按并行任務(wù)分

這種問題的任務(wù)不分先后，可能是并行的，可以分別求解后，再按一定的規(guī)則（比如某種配比公式）將其組合后得到最終解。

第三個(gè)問題：如何知道貪心算法結(jié)果逼近了全局最優(yōu)值？

這個(gè)問題是不能量化判斷的，正是因?yàn)槿肿顑?yōu)值不能夠知道，所以才求的局部最優(yōu)值。追求過程需要考慮以下幾個(gè)問題:

1.成本

耗費(fèi)多少資源，花掉多少編程時(shí)間。

2.速度

計(jì)算量是否過大，計(jì)算速度能否滿足要求。

3.價(jià)值

得到了最優(yōu)解與次優(yōu)解是否真的有那么大的差別，還是說差別可以忽略。