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

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

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

基本思路：

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

⒉.把求解的問題分成若干個子問題。

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

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

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

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

2. while 能朝給定總目標前進一步 do

3.求出可行解的一個解元素;

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

背包問題

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

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

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

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

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

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

最終的總重量是：130；最終的總價值是：165。

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

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

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

最終的總重量是：150；最終的總價值是：170。

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

單源最大路徑問題

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

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

其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。

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

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

例如，對下圖中的有向圖，應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下表中。

Dijkstra算法的迭代過程：

算法的正確性和計算復雜性

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

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

(3)計算復雜性

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

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

#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 () ;}

貪心算法三個核心問題

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

1.原問題復雜度過高；

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

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

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

第二個問題：如何把原問題分解成子問題？

1、按串行任務分

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

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

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

3、按并行任務分

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

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

這個問題是不能量化判斷的，正是因為全局最優(yōu)值不能夠知道，所以才求的局部最優(yōu)值。追求過程需要考慮以下幾個問題:

1.成本

耗費多少資源，花掉多少編程時間。

2.速度

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

3.價值

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