关闭

关闭

关闭

封号提示

内容

首页 第4章 贪心算法.ppt

第4章 贪心算法.ppt

第4章 贪心算法.ppt

上传者: 清风茶淡 2012-03-01 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《第4章 贪心算法ppt》,可适用于高等教育领域,主题内容包含第章贪心算法第章贪心算法第章贪心算法第章贪心算法顾名思义贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑它所作出的选择只是在符等。

第章贪心算法第章贪心算法第章贪心算法第章贪心算法顾名思义贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑它所作出的选择只是在某种意义上的局部最优选择。当然希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解但对许多问题它能产生整体最优解。如单源最短路经问题最小生成树问题等。在一些情况下即使贪心算法不能得到整体最优解其最终结果却是最优解的很好近似。第章贪心算法第章贪心算法本章主要知识点:活动安排问题贪心算法的基本要素最优装载哈夫曼编码单源最短路径最小生成树多机调度问题贪心算法的理论基础活动安排问题活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。活动安排问题活动安排问题设有n个活动的集合E={,,…,n}其中每个活动都要求使用同一资源如演讲会场等而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交则称活动i与活动j是相容的。也就是说当sifj或sjfi时活动i与活动j相容。活动安排问题活动安排问题在下面所给出的解活动安排问题的贪心算法greedySelector:publicstaticintgreedySelector(ints,intf,booleana){intn=slengtha=trueintj=intcount=for(inti=i<=ni){if(si>=fj){ai=truej=icount}elseai=false}returncount}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列活动安排问题活动安排问题由于输入的活动以其完成时间的非减序排列所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说该算法的贪心选择的意义是使剩余的可安排时间段极大化以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列算法只需O(n)的时间安排n个活动使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列可以用O(nlogn)的时间重排。活动安排问题活动安排问题例:设待安排的个活动的开始时间和结束时间按结束时间的非减序排列如下:活动安排问题活动安排问题算法greedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动而空白长条表示的活动是当前正在检查相容性的活动。活动安排问题活动安排问题若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi则不选择活动i否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题贪心算法greedySelector却总能求得的整体最优解即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。贪心算法的基本要素贪心算法的基本要素本节着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题怎么知道是否可用贪心算法解此问题以及能否得到问题的最优解呢这个问题很难给予肯定的回答。但是从许多可以用贪心算法求解的问题中看到这类问题一般具有个重要的性质:贪心选择性质和最优子结构性质。贪心算法的基本要素贪心算法的基本要素贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到。这是贪心算法可行的第一个基本要素也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题而贪心算法则通常以自顶向下的方式进行以迭代的方式作出相继的贪心选择每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题要确定它是否具有贪心选择性质必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心算法的基本要素贪心算法的基本要素最优子结构性质当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法的基本要素贪心算法的基本要素贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质这是类算法的一个共同点。但是对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解是否能用动态规划算法求解的问题也能用贪心算法求解下面研究个经典的组合优化问题并以此说明贪心算法与动态规划算法的主要差别。贪心算法的基本要素贪心算法的基本要素背包问题:给定n种物品和一个背包。物品i的重量是Wi其价值为Vi背包的容量为C。应如何选择装入背包的物品使得装入背包中物品的总价值最大在选择装入背包的物品时对每种物品i只有种选择即装入背包或不装入背包。不能将物品i装入背包多次也不能只装入部分的物品i。贪心算法的基本要素贪心算法的基本要素背包问题:与背包问题类似所不同的是在选择物品i装入背包时可以选择物品i的一部分而不一定要全部装入背包in。这类问题都具有最优子结构性质极为相似但背包问题可以用贪心算法求解而背包问题却不能用贪心算法求解。贪心算法的基本要素贪心算法的基本要素用贪心算法解背包问题的基本步骤:首先计算每种物品单位重量的价值ViWi然后依贪心选择策略将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后背包内的物品总重量未超过C则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去直到背包装满为止。具体算法可描述如下页:贪心算法的基本要素贪心算法的基本要素publicstaticfloatknapsack(floatc,floatw,floatv,floatx){intn=vlengthElementd=newElementnfor(inti=i<ni)di=newElement(wi,vi,i)MergeSortmergeSort(d)intifloatopt=for(i=i<ni)xi=for(i=i<ni){if(diw>c)breakxdii=opt=divc=diw}if(i<n){xdii=cdiwopt=xdii*div}returnopt}算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此算法的计算时间上界为O(nlogn)。当然为了证明算法的正确性还必须证明背包问题具有贪心选择性质。贪心算法的基本要素贪心算法的基本要素对于背包问题贪心选择之所以不能得到最优解是因为在这种情况下它无法保证最终能将背包装满部分闲置的背包空间使每公斤背包空间的价值降低了。事实上在考虑背包问题时应比较选择该物品和不选择该物品所导致的最终方案然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此动态规划算法的确可以有效地解背包问题。最优装载最优装载有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下将尽可能多的集装箱装上轮船。算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略可产生最优装载问题的最优解。具体算法描述如下页。最优装载最优装载publicstaticfloatloading(floatc,floatw,intx){intn=wlengthElementd=newElementnfor(inti=i<ni)di=newElement(wi,i)MergeSortmergeSort(d)floatopt=for(inti=i<ni)xi=for(inti=i<ndiw<=ci){xdii=opt=diwc=diw}returnopt}其中Element类说明为参见本书P最优装载最优装载贪心选择性质可以证明最优装载问题具有贪心选择性质。最优子结构性质最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性质容易证明算法loading的正确性。算法loading的主要计算量在于将集装箱依其重量从小到大排序故算法所需的计算时间为O(nlogn)。哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在~之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用串表示各字符的最优表示方式。给出现频率高的字符较短的编码出现频率较低的字符以较长的编码可以大大缩短总码长。前缀码对每一个字符规定一个,串作为其代码并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。哈夫曼编码哈夫曼编码编码的前缀性质可以使译码方法非常简单。表示最优前缀码的二叉树总是一棵完全二叉树即树中任一结点都有个儿子结点。平均码长定义为:使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。哈夫曼编码哈夫曼编码构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始执行|C|-次的“合并”运算后产生最终所要求的树T。哈夫曼编码哈夫曼编码在书上给出的算法huffmanTree中编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的棵具有最小频率的树。一旦棵具有最小频率的树合并后产生一棵新的树其频率为合并的棵树的频率之和并将新树插入优先队列Q。经过n-次的合并后优先队列中只剩下一棵树即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间由于最小堆的removeMin和put运算均需O(logn)时间n-次的合并总共需要O(nlogn)计算时间。因此关于n个字符的哈夫曼算法的计算时间为O(nlogn)。哈夫曼编码哈夫曼编码哈夫曼算法的正确性要证明哈夫曼算法的正确性只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。()贪心选择性质()最优子结构性质单源最短路径单源最短路径给定带权有向图G=(V,E)其中每条边的权是非负实数。另外还给定V中的一个顶点称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。单源最短路径单源最短路径其基本思想是设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时S中仅含有源。设u是G的某一个顶点把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从VS中取出具有最短特殊路长度的顶点u将u添加到S中同时对数组dist作必要的修改。一旦S包含了所有V中顶点dist就记录了从源到所有其他顶点之间的最短路径长度。单源最短路径单源最短路径例如对右图中的有向图应用Dijkstra算法计算从源顶点到其他顶点间最短路径的过程列在下页的表中。单源最短路径单源最短路径Dijkstra算法的迭代过程:单源最短路径单源最短路径算法的正确性和计算复杂性()贪心选择性质()最优子结构性质()计算复杂性对于具有n个顶点和e条边的带权有向图如果用带权邻接矩阵表示这个图那么Dijkstra算法的主循环体需要时间。这个循环需要执行n次所以完成循环需要时间。算法的其余部分所需要时间不超过。最小生成树最小生成树设G=(V,E)是无向连通带权图即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G’是一棵包含G的所有顶点的树则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如在设计通信网络时用图的顶点表示城市用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用则最小生成树就给出了建立通信网络的最经济的方案。最小生成树最小生成树最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这个算法做贪心选择的方式不同它们都利用了下面的最小生成树性质:设G=(V,E)是连通带权图U是V的真子集。如果(u,v)E且uUvVU且在所有这样的边中(u,v)的权cuv最小那么一定存在G的一棵最小生成树它以(u,v)为其中一条边。这个性质有时也称为MST性质。最小生成树最小生成树Prim算法设G=(V,E)是连通带权图V={,,…,n}。构造G的最小生成树的Prim算法的基本思想是:首先置S={}然后只要S是V的真子集就作如下的贪心选择:选取满足条件iSjVS且cij最小的边将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。最小生成树最小生成树利用最小生成树性质和数学归纳法容易证明上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此在算法结束时T中的所有边构成G的一棵最小生成树。例如对于右图中的带权图按Prim算法选取边的过程如下页图所示。最小生成树最小生成树最小生成树最小生成树在上述Prim算法中还应当考虑如何有效地找出满足条件iS,jVS且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置个数组closest和lowcost。在Prim算法执行过程中先找出VS中使lowcost值最小的顶点j然后根据数组closest选取边(j,closestj])最后将j添加到S中并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间为最小生成树最小生成树Kruskal算法Kruskal算法构造G的最小生成树的基本思想是首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始依边权递增的顺序查看每一条边并按下述方法连接个不同的连通分支:当查看到第k条边(v,w)时如果端点v和w分别是当前个不同的连通分支T和T中的顶点时就用边(v,w)将T和T连接成一个连通分支然后继续查看第k条边如果端点v和w在当前的同一个连通分支中就直接再查看第k条边。这个过程一直进行到只剩下一个连通分支时为止。最小生成树最小生成树例如对前面的连通带权图按Kruskal算法顺序得到的最小生成树上的边如下图所示。最小生成树最小生成树关于集合的一些基本运算可用于实现Kruskal算法。按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实现这个优先队列。对一个由连通分支组成的集合不断进行修改需要用到抽象数据类型并查集UnionFind所支持的基本运算。当图的边数为e时Kruskal算法所需的计算时间是。当时Kruskal算法比Prim算法差但当时Kruskal算法却比Prim算法好得多。多机调度问题多机调度问题多机调度问题要求给出一种作业调度方案使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NP完全问题到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。约定每个作业均可在任何一台机器上加工处理但未完工前不允许中断处理。作业不能拆分成更小的子作业。多机调度问题多机调度问题采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略当时只要将机器i的,ti时间区间分配给作业i即可算法只需要O()时间。当时首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。多机调度问题多机调度问题例如设个独立作业{,,,,,,}由台机器MM和M加工处理。各作业所需的处理时间分别为{,,,,,,}。按算法greedy产生的作业调度如下图所示所需的加工时间为。贪心算法的理论基础贪心算法的理论基础借助于拟阵工具可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。拟阵拟阵M定义为满足下面个条件的有序对(S,I):()S是非空有限集。()I是S的一类具有遗传性质的独立子集族即若BI则B是S的独立子集且B的任意子集也都是S的独立子集。空集必为I的成员。()I满足交换性质即若AI,BI且|A|<|B|则存在某一元素xBA使得A{x}I。贪心算法的理论基础贪心算法的理论基础例如设S是一给定矩阵中行向量的集合I是S的线性独立子集族则由线性空间理论容易证明(S,I)是一拟阵。拟阵的另一个例子是无向图G=(V,E)的图拟阵。给定拟阵M=(S,I)对于I中的独立子集AI若S有一元素xA使得将x加入A后仍保持独立性即A{x}I,则称x为A的可扩展元素。当拟阵M中的独立子集A没有可扩展元素时称A为极大独立子集。贪心算法的理论基础贪心算法的理论基础下面的关于极大独立子集的性质是很有用的。定理:拟阵M中所有极大独立子集大小相同。这个定理可以用反证法证明。若对拟阵M=(S,I)中的S指定权函数W使得对于任意xS有W(x)>则称拟阵M为带权拟阵。依此权函数S的任一子集A的权定义为。关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。贪心算法的理论基础贪心算法的理论基础给定带权拟阵M=(S,I)确定S的独立子集AI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的因此最优子集也一定是极大独立子集。例如在最小生成树问题可以表示为确定带权拟阵的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入经计算后输出M的最优子集A。贪心算法的理论基础贪心算法的理论基础Setgreedy(M,W){A=将S中元素依权值W(大者优先)组成优先队列while(S!=){SremoveMax(x)if(A{x}I)A=A{x}}returnA}贪心算法的理论基础贪心算法的理论基础算法greedy的计算时间复杂性为。引理(拟阵的贪心选择性质)设M=(S,I)是具有权函数W的带权拟阵且S中元素依权值从大到小排列。又设xS是S中第一个使得{x}是独立子集的元素则存在S的最优子集A使得xA。算法greedy在以贪心选择构造最优子集A时首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。贪心算法的理论基础贪心算法的理论基础引理:设M=(S,I)是拟阵。若S中元素x不是空集的可扩展元素则x也不可能是S中任一独立子集A的可扩展元素。引理(拟阵的最优子结构性质)设x是求带权拟阵M=(SI)的最优子集的贪心算法greedy所选择的S中的第一个元素。那么原问题可简化为求带权拟阵M’=(S’,I’)的最优子集问题其中:S’={y|yS且{x,y}I}I’={B|BS{x}且B{x}I}M’的权函数是M的权函数在S’上的限制(称M’为M关于元素x的收缩)。贪心算法的理论基础贪心算法的理论基础定理(带权拟阵贪心算法的正确性)设M=(S,I)是具有权函数W的带权拟阵算法greedy返回M的最优子集。任务时间表问题给定一个单位时间任务的有限集S。关于S的一个时间表用于描述S中单位时间任务的执行次序。时间表中第个任务从时间开始执行直至时间结束第个任务从时间开始执行至时间结束…第n个任务从时间n开始执行直至时间n结束。贪心算法的理论基础贪心算法的理论基础具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下。()n个单位时间任务的集合S={,,…,n}()任务i的截止时间,in,n即要求任务i在时间之前结束()任务i的误时惩罚,in,即任务i未在时间之前结束将招致的惩罚若按时完成则无惩罚。任务时间表问题要求确定S的一个时间表(最优时间表)使得总误时惩罚达到最小。贪心算法的理论基础贪心算法的理论基础这个问题看上去很复杂然而借助于拟阵可以用带权拟阵的贪心算法有效求解。对于一个给定的S的时间表在截止时间之前完成的任务称为及时任务在截止时间之后完成的任务称为误时任务。S的任一时间表可以调整成及时优先形式即其中所有及时任务先于误时任务而不影响原时间表中各任务的及时或误时性质。类似地还可将S的任一时间表调整成为规范形式其中及时任务先于误时任务且及时任务依其截止时间的非减序排列。贪心算法的理论基础贪心算法的理论基础首先可将时间表调整为及时优先形式然后再进一步调整及时任务的次序。任务时间表问题等价于确定最优时间表中及时任务子集A的问题。一旦确定了及时任务子集A将A中各任务依其截止时间的非减序列出然后再以任意次序列出误时任务即SA中各任务由此产生S的一个规范的最优时间表。对时间t=,,…,n设(A)是任务子集A中所有截止时间是t或更早的任务数。考察任务子集A的独立性。贪心算法的理论基础贪心算法的理论基础引理:对于S的任一任务子集A下面的各命题是等价的。()任务子集A是独立子集。()对于t=,,…,n(A)t。()若A中任务依其截止时间非减序排列则A中所有任务都是及时的。任务时间表问题要求使总误时惩罚达到最小这等价于使任务时间表中的及时任务的惩罚值之和达到最大。下面的定理表明可用带权拟阵的贪心算法解任务时间表问题。贪心算法的理论基础贪心算法的理论基础定理:设S是带有截止时间的单位时间任务集I是S的所有独立任务子集构成的集合。则有序对(S,I)是拟阵。由定理可知用带权拟阵的贪心算法可以求得最大权(惩罚)独立任务子集A以A作为最优时间表中的及时任务子集容易构造最优时间表。任务时间表问题的贪心算法的计算时间复杂性是。其中f(n)是用于检测任务子集A的独立性所需的时间。用引理中性质()容易设计一个时间算法来检测任务子集的独立性。因此整个算法的计算时间为。具体算法greedyJob可描述如P。贪心算法的理论基础贪心算法的理论基础用抽象数据类型并查集UnionFind可对上述算法作进一步改进。如果不计预处理的时间改进后的算法fasterJob所需的计算时间为。

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/58
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部