1、算法设计与分析*河南工程学院第5章 贪心算法 5.1 算法概述 5.2 背包问题 5.3 带有期限的作业排序 5.4 最优归并模式 5.5 哈夫曼编码 5.6 最小生成树 5.7 单源点最短路径算法设计与分析*河南工程学院 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似
2、。5.1 算法概述算法设计与分析*河南工程学院 贪心算法采用时逐步构造最优解得方法 在每个阶段，都在一定的标准下作出一个看上去最优的决策。决策一旦作出，就不可更改。作出这个局部最优决策所依照的标准称为贪心准则算法设计与分析*河南工程学院 贪心算法的特点：1 在当前状态下一旦选定一个分量，就不再重试其他的可行性；2 它并不从整体最优上作出考虑，它的选择只是在贪心准则下的局部最优选择算法设计与分析*河南工程学院 5.1.1 贪心选择性质 在求解一个问题的过程中，如果每一个阶段都是当前状态下的最优选择，即局部最优选择，并且最终能够求得问题的整体最优解算法设计与分析*河南工程学院 5.1.2 最优子结
3、构性质 当一个问题的最优解包括了这个问题的子问题的最优解时，就说这个问题具有最优子问题算法设计与分析*河南工程学院 5.1.3 活动安排问题 设总共有n项活动(1,2,n),并且所有的活动都需要使用同一个会场，而且任意两个活动不能同时使用这个会场。设活动i占用会场的时间时bi,ei),其中bi=ej then xi true ji;else xifalse;114算法设计与分析*河南工程学院 例：例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i12345678910 11Si 130535688212fi45678910 11 12 13 14算法设计与分析*河南工程
4、学院 算法算法greedySelector greedySelector 的的计算过程计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。算法设计与分析*河南工程学院 假设x是活动安排问题的一个最优解，并且选人x中的活动也是按照其结束的时间非减序排列的，设x中的第一个活动是i 当i=1时，x活动就是以贪心选择开始的最优解 如果i1,那么设一个新解x1=x-i 1 X2=x1-1 假设此子问题中可以找到另一个解y1,它比x2包含更多的活动，那么将活动1加到y1后就得到整个问题的一个最优解，与假设x是一个最优解想
5、矛盾。算法设计与分析*河南工程学院5.2 背包问题 已知一个可容纳重量为C的背包以及n种物品，其中第i件物品的重量为wi,每件物品的效益是pi(pi0).假设将第i件物品的一部分yi(0=yicu break;7 then yi1;8 cucu-wi;9 10 if i=n 11 then yicu/wi算法设计与分析*河南工程学院 设yn是Knapsack算法得出的向量解 1 如果任意的yi=1,那么这个解肯定是问题的最优解 2 否则，设j是yi1的最小下标。可知1=ij 时,yi=1 ji=n时，yi=0;i=j时，0=yi1 3 如果yn不是问题的最优解，则肯定存在一个可行解xn,满足【
6、piyi【pixi.根据约束条件可知,【wixi=C.若k是使xiyi的最小下标值，那么算法设计与分析*河南工程学院（1）假设kj,可知yk=1,因为xkyk,所以xkyk;(2)k=j,根据约束条件【wiyi=C,且当1=ij时，xi=yi=1,当jiyk,那么很明显【wixiC,不符合约束条件。所以，xkj,则【wixiC,这也是不可能的 有以上分析可知xkyk算法设计与分析*河南工程学院 假设增大xk的值，使得xk=yk,那么肯定是从(xk+1,xn)中减去了同样的量以保证所用的总容量仍是M。那么，又得到一个新的可行解zn。其中当1=i=k时，zi=yi,当ki=【pixi+【(zk-x
7、k)wk-【(xi-zi)wipi/wi =【pixi 1 如果【pizi0,当且仅但作业i在它的截止期限di之前完成时，才会获得效益值pi0算法设计与分析*河南工程学院 5.3.1 带有期限的作业排序算法 设 n=7,(p1,p2,.,p7)=(35,30,25,20,15,10,5)(d1,d7)=(4,2,4,3,4,8,3)算法设计与分析*河南工程学院GreedyJob(int n,int d,int&J)1 k1;d00;J00;J11;5 for j2 to n6 do rk;8 while dJrdi and dJrr9 do rr-1;12 if dJrr13 then 14
8、for jk to r+115 do J(j+1)Jj;)17 Jr+1i;kk+1;20 21 22 return k;算法设计与分析*河南工程学院 设有 n个作业，并且完成每个作业所需要的时间都是相同的，将这个时间设为单位时间；同时，每个作业i(1=i0，当作业i在它的截止期限di之前完成时，会获得效益值pi0.设J 是由GreedyJob算法得到的一个作业的集合，而W是由最优解组成的作业集合 那么，现在所要证明的就是J和W具有相同的效益值，从而J也是一组最优解算法设计与分析*河南工程学院 首先假设WJ,那么很明显W不可能是最最优解；根据贪心算法的基本思想可以确定J W是不可能的 所以，至
9、少有这样两个作业m和n，满足：m J并且m W，n W并且nJ 设m是满足m J 并且m W的一个具有最大效益值的作业。设n是满足n W并且n J的任意一个作业，那么当pnpm时，可以知道贪心算法会优先考虑作业n同时把作业n选人J中，这与n W相矛盾，所以可知对任意n W并且n J的作业n,都有pm=pn;算法设计与分析*河南工程学院 设作业i即时属于J有属于W的一个作业，同时，作业i在J中在t到t+1时刻被执行，而在W中它在t1到t1+1的时刻被执行。如果t=pn可知，在调整后的W 中的tm到tm+1时刻，如果将作业n去掉而执行作业m，那么就得到一个新的作业集合Wj算法设计与分析*河南工程学
10、院 5.3.2 改进的带有期限的作业排序算法 尽量推迟作业i的处理时间，给后继的作业留下尽可能大的选择空间 当选择了作业i时，在0,1,1,2,.di-1,di这些可行的时间段中，要尽量把作业i放在靠右的时间段算法设计与分析*河南工程学院FasterJob(int d,int&J,int n)1 for i0 to n2 do Fii;Pi-1;6 k0;7 for i1 to n8 do 9 rFind(min(n,d(i);10 if F(r)011 then 12 kk+1;J(k)i;14lFind(F(r)-1);15Union(l,i);16F(r)F(l);17 18 19 re
11、turn k算法设计与分析*河南工程学院 Union(int i,int j)1 xParent(i)+Parent(j)2 if Parent(i)Parent(j)3 then 4 Parent(i)j;5 Parent(j)x;6 7 else 8 Parent(j)i;9 Parent(i)x;10 算法设计与分析*河南工程学院 Find(i)1 ji;2 while Parent(j)0 3 do jParent(j);4 ki;5 while kj 6 do 7 tParent(k);8 Parent(k)j;9 kt;10 11 return j;算法设计与分析*河南工程学院5.
12、4 最优归并模式 假设有4个文件，分别用x1,x2,x3,x4表示，可以通过成对的重复归并已经分类的文件来完成这4个文件的归并 X1+x2=y1 X3+y1=y2 Y2+x4=算法设计与分析*河南工程学院 假设有a,b,c三个文件 分别有10个，20个和30个记录 第一种：（a+b)+c 第二种：（b+c)+a算法设计与分析*河南工程学院 每一步都归并两个最小的文件 每一步都只归并两个文件的归并称为二路归并模式。根据这种归并模式构造出来的二叉树称为二元归并树6030301020算法设计与分析*河南工程学院 Struct BiTnode 1 2 ElemTypeF weight;/节点的权值，文
13、件的记录数 3 struct BiTnode lchild,rchild;4 ;算法设计与分析*河南工程学院 Tree(BiTnode*I,n)1 kn 2 for i1 to n-1 3 do 4 BitNode*Tnew BiTNode 5 TlchildI1;6 TrchildI2;7 TweightI1.weight+I2.weight;8 for j3 to k-1 9 do 算法设计与分析*河南工程学院 10 if Ij.weight=Tweight 11 then Ij-1Ij;12 else Ij-1*T;17 Ij-1Ij;18 19 kk-1;20 21 return I1
14、.weight算法设计与分析*河南工程学院5.5 哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。1、前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码前缀码。算法设计与分析*河南工程学院5.5 哈夫曼编码 编码的前缀性质可以使译码方法非常简单。表示最优前缀码最优前缀码的二叉树总是一棵完全二叉树完全二叉树，即树
15、中任一结点都有2个儿子结点。平均码长平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码最优前缀码。)()()(cdcfTBTCc 算法设计与分析*河南工程学院5.5 哈夫曼编码2 2、构造哈夫曼编码、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。算法设计与分析*河南工程学院 在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以以f f为键值的优先队列为
16、键值的优先队列Q Q用在贪心选择贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间计算时间为O(nlogn)。算法设计与分析*河南工程学院 typedef struct 1 2 Elemty
17、pe weight;3 Elemtype parent,lchild,rchild;4 HTNode,HuffmanTree;Typedef char*HuffmanCode;算法设计与分析*河南工程学院HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,Elemtype*f,int n)1 if n=1 than return;2 m2*n-1;3 pHT(HuffmanTree)malloc(m+1)*sizeof(HTNode);4 for i1 to n5 do 6 *p*f,0,0,0;7 p+;w+;8 9 for in+1 to m10 do
18、11 *p0,0,0,0;12 p+;13 算法设计与分析*河南工程学院 14 for in+1 to m 15 do 16 Select(HT,i-1,s1,s2);17 HTs1.parenti;HTs2.parent=i;18 HTi.lchilds1;HTi.rchild=s2;19 HTi.weightHTs1.weight+HTs2.weight;20 21 HC(HuffmanCode)malloc(n+1)*sizeof(char);22 cd(char*)malloc(n*sizeof(char);23 cdn-1”0”;算法设计与分析*河南工程学院24 for i1 to
19、n25 do26 startn-1;tHTi.parent;ci;27 while c0;28 do 29 if HTt.lchildc;30 then cd-start033 else cd-start1;34 ct;35 tHTt.parent;36 37 HCi(char*)malloc(n-start)*sizeof(char);38 strcpy(HCi,&cdstart);39 40 free(cd);算法设计与分析*河南工程学院5.6 最小生成树 设G=(V,E)是无向连通带权图，即一个网络网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为
20、G的生成树。生成树上各边权的总和称为该生成树的耗费耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。例如例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。算法设计与分析*河南工程学院5.6 最小生成树1、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方
21、式不同，它们都利用了下面的最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MSTMST性质性质。算法设计与分析*河南工程学院5.6 最小生成树2 2、PrimPrim算法算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选贪心选择择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这
22、个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小最小生成树生成树。算法设计与分析*河南工程学院5.6 最小生成树利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合边集合T T始终始终包含包含G G的某棵最小生成树中的某棵最小生成树中的边的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。例如例如，对于右图中的带权图，按PrimPrim算法算法选取边的过程如下页图所示。算法设计与分析*河南工程学院5.6 最小生成树算法设计与分析*河南工程学院5.6 最小生成树在上述Prim算法中，还应当考虑如何有效地找出满如何有效地找出满足条件足条件i i S,jS
23、,j V-SV-S，且权，且权cijcij最小的边最小的边(i,j)(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间计算时间为)(2nO算法设计与分析*河南工程学院5.6 最小生成树3 3、KruskalKruskal算法算法Kruskal算法构造G的最小生成树的基本思想基本思想是，首先将G的n个顶点看成n个孤立的连通分支
24、。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。算法设计与分析*河南工程学院5.6 最小生成树例如，例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。算法设计与分析*河南工程学院5.6 最小生成树关于集合的一些基本运算集
25、合的一些基本运算可用于实现Kruskal算法。按权的递增顺序查看等价于对优先队列优先队列执行removeMinremoveMin运算。可以用堆堆实现这个优先队列。对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集并查集UnionFindUnionFind所支持的基本运算。当图的边数为e时，Kruskal算法所需的计算时间计算时间是 。当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。)log(eeO)(2ne)(2noe 算法设计与分析*河南工程学院5.7 单源最短路径给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还
26、给定V中的一个顶点，称为源源。现在要计算从源到所有其它各顶点的最短路长度最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题单源最短路径问题。1、算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。算法设计与分析*河南工程学院5.7 单源最短路径其基本思想基本思想是，设置顶点集合S并不断地作贪心选择贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每
27、次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。算法设计与分析*河南工程学院5.7 单源最短路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。算法设计与分析*河南工程学院5.7 单源最短路径迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,
28、4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代过程：算法设计与分析*河南工程学院5.7 单源最短路径2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。)(nO)(2nO)(2nO算法设计与分析*河南工程学院 批处理作业调度 Int n;/作业数 Int f1;/机器1完成处理时间 Int f;/完成时间和 Int best
29、f;/当前最优值 Int m;/各作业需要的处理时间 Int x;/当前作业调度 Int bestx;/当前最优作业调度 Int f2;/机器2完成处理时间算法设计与分析*河南工程学院TrackBack(int i)1 if(i=n)2 for (j=0;jn;j+)3 bestxj=xj;4 bestf=f;5 else6 for(j=i;j0)9 f2i=(f2i-1f1)?f2i-1:f1)+mxj2;10 else 11 f2i=f1+mxj2;12 f=f+f2i;13 if(fn)Compute();else for(int j=t;j=n;j+)swap(rt,rj);Backtrack(t+1);swap(rt,rj);其中，compute计算当前配对的竞赛优势的总和。void pref:Compute(void)for(int i=1,temp=0;i=n;i+)temp+=piri*qrii;if(tempbest)best=temp;for(int i=1;i=n;i+)bestri=ri;
