算法設計與分析複習——第四章：貪心算法

1，貪心算法的設計思想是什麼，有什麼特點？如果一個問題用貪心算法可以獲得全局最優解，那麼該問題的求解應滿足哪些條件？

答：貪心算法的設計思想是在對問題求解時，總是做出在目前看來是最好的選擇。

它的特點是1）不是從整體考慮——得到的解可能不是全局最優 2）簡單，直接，易了解，效率高。

如使用貪心算法求解問題獲得全局最優解，則問題應滿足

1）貪心選擇性質（與動态規劃的主要差別）

所求問題的整體最優解可以通過一系列局部最優的選擇（即貪心選擇）來達到

2）最優子結構性質（動态規劃算法和貪心算法的共同點）

一個問題的最優解包含其子問題的最優解時。

用貪心法求解的問題應具備兩個特性：

（1）最優子結構性質

          問題的最優解包含着子問題的最優解。

（2）貪心選擇性質

          局部最優解的選擇整體最優解

2，貪心法與動态規劃法的比較

答：貪心法：目前狀态下，局部最優選擇，然後求解作出此選擇之後的子問題。貪心選擇依賴于以往作出的選擇，但不受将來所作的選擇，既不依賴于子問題的解。

動态規劃法：每步所作的選擇依賴于相關子問題的解，隻有在解出相關子問題以後，才能作出選擇。

3，如何證明一個問題具有貪心選擇性質？

答：思路：證明每步貪心選擇à問題的整體最優解。

證明步驟：

1）假設問題有一個整體最優解。

2）修改這個最優解，使其以貪心選擇開始，并且證明修改後的解仍然為最優解。

3）運用數學歸納法，證明：

    每一步貪心選擇問題的整體最優解。

    因為作出貪心選擇以後，根據最優子結構性質，原問題轉化為規模更小的子問題。

例題：

1，設n=8，[w1，…w8]=[100, 200, 50, 90, 150, 50, 20, 80]，c=400。

         解：所考察貨箱的次序為 :7, 3,  6,  8, 4, 1, 5,  2。貨箱7, 3, 6, 8, 4, 1的總重量為390個機關且已被裝載, 剩下的裝載能力為10 ,小于任意貨箱.是以得到解

[x1,...x8]=[ 1, 0, 1, 1,  0, 1, 1, 1]

template < class Type >

void Loading(int x[], Type w[], Type c, int n )

{ int *t = new int [n + 1];

   Sort(w, t, n) ; //按貨箱重量排序/

   for (int i = 1; i < = n; i ++)

         x[i] = 0;

   for (int i = 1;i<= n && w[t[i]] <= c; i++) {

             x[t[i]] = 1;

             c-= w[t[i]];}} //調整剩餘空間/

｝

2，

n  例：字元出現頻率與編碼方案

            a       b        c          d         e         f

頻率       45       13       12        16         9        5

定長碼     000     001      010       011        100      101

變長碼1    0      1         00        01         10       11

變長碼2    0      101      100      111         1101     1100

<a href="http://blog.51cto.com/attachment/201203/013503505.png" target="_blank"></a>

<a href="http://blog.51cto.com/attachment/201203/013545340.png" target="_blank"></a>

3，<b>單源最短路徑</b>

<a href="http://blog.51cto.com/attachment/201203/013633732.png" target="_blank"></a>

<a href="http://blog.51cto.com/attachment/201203/013713663.png" target="_blank"></a>

4，最小生成樹

<b>Kruskal</b>

<b></b>

<b>Prim</b>

bool Kruskal(int n, int e, EdgeNode &lt; Type &gt; E[ ], EdgeNode &lt; Type &gt; t[ ] ){

               MinHeap &lt; EdgeNode &lt; Type &gt; &gt; H(1);

               H. Initialize(E, e, e);

               UnionFind U(n);

              int k = 0;

              while (e &amp;&amp; k &lt; n- 1) {

                    EdgeNode &lt;int &gt; x;

                    H. DeleteMin(x);

                    e--;

                    int a = U.Find(x.u);

                    int b = U.Eind(x.v);

                    if (a! = b) {

                    t[k ++] = x;

                    U. Union(a, b);

}

                    H. Deactivate( )

renturn (k = = n-1);

Template&lt;class Type&gt;

Void Prim(int n,Type **c)

{     Type lowcost[maxint];

       int closest[maxint];

       bool s[maxint];

       s[1]=true;

       for(int I=2;I&lt;=n;I++)

       {    lowcost[I]=c[1][I];

                closest[I]=1;

             s[I]=false;

       }

       for(int I=1;I&lt;=n;k++)

       {    Type min=inf;

             int j=1;

             for(int k=2;k&lt;=n;k++)

                 if((lowcost[k]&lt;min)&amp;&amp;(!s[k]))

                {    min=lowcost[k];

                      j=k;      }

            cout&lt;&lt;j&lt;&lt;closet[j]&lt;&lt;endl;

       s[j]=true;

for(int k=2;k&lt;=n;k++)

       if((c[j][k]&lt;lowcost[k]&amp;&amp;(!s[k]))

        {

           lowcost[k]=c[j][k];

           closet[k]=j;

       }

<a href="http://blog.51cto.com/attachment/201203/013845177.png" target="_blank"></a>

5，7個獨立的作業{a, b, c, d, e, f, g}，加工時間分别為{2，14，4，16，6，5，3}，3台機器：M1, M2, M3貪心排程結果：加工時間為17，達到最優。

<a href="http://blog.51cto.com/attachment/201203/013945952.png" target="_blank"></a>

本文轉自 夢朝思夕 51CTO部落格，原文連結:http://blog.51cto.com/qiangmzsx/802717