《算法设计与分析》第06章.ppt

第6章 贪心法,Greedy Algorithm,1,找零问题,假如售货员需要找给小孩67美分的零钱。现在，售货员手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促下，售货员想尽快将钱找给小孩。她的做法是：先找不大于67美分的最大硬币25美分硬币，再找不大于672542美分的最大硬币25美分硬币，再找不大于422517美分的最大硬币10美分硬币，再找不大于17107美分的最大硬币5美分硬币，最后售货员再找出两个1美分的硬币。至此，售货员共找给小孩6枚硬币。售货员的原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的硬币。,2,贪心法就是 只顾眼前利益，每次都选最好的。总是作出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。,3,6.1 一般方法 6.2 背包问题 6.3 带时限的作业排序 6.4 最佳合并模式 6.5 最小代价生成树 6.6 单源最短路径 6.7 磁带最优存储 6.8 贪心法的基本要素*贪心法的应用,4,6.1 一般方法,5,最优化问题（optimization problems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最优解（optimal solution）。,6,贪心法是通过分步决策（stepwise decision）的方法来求解问题的。贪心法每一步上用作决策依据的选择准则被称为最优量度标准（optimization criterion）。在根据最优量度标准选择分量的过程中，还需要使用一个可行解判定函数。贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。,7,【程序61】贪心法SolutionType Greedy(SType a,int n)SolutionType solution=;for(int i=0;in;i+)SType x=Select(a);if(Feasiable(solution,x)solution=Union(solution,x);return solution;,8,6.2 背包问题,9,6.2.1 问题描述,已知一个载重为M的背包和n件物品，第i件物品的重量为 wi，如果将第i件物品全部装入背包，将有收益pi，这里，wi0，pi0，0in。所谓背包问题是指求一种最佳装载方案，使得收益最大。所以，背包问题是现实世界一个常见的最优化问题。两类背包问题:如果每一件物品不能分割，只能作为整体或者装入背包，或者不装入，称为 0/1背包问题；如果物品是可以分割的，也就是允许将其中的一部分装入背包为一般背包问题或简称背包问题。,10,6.2.2 贪心法求解,背包问题 背包问题的解可以表示成一个n-元组：X=(x0,x1,xn1)，0 xi1，0in，每个xi是第i件物品装入背包中的部分。判定可行解的约束条件是：,11,背包问题的最优解必须使下列目标函数取最大值：,12,例61 设有载重能力M=20的背包，3件物品的重量为:（w0,w1,w2）=(18,15,10)，物品装入背包的收益为：（p0,p1,p2）=(25,24,15)。,13,【程序62】背包问题的贪心算法 templateclass Knapsack public:Knapsack(int mSize,float cap,float*wei,T*prof);void GreedyKnapsack(float*x);private:float m,*w;T*p;int n;,14,templatevoid Knapsack:GreedyKnapsack(float*x)/前置条件：wi已按pi/wi的非增次序排列 float u=m;for(int i=0;iu)break;xi=1.0;u=u-wi;if(i=n)xi=u/wi;,15,6.2.3 算法正确性,定理61 如果p0/w0p1/w1pn1/wn1，则程序62求得的背包问题的解是最优解。,16,6.3 带时限的作业排序,17,问题描述,设有一个单机系统、无其它资源限制且每个作业运行相等时间，不妨假定每个作业运行1个单位时间。现有n个作业，每个作业都有一个截止期限di0，di为整数。如果作业能够在截止期限之内完成，可获得pi0的收益。问题要求得到一种作业调度方案，该方案给出作业的一个子集和该作业子集的一种排列，使得若按照这种排列次序调度作业运行，该子集中的每个作业都能如期完成，并且能够获得最大收益。也就是说这种作业调度是最优的。,18,6.3.2 贪心法求解,例62 设有4个作业，每个作业的时限为(d0,d1,d2,d3)=(2,1,2,1),收益为(p0,p1,p2,p3)=(100,10,15,27)。,19,20,【程序63】带时限作业排序的贪心算法 void GreedyJob(int d,Set X,int n)/前置条件：p0p1,pn-1 X=0;for(int i=1;in;i+)if(集合 Xi 中作业都能在给定时限内完成)X=Xi;,21,算法正确性,定理62 程序63的贪心算法对于带时限作业排序问题将得到最优解。,22,23,24,可行性判定,定理63 X=（x0,x1,xk）是k个作业的集合，=（0,1,k）是X 的一种特定排列，它使得d0=d1=dk，其中，dj是作业j的时限。X是一个可行解当且仅当X中的作业能够按次序调度而不会有作业超期。,25,26,6.3.5 作业排序贪心算法,定理63提供了一种高效的可行解判定方法。使得在按最优量度标准，即按作业收益的非增次序选择下一个作业后，可以有效地判定是否可将该作业加入已生成的部分解向量X。,27,【程序64】带时限的作业排序程序int JS(int*d,int*x,int n)/设p0p1pn-1 int k=0;x0=0;for(int j=1;j=0,28,6.3.6 一种改进算法,本小节将介绍一种带时限作业排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的时间从(n2)减少到接近O(n)。,29,30,例63 设n=5个作业，作业的时限为:(d0,d1,d2,d3,d4)=(2,2,1,3,3),收益为:(p0,p1,p2,p3,p4)=(20,15,10,5,1)。,31,32,【程序65】使用并查集的带时限作业排序 int FJS(int*d,int*x,int n)UFSet s(n);int b,k=-1,*f=new intn+1;for(int i=0;i=n;i+)fi=i;,33,for(i=0;in;i+)if(ndi)b=n;else b=di;int r=s.Find(b);if(fr)x+k=i;int t=s.Find(fr-1);s.Union(t,r);fr=ft;delete f;return k;,34,35,6.4 最佳合并模式,36,问题描述,两路合并外排序算法通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将n个长度不等的有序子文件合并成一个有序文件。合并n个有序子文件成为一个有序文件的合并过程可以有多种方式，称为合并模式。在整个合并过程中，需从外存读写的记录数最少的合并方案称为最佳合并模式（optimal merge pattern）。,37,例64 设有5个有序子文件（F1,F2,F3,F4,F5），其长度分别为（20，30，30，10，5）。现通过两两合并将其合并成一个有序文件。,38,带权外路径长度是针对扩充二叉树而言的。扩充二叉树（extended binary tree）中除叶子结点外，其余结点都必须有两个孩子。扩充二叉树的带权外路径长度（weighted external path length）定义为：,39,贪心法求解,两路合并最佳模式问题的最优量度标准为带权外路径长度最小。,40,两路合并最佳模式的贪心算法简述如下：设Ww0,w1,wn1是n个有序文件的长度；以每个权值作为根结点值，构造n棵只有根的二叉树；选择两棵根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根的权值之和；重复第2步，直到合并成一棵二叉树为止。,41,【程序66】两路合并最佳模式的贪心算法templatestruct HNode/优先权队列中的元素的类型 operator T()const return weight;BTNode*ptr;T weight;,42,template BTNode*CreateHfmTree(T*w,int n)/w 为一维数组保存n个权值PrioQueue pq(2*n-1);BTNode*p;HNode a,b;for(int i=0;i(wi);a.ptr=p;a.weight=wi;pq.Append(a);,43,for(i=1;i(a.weight,a.ptr,b.ptr);a.ptr=p;pq.Append(a);pq.Serve(a);return a.ptr;,44,6.4.3 算法正确性,定理64设有n个权值W=w0,w1,wn1作为外结点的权值，构造两路合并树的贪心算法将生成一棵具有最小带权外路径长度的二叉树。,45,46,6.5 最小代价生成树,47,问题描述,问题一个无向连通图的生成树是一个极小连通子图，它包括图中全部结点，并且有尽可能少的边。一棵生成树的代价是树中各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的最小代价生成树（minimum-cost spanning tree）。,48,6.5.2 贪心法求解,最优量度标准 选择使得迄今为止已入选S中边的代价之和增量最小的边 克鲁斯卡尔算法的贪心准则是：按边代价的非减次序考察E中的边，从中选择一条代价最小的边e=(u,v)。普里姆算法的贪心准则是：在保证S所代表的子图是一棵树的前提下选择一条最小代价的边e=(u,v)。,49,【程序67】最小代价生成树的贪心算法ESetType SpanningTree(ESetType E,int n)/G=(V,E)为无向图 ESetType S=;int u,v,k=0;EType e;while(kn-1,50,普里姆算法,【程序68】普里姆算法 templatestruct ENode/带权图的边结点int adjVex;T w;ENode*nextArc;,51,template class Graphpublic:Graph(int mSize);void Prim();protected:void Prim(int k,int*nearest,T*lowcost);ENode*a;int n;,52,templatevoid Graph:Prim(int s)/公有成员函数int*nearest=new intn,*lowcost=new intn;Prim(s,nearest,lowcost);for(int j=0;jn;j+)cout(nearestj,“j,lowcostj);coutendl;delete nearest;delete lowcost;,53,templatevoid Graph:Prim(int k,int*nearest,T*lowcost)/私有成员函数 bool*mark=new booln;ENode*p;if(kn-1)throw OutofBounds;for(int i=0;in;i+)nearesti=-1;marki=false;lowcosti=INFTY;lowcostk=0;nearestk=k;markk=true;,54,for(i=1;inextArc)int j=p-adjVex;if(!markj)普里姆算法的运行时间是O(n2)。,55,56,6.5.4 克鲁斯卡尔算法,克鲁斯卡尔算法从边的集合E中，按照边的权值从小到大的次序依次选取边加以考察。template struct eNodeoperator T()const return w;int u,v;T w;,57,58,【程序69】克鲁斯卡尔算法 template void Graph:Kruskal(PrioQueue,59,while(kn-1 克鲁斯卡尔算法的时间复杂度为 O（elog e）。,60,6.5.5 算法正确性,定理65 设图G=（V，E）是一个带权连通图，U是V的一个真子集。若边(u,v)E是所有uU,vV-U的边中权值最小者，那么一定存在G的一棵最小代价生成树T=(V,S)，(u,v)S。这一性质称为MST（minimum spanning tree）性质。,61,定理66 普里姆算法和克鲁斯卡尔算法都将产生一个带权无向连通图的最小代价生成树。,62,6.6 单源最短路径,63,6.6.1 问题描述,单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，求从s到其余各结点的最短路径，其中，s称为源点。,64,65,贪心法求解,迪杰斯特拉（Dijkstra）算法首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。,66,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法templateclass MGraph public:MGraph(int mSize);void Dijkstra(int s,T*,67,private:int Choose(int*d,bool*s);T*a;int n;,68,template int MGraph:Choose(int*d,bool*s)int i,minpos;T min;min=INFTY;minpos=-1;for(i=1;in;i+)if(dimin,69,template void MGraph:Dijkstra(int s,T*,70,inSs=true;ds=0;for(i=1;in-1;i+)k=Choose(d,inS);inSk=true;for(j=0;jn;j+)if(!inSj,71,72,6.6.4 算法正确性,定理67 已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有i，iV-s，di(s,i)，且一旦di=(s,i)，它将不再改变。定理68 已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有结点i和j,iS，jV-S，必有didj。,73,74,定理69 已知带非负权值的有向图G=(V,E)，路径（s=v0,vi,vk=t）是从s到vk的一条最短路径，viV，0ikn，则子路径（s=v0,vi）和（vi,vk=t）必定分别是从s到vi 和vi到t的最短路径。定理610 已知带非负权值的有向图G=(V,E)，其源点为s，迪杰斯特拉算法结束时，对所有结点i，有di=(s,i)。,75,6.7 磁带最优存储,76,6.7.1 单带最优存储,问题 设有n个程序编号为0,n-1，存放在长度为L的磁带上，程序i在磁带上的存储长度为ai，0in。假定每个程序被检索地概率相等，则平均检索时间（mean retrieval time MRT）定义为 单带最优存储问题是求这n个程序的一种排列，使得MRT有最小值。,77,例65 设n=3，(a0,a1,a2)=(5,10,3)。,78,贪心法求解量度标准：计算迄今为止已选的那部分程序的D值，选择下一个程序应使得该值增加最小。定理611 设有n个程序0,1,n-1,程序i的长度为ai，0in，且有a0a1an1，=(0,1,n1)是这n个作业的一种排列。那么只有当j=j，0in时，D()=有最小值。,79,6.7.2 多带最优存储,问题 设有m1条磁带T0,T1,Tm1和n个程序。要求将此n个程序分配到这m条磁带上，令Ij,0jm 是存放在第j条磁带上的程序子集的某种排列，D(Ij)的定义如前面相同，那么，求m条磁带上检索一个程序的平均检索时间的最小值等价于求 的最小值。,80,【程序611】多带最优存储#include void Store(int n,int m)int j=0;for(int i=0;in;i+)cout 将程序i 加到磁带 jendl;j=(j+1)%m;coutendl;,81,定理612 设有n个程序0,1,n-1,程序i的长度为ai，0in，且有a0a1an1，程序611 实现将n个程序分配到m条磁带上，且有最小TD值。,82,6.8 贪心法的基本要素,83,6.8.1 最优量度标准,选择最优量度标准是使用贪心法求解问题的核心问题。贪心算法每一步作出的选择可以依赖以前作出的选择，但不依赖将来的选择，也不依赖于子问题的解。对于一个贪心算法，必须证明所采用的量度标准能够导致一个整体最优解。,84,6.8.2 最优子结构,最优子结构特性是关于问题最优解的特性。当一个问题的最优解中包含了子问题的最优解，则称该问题具有最优子结构特性（optimal substructure）。一般而言，如果一个最优化问题的解结构具有元组形式，并具有最优子结构特性，我们可以尝试选择量度标准。,85,贪心法的运用范围：明显的贪心（问题本身就是贪心）贪心数据结构（如：堆）可证明贪心策略的贪心（这是我们最常见的）博弈、游戏策略，这些策略大多是贪心求较优解或多次逼近,86,活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,87,活动安排问题,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi。如果选择了活动i，则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,88,算法描述,在下面所给出的解活动安排问题的贪心算法greedySelector:public static int greedySelector(int s,int f,boolean a)int n=s.length-1;a1=true;int j=1;int count=1;for(int i=2;i=fj)ai=true;j=i;count+;else ai=false;return count;,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,89,复杂性分析,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。,90,复杂性分析,算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,91,一个实例,例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,92,图示,算法greedySelector 的计算过程如右图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,93,说明,若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。,94,最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。该问题可形式化描述为其中变量xi=0表示不装入集装箱i，xi=1表示装入集装箱i。,95,算法描述,最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下：templatevoid 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,