算法设计与分析复习——第四章:贪心算法

 

第四章:贪心算法

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},加工时间分别为{214416653}3台机器:M1, M2, M3贪心调度结果:加工时间为17,达到最优。

 

算法设计与分析复习——第四章:贪心算法


本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/802717


上一篇:企业日志分析之linux系统history收集展示


下一篇:申通快递双11云原生应用实践