算法与结构ppt课件 第五章 贪心法 old(华北电力大学科技学院).ppt

计算机算法设计与分析,North China Electric Power University,Computer Algorithms Design & Analysis,华北电力大学计算机科学与工程系,Dept. of Computer Science&Engineering of North China Electric Power University,第五章 贪心算法(Greedy Algorithm), 活动安排问题, 最优装载, 单源最短路径, 最小生成树, 多机调度问题,North China Electric Power University, 贪心算法的基本要素,例 找钱问题：,假定有四种面值分别为二角五分、一角、五分和一分，现要找给某顾客六角三分钱，问怎样找钱，才能使所拿出的硬币个数是最少的？,分析与解答：,1. 动态规划算法,设ak是找k分钱所需的最少硬币个数，则存在如下递归关系：,ak=1+minak-25,ak-10,ak-5,ak-1,2. 贪心算法：每次尽可能将面值大的硬币找给客户。,问题的解为：需要找6枚硬币，面值分别为： 25分，25分，10分，1分，1分，1分,该解是问题的一个整体最优解。,1 活动安排问题,North China Electric Power University,问题的描述:,设有n个活动的集合E=1,2, ,n,其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si 和结束时间fi 且si fi 。如果选择了活动i，则它在半开时间区间 si ,fi ) 内占用资源。若区间si ,fi )与区间sj ,fj ) 不相交，则称活动i与活动j是相容的。也就是说 ,当si fj或sj fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。 下面给出的算法GreedySelector中，各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非递减序排列。,North China Electric Power University,2.算法描述： template void GreedySelector(int n,Type s, Type f,bool A) A1=true;/表示活动进入相容集合，即活动被安排 int j=1;/进入相容集合的最后一个活动 for (int i=2;i=fj Ai=ture; j=i; else Ai=false; ,North China Electric Power University,集合A用来存储所选择的活动。活动i在集合A中，当且仅当Ai的值为ture。变量j用以记录最近一次加入到A中的活动。由于输入的活动是以其完成时间的非递减序排列的，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入A中。直观上按这种方法选择相容活动就为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相同活动。,3.例： 设待安排的11个活动的开始时间和结束时间按时间的非减序排列如下：,计算过程如图：,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,1,4,8,11,1,4,8,8,8,8,1,1,1,1,1,1,1,1,1,4,4,4,4,4,4,4,2,3,5,6,7,9,10,11,（ 时间 ）,2 贪心算法的基本要素,贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下确能达到预期的目的。下面讨论用贪心法求解的问题的一般特征。 贪心法两个重要的性质： 贪心选择性质和最优子结构性质。1.贪心选择性质（存在一个以贪心选择开始的最优解） 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 这是贪心算法可行的第一个基本要素。,2.最优子结构性质 当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。 该性质是可用动态规划或贪心算法求解的一个关键特性。,3.贪心算法和动态规划算法的差异 贪心算法和动态规划算法虽然都要求问题具有最优子结构性质，但是能用动态规划算法求解的问题不一定能用贪心法来求解。 下面用两个例子来说明一下：0-1背包问题：给定n种物品和一个背包。物品的i重量是wi，其价值为vi ，背包的容量为c。问应如何选择装入背包中的物品的总价值最大？,注意：在选择装入背包的物品时，对每中物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品装入背包时，可以选择物品的一部分，而不一定要全部装入背包。 分析：两个问题相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能。背包问题的贪心算法描述： 首先计算每种物品单位重量的价值vi/wi，然后,依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直到背包装满为止。,void Knapsack(int n ,float M ,float v ,float w ,float x) Sort(n,v,w); int i; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; 这种贪心策略对0-1背包问题就不适用了，因为它无法保证最终能将背包装满，部分背包空间的闲置使每千克背包空间所具有的价值降低了。而动态规划算法可以解决0-1背包问题。,3 最优装载,1.问题描述： 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi 。最优装载问题要求确定，在装载体积不受限制的情况下，应如何装载才能将尽可能多的集装箱上轮船。2.算法描述： 最优装载问题可用贪心法求解。采用重量最轻者先装的贪心选择策略，由此可得最优装载问题的一个最优解，具体算法描述如下：,template 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+) xi=0; for (int i=1;i=n ,3.贪心选择性质,设集装箱已依其重量从小到大排序，(x1,x2,xn)是最优装载问题的一个最优解。又设k=mini|xi=1。易知，如果给定的最优装载问题有解，则1 kn。1)当k=1时，(x1,x2,xn) 是一个满足贪心选择性质的最优解。2)当k1时，取y1=1;yk=0;yi=xi,1i n,in,则,因此， (y1,y2,yn)是所给最优装载问题的一个可行解。,另一方面，由 知， (y1,y2,yn)是一个满足贪心选择性质的最优解。所以，最优装载问题具有贪心选择性质。,4.最优子结构性质,设(x1,x2,xn) 是最优装载问题的一个满足贪心选择性质的最优解，则易知，x1=1, (x2,x3,xn) 是轮船载重量为c-w1且待装集装箱为2,3,n时相应最优装载问题的一个最优解。也就是说，最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法Loading的正确性。算法Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlog n)。,4 哈夫曼编码,哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法使用一个字符在文件中出现的频率表来建立一个用0，1串表示各符号的最优表示方式。,例：假设有一个数据文件包含100000个字符，用压缩的方式来存储它。该文件中各字符出现的频率如表：,若使用定长码，表示每个不同的字符需要3位：a=000，b=001，f=101。整个文件需300000位。使用变长码比定长码好的多，即给出现频率高的字符较短的编码，出现频率低的字符以较长的编码，其中字符a用0表示，f用4位串1100表示。整个文件的总码长为： =224 000 它比用定长码方案好，总码长减少了约25%。,1.前缀码对每一个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，称这样的代码具有前缀性质，或简称为前缀码。编码的前缀性质可以使译码方法简单。即可从编码文件中不断取出代表某一字符的前缀码，转换成原字符，继而译出文件。,给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为 。 也是字符c的前缀码长。该编码方案的平均码长定义为：B（T）= 使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。,2.构造哈夫曼编码 哈夫曼提出了一种构造哈夫曼前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以 个叶结点开始，执行 次的“合并”运算后产生最终所要求的树T。下面的算法中，,编码字符集中每一字符c的频率是f（c）。以f为键值的优先队列Q用以在作贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的两棵树的频率之和，并将新树插入优先队列Q。,算法中用到的类Huffman定义为： template class Huffman friend BinaryTree Huffman(Type ,int); public: operator Type( ) const return weight; private: BinaryTree tree Type weight; ;,算法HuffmanTree描述如下： template BinaryTree HuffmanTree(Type f ,int n) /生成单结点树 Huffman *w=new Huffman n+1; BinaryTree z, zero; for (int i=1; i Q(1);,Q.Initialize(w,n,n); /反复合并最小频率树 Huffman x,y; for (int i=1; in; i+) Q.DeleteMin(x); Q.DeleteMin(y); z.MakeTree(0, x.tree, y.tree); x.weight+=y.weight; x.tree=z; Q.Insert(x); Q.DeleteMin(x); Q.Deactivate( ); Delete w; return x.tree; ,5 单源最短路径,给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。计算从源到所有其他个顶点的最短路径长度。这里路的长度是指路上各边权之和。这个问题称为单源最短路径问题。,1.算法基本思想 设置一个顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，我们把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist来记录当前每个顶点所对应的最短特殊路径长度。算法每次从V-S中,取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。,2.算法描述如下： 输入的带权有向图是G=(V,E),V=1,2,n顶点v是源。c是一个二维数组，cij表示边(i,j)的权，不属于E时，cij是一个大数。Disti表示当前从源到顶点i的最短特殊路径长度。,template void Dijkstra(int n,int v,Type dist, int prev,Type * * c ) /单源最短路径问题的Dijkstra算法 bool smaxint;,for (int i=1;i=n;i+) disti=cvi; si=false; if (disti= =maxint) previ=0;/prev存储从源到i的最短路径/的前一个顶点 else previ=v; /初始化dist向量 distv=0;sv=true; for (int i=1;in;i+) int temp=maxint; int u=v; for (int j=1;j=n;j+) if(!sj),for(int j=1;j=n;j+) if(!sj) /对dist向量进行必要的修改 ,3.例：对有向图，用Dijkstra算法从源顶点1到其他顶点间最短路径的过程列在表中。,1,2,3,4,5,10,50,20,100,60,30,10,一个带权的有向图：,表：,Dijkstra算法的迭代过程,上述Dijkstra算法只求出从源顶点到其他顶点间的最短路径长度。如果还要求出相应的最短路径，可以用算法中数组prev记录的信息求出相应的最短路径。算法中数组prev记录的是从源到顶点i的最短路径上i的前一个顶点。如上面的例子，经Dijkstra计算后可得数组prev具有值prev2=1，prev3=4，prev4=1，prev5=3。如果要找出顶点1到顶点5的最短路径，可以从数组prev得到顶点5的前一个顶点是3，3的前一个顶点是4，4的前一个顶点是1。于是从顶点1到顶点5的最短路径是1，4，3，5。,6 最小生成树 设G=(V,E)是一个无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的一个子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。 网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,最小生成树性质 设G=(V,E)是一个连通带权图，U是V的一个真子集。如果 , 且 ， ，且在所有这样的边中,(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中的一条边。2.Prim算法 设G=(V,E)是一个连通带权图，V=1,2,n。构造G的一棵最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就做如下的贪心选择：选取满足条件 ，且cij最小的边，并将顶点j添加到S中。这个过程一直到S=V为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。,算法描述如下： void Prim(int n,Type * * c) T= ; S=1; while (S!=V) (i,j)= 且 的最小权边；, ,在上述Prim算法中，还应考虑如何有效地找出满足条件 且权cij最小的边(i,j)。实现这个目的的一个较简单的办法是设置两个数组closest和lowcost。对于每一个 ，closestj是j在S中的一个邻接顶点，它与j在S中的其他邻接点k相比较有cjclosestj=cjk。lowcostj的值就是cjclosestj。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。 算法如下： 其中，c是一个二维数组，cij表示边(i,j)的权。,template void Prim(int n,Type * *c) Type lowcostmaxint; int closestmaxint; bool smaxint; s1=true; for (int i=2; i=n; i+) lowcosti=c1i; closesti=1; si=false; for (int i=1; in; i+) Type min=inf; int j=1; for (int k=2; k=n; k+),if (lowcostkmin) ,3.Kruskal算法 基本思想是：首先将G的n个顶点看成n个孤立的连通分支，将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。 将按权的递增顺序查看的边的序列可以看作一个优先队列。另外，还要对一个由连通分支组成的集合不断进行修改，此集合记为U，则需要用到的集合的基本运算有：,（1）Union(a,b)：将U中两个连通分支a和b连接起来，所得的结果称为A或B。 （2）Find(v)：返回U中包含顶点v的连通分支的名字。这个运算用来确定某条边的两个端点所属的连通分支。算法如下： template class EdgeNode friend ostream,template bool Kruskal(int n,int e,EdgeNode E , EdgeNode t ) MinHeap H(1); H.Initialize(E,e,e); UnionFind U(n); int k=0; while (e,if (a!=b) tk+=x; U.union(a,b); H.Deactivate( ); return (k = =n-1);,7 多机调度问题,1.问题的描述： 设有n个独立的作业1，2，n，由m台相同的机器进行加工处理。作业i所需要的处理时间为ti 。现约定任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。 多机调度问题要求给出一种作业的调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是一个NP完全问题，到目前为止还没有一个有效的解法，对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的,近似算法。按此策略，当n小于等于m时，将机器i的0,ti时间区间分配给作业i即可。 当nm时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。2.算法描述如下： class JobNode friend void Greedy(JobNode *, int , int); friend void main (void); public: operator int ( ) const return time; private: int ID, time; ;,class MachineNode friend void Greedy(JobNode *, int , int); public: operator int( ) const return avail; private: int ID, avail; template void Greedy(Type a ,int n,int m) if (n=m) cout“为每个作业分配一台机器。”endl; return; Sort(a,n);,MinHeap H(m); MachineNode x; for (int i=1; i=1; i- -) H.DeleteMin(x); cout“将机器”x.ID“从” x.avail“到” (x.avail+ai.time) “的时间段分配给作业”ai.IDendl; x.avail+=ai.time; H.Insert(x); ,3.例： 设7个独立作业1，2，3，4，5，6，7由3台机器M1，M2和M3来加工处理。各作业所需的处理时间分别为2，14，4，16，6，5，3。 按算法Greedy产生的作业调度如下图所示，所需的加工时间为17。,4,M1,2,7,5,6 3,1,DUOJI,M2,M3,多机调度示例,