第四章：贪心算法

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

 

 

 

3，单源最短路径

 

 

 

4，最小生成树

 

Kruskal

Prim

template < class Type >

bool Kruskal(int n, int e, EdgeNode < Type > E[ ], EdgeNode < Type > t[ ] ){

               MinHeap < EdgeNode < Type > > H(1);

               H. Initialize(E, e, e);

               UnionFind U(n);

              int k = 0;

              while (e && k < n- 1) {

                    EdgeNode <int > 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<class Type>

Void Prim(int n,Type **c)

{     Type lowcost[maxint];

       int closest[maxint];

       bool s[maxint];

       s[1]=true;

       for(int I=2;I<=n;I++)

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

                closest[I]=1;

             s[I]=false;

       }

       for(int I=1;I<=n;k++)

       {    Type min=inf;

             int j=1;

             for(int k=2;k<=n;k++)

                 if((lowcost[k]<min)&&(!s[k]))

                {    min=lowcost[k];

                      j=k;      }

            cout<<j<<closet[j]<<endl;

       s[j]=true;

for(int k=2;k<=n;k++)

       if((c[j][k]<lowcost[k]&&(!s[k]))

        {

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

           closet[k]=j;

       }

}

}

 

 

5，7个独立的作业{a, b, c, d, e, f, g}，加工时间分别为{2，14，4，16，6，5，3}，3台机器：M1, M2, M3贪心调度结果：加工时间为17，达到最优。