第四章：贪心算法
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，达到最优。
本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/802717