第4章贪心算法.pptx
- 文档编号:18627896
- 上传时间:2023-08-21
- 格式:PPTX
- 页数:70
- 大小:2.18MB
第4章贪心算法.pptx
《第4章贪心算法.pptx》由会员分享,可在线阅读,更多相关《第4章贪心算法.pptx(70页珍藏版)》请在冰点文库上搜索。
,第4章贪心算法,顾名思义,贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。
当然,希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。
如单源最短路经问题,最小生成树问题等。
在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。
1,活动安排问题贪心算法的基本要素最优装载哈夫曼编码单源最短路径最小生成树多机调度问题,本章要点,4.1活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。
该问题要求高效地安排一系列争用某一公共资源的活动。
贪心算法提供了一个简单、有效的方法使得尽可能多的活动能兼容地使用公共资源。
4.1活动安排问题,设有n个活动的集合E=1,2,n,其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。
每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。
如果选择了活动i,则它在半开时间区间si,fi)内占用资源。
若区间si,fi)与区间sj,fj)不相交,则称活动i与活动j是相容的。
也就是说,当sifj或sjfi时,活动i与活动j相容。
活动选择问题输入:
S=1,2,n为n项活动的集合,si,fi分别为活动i的开始和结束时间,活动i与j相容sifj或sjfi.求:
最大的两两相容的活动集A实例策略1:
排序使得s1s2sn,从前向后挑选(按照开始时间早优先)策略2:
排序使得f1s1f2s2fnsn,从前向后挑选(按照短时间优先原则)策略3:
排序使得f1f2fn,从前向后挑选(按结束时间早优先)以上策略中的挑选都要注意满足相容性条件,4.1贪心法的设计思想,两个反例,策略1:
S=1,2,3,s1=0,f1=20,s2=2,f2=5,s3=8,f3=15,策略2:
S=1,2,3,s1=0,f1=8,s2=7,f2=9,s3=8,f3=15,4.1活动安排问题,publicstaticintgreedySelector(ints,intf,booleana)intn=s.length;a0=true;intj=0;intcount=1;for(inti=1;i=fj)ai=true;j=i;count+;elseai=false;returncount;,在下面所给出的解活动安排问题的贪心算法greedySelector:
各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,4.1活动安排问题,由于输入的活动以其完成时间的非减序排列,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。
直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。
也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
算法greedySelector的效率极高。
当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。
如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。
4.1活动安排问题,例:
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:
A=1,4,8,11,4.1活动安排问题,算法greedySelector的计算过程如左图所示。
图中每行相应于算法的一次迭代。
阴影长条表示的活动是已选入集合A的活动,而空白长条表示的活动是当前正在检查相容性的活动。
10,A=1,4,8,11,4.1活动安排问题,若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi,则不选择活动i,否则选择活动i加入集合A中。
贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题,贪心算法greedySelector却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。
这个结论可以用数学归纳法证明。
算法的正确性证明,证:
S=1,2,n是活动集,且f1fn归纳基础:
k=1,证明存在最优解包含活动1任取最优解A,A中的活动按截止时间递增排列.如果A的第一个活动为j,j1,令A=(Aj)1,由于f1fj,A也是最优解,且含有1.,定理算法Select执行到第k步,选择k项活动i1=1,i2,ik,那么存在最优解A包含i1=1,i2,ik.,根据定理:
算法至多到第n步得到最优解,归纳步骤:
假设命题对k为真,证明对k+1也为真.算法执行到第k步,选择了活动i1=1,i2,ik,根据归纳假设存在最优解A包含i1=1,i2,ik,A中剩下的活动选自集合S=i|iS,sifk,且A=i1,i2,ikB是最优解。
算法正确性证明(续),14,算法正确性证明(续),其中B是S的最优解.(反证法:
B不是S的最优解,设S的最优解为B*,B*的活动比B多,那么B*1,i2,ik是S的最优解,且比A的活动多,与A的最优性矛盾.)根据归纳基础,存在S的最优解B含有S中的第一个活动,即ik+1,且|B|=|B|,于是,也是原问题的最优解.,这里需要注意的是:
B*的元素个数比B大,而B的元素个数跟B一样的,只是组成不同,因而也同样可以作为最优解。
4.2贪心算法的基本要素,本节着重讨论可以用贪心算法求解的问题的一般特征。
对于一个具体的问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢?
这个问题很难给予肯定的回答。
但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:
贪心选择性质和最优子结构性质。
4.2贪心算法的基本要素,1、贪心选择性质,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
4.2贪心算法的基本要素,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
2、最优子结构性质,4.2贪心算法的基本要素,贪心算法和动态规划算法都要求问题具有最优子结构性质,这是2类算法的一个共同点。
但是,对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?
是否能用动态规划算法求解的问题也能用贪心算法求解?
下面研究2个经典的组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。
3、贪心算法与动态规划算法的差异,4.2贪心算法的基本要素,0-1背包问题:
给定n种物品和一个背包。
物品i的重量是Wi,其价值为Vi,背包的容量为C。
应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
19,在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。
不能将物品i装入背包多次,也不能只装入部分的物品i。
给定,要求找出一个n元0-1向量,4.2贪心算法的基本要素,背包问题:
与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1in。
这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。
给定,要求找出一个n元向量,4.2贪心算法的基本要素,首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去,直到背包装满为止。
具体算法可描述如下页:
21,用贪心算法解背包问题的基本步骤:
4.2贪心算法的基本要素,publicstaticfloatknapsack(floatc,floatw,floatv,floatx)intn=v.length;Elementd=newElementn;for(inti=0;ic)break;/若物品i的重量大于c,结束循环xdi.i=1;opt+=di.v;c-=di.w;if(in)xdi.i=c/di.w;/部分放入opt+=xdi.i*di.v;returnopt;,22,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。
因此,算法的计算时间上界为O(nlogn)。
当然,为了证明算法的正确性,还必须证明背包问题具有贪心选择性质。
完美图解,宝物清单,排序后宝物清单,运载力m=30,
(1)选择宝物2,剩余运载力为30-2=28,最大价值为8,
(2)选择宝物10,剩余运载力为28-5=23,最大价值为23,(3)选择宝物6,剩余运载力为23-8=15,最大价值为43,(4)选择宝物4,剩余运载力为15-9=6,最大价值为61,(5)选择宝物3,剩余运载力为6-5=1,最大价值为69,(6)选择宝物5,剩余运载力为1-1=0,最大价值为70.5,4.2贪心算法的基本要素,对于0-1背包问题,贪心选择之所以不能得到最优解是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。
事实上,在考虑0-1背包问题时,应比较选择该物品和不选择该物品所导致的最终方案,然后再作出最好选择。
由此就导出许多互相重叠的子问题。
这正是该问题可用动态规划算法求解的另一重要特征。
实际上也是如此,动态规划算法的确可以有效地解0-1背包问题。
贪心算法的特点,设计要素:
(1)贪心法适用于组合优化问题.求解过程是多步判断过程,最终的判断序列对应于问题的最优解.判断依据某种“短视的”贪心选择性质,性质的好坏决定了算法的成败.贪心法必须进行正确性证明贪心法的优势:
算法简单,时间和空间复杂性低,贪心法的正确性证明,数学归纳法1.叙述一个描述算法正确性的命题P(n),n为算法步数或者问题规模2.归纳基础:
P
(1)或P(n0)为真,n0为某个自然数3.归纳步骤:
P(k)P(k+1)第一数学归纳法k(kn)P(k)P(n)第二数学归纳法交换论证1.分析算法的解的结构特征2.从一个最优解逐步进行结构变换(替换成分、交换次序等)得到一个新的解(结构上与贪心算法的解更接近)3.证明:
上述变换最终得到算法的解,且变换在有限步结束,每步变换都保持解的最优性不降低.,贪心法:
将集装箱按照从轻到重排序,轻者先装,n个集装箱1,2,n装上轮船,集装箱i的重量wi,轮船装载重量限制为C,无体积限制.问如何装使得上船的集装箱最多?
不妨设wic.,4.3最优装载Loading,publicstaticfloatloading(floatc,floatw,intx)intn=w.length;Elementd=newElementn;for(inti=0;in;i+)di=newElement(wi,i);MergeSort.mergeSort(d);floatopt=0;for(inti=0;in;i+)xi=0;for(inti=0;in,28,其中Element类说明为参见本书P115,4.3最优装载Loading,完美图解,29,
(1)选择排序后的第1个,opt=2,
(2)选择排序后的第2个,opt=5,(3)选择排序后的第3个,opt=9,(4)选择排序后的第4个,opt=14,(5)选择排序后的第5个,opt=21,定理4.2对装载问题任何规模为k的输入,算法得到最优解.证明法对问题规模归纳.设集装箱从轻到重记为1,2,k.证:
k=1,只有1个箱子,算法显然正确.假设对于k个集装箱的输入,贪心法都可以得到最优解,考虑输入N=1,2,k+1,其中w1w2wk+1.由归纳假设,对于N=2,3,k+1,C=Cw1,贪心法得到最优解I.令I=1I,则I(算法解)是关于N的最优解.,正确性证明,正确性证明(续),反证法:
假设I不是最优,存在包含1的关于N的最优解I*(如果I*中没有1,用1替换I*中的第一个元素得到的解也是最优解),且|I*|I|;那么I*1是关于N和C的解且|I*1|I1|=|I|与I的最优性矛盾.,I*1,1,I*,I1,1,I,I*1,I1=I,I不是最优,1,2,k+1,2,3,k+1,4.4哈夫曼编码,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。
其压缩率通常在20%90%之间。
哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。
给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,可以大大缩短总码长。
1、前缀码对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其它字符代码的前缀。
这种编码称为前缀码。
非前缀码的例子a:
001,b:
00,c:
010,d:
01解码的歧义,例如字符串0100001解码1:
01,00,001d,b,a解码2:
010,00,01c,b,d,32,前缀码的二叉树及权值,前缀码:
00000,00001,0001,001,01,100,101,11频率:
00000:
5%,000001:
5%,0001:
10%,001:
15%,01:
25%,100:
10%,101:
10%,11:
20%平均的二进制位数B=(5+5)5+104+(15+10+10)3+(25+20)2/100=2.85最优前缀码权值B最小,40,编码的前缀性质可以使译码方法非常简单。
表示最优前缀码的二叉树总是一棵完全二叉树,即树中任一结点都有2个儿子结点。
平均码长定义为:
使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。
34,4.4哈夫曼编码,2、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
算法以|C|个叶结点开始,执行|C|1次的“合并”运算后产生最终所要求的树T。
35,4.4哈夫曼编码,在书上给出的算法huffmanTree中,编码字符集中每一字符c的频率是f(c)。
以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。
一旦2棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的2棵树的频率之和,并将新树插入优先队列Q。
经过n1次的合并后,优先队列中只剩下一棵树,即所要求的树T。
算法huffmanTree用最小堆实现优先队列Q。
初始化优先队列需要O(n)计算时间,由于最小堆的removeMin和put运算均需O(logn)时间,n1次的合并总共需要O(nlogn)计算时间。
因此,关于n个字符的哈夫曼算法的计算时间为O(nlogn)。
36,4.4哈夫曼编码,例如a:
45,b:
13;c:
12;d:
16;e:
9;f:
5,平均位数:
4(0.05+0.09)+3(0.16+0.12+0.13)+10.45=2.24,编码:
f-0000,e-0001,d-001,c-010,b011,a-1,f,e,d,c,b,a,5,9,16,12,13,45,完美图解,3、哈夫曼算法的正确性要证明哈夫曼算法的正确性,只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。
(1)贪心选择性质
(2)最优子结构性质,38,4.4哈夫曼编码,T和T的前缀码的平均码长之差为:
设C是字符集,cC,f(c)为频率,x,yC,f(x),f(y)频率最小,那么存在最优二元前缀码使得x,y的码字等长,且仅在最后一位不同.,fxfy,fbfcfxfb,fyfc,算法正确性证明:
贪心选择性质,T”表示的前缀码是最优前缀码,且x和y有最长码,且仅最后一位不同。
设T是表示字符集C的一个最优前缀码所对应的二叉树,C中字符c出现的频率为f(c)。
设x,yT,x,y是树叶兄弟,z是x,y的父亲,若将z看作具有f(z)=f(x)+f(y)的字符,则树T=Tx,y。
T是对应于二元前缀码C=(Cx,y)z的一个最优前缀码对应的二叉树,而且B(T)=B(T)+f(x)+f(y).,算法正确性证明(最优子结构性质),证cCx,y,有dT(c)=dT(c)f(c)dT(c)=f(c)dT(c)dT(x)=dT(y)=dT(z)+1.,若T所表示的前缀码不是最优的,并假设存在T”为最优,即B(T”)B(T)。
由于z被看作C中的一个字符,故z在T”中是一树叶。
若将x和y加入树T”中作为z的儿子,则可得到表示字符集C的前缀码的二叉树T”,且有B(T”)=B(T”)+f(x)+f(y)B(T)+f(x)+f(y)=B(T)成立但已知条件T是最优,故矛盾。
所以T所表示的字符集C的前缀码最优。
Huffman树应用:
文件归并,例问题:
给定一组不同长度的排好序文件构成的集合S=f1,fn其中fi表示第i个文件含有的项数.使用二分归并将这些文件归并成一个有序的文件.归并过程对应于二叉树:
文件为树叶.fi与fj归并的文件是它们的父结点.归并代价(最多的比较次数):
结点fi与fj归并代价为fi+fj1.总的代价:
每个文件(树叶)的深度乘以文件大小之和再减掉归并次数n1,实例,代价顺序归并:
(21+10+32+41)3+(18+70)25=483Huffman树归并:
(10+18)4+213+(70+41+32)25=456,实例:
S=21,10,32,41,18,70,4.5单源最短路径,给定带权有向图G=(V,E),其中每条边的权是非负实数。
另外,还给定V中的一个顶点,称为源。
现在要计算从源到所有其它各顶点的最短路长度。
这里路的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
1、算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。
43,其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。
一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时,S中仅含有源。
设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。
一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。
44,4.5单源最短路径,例如,对右图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。
45,4.5单源最短路径,Dijkstra算法的迭代过程:
4.5单源最短路径,动画演示,完美图解,初始化,将该点加入到S中,借桥更新最短距离,将该点加入到S中,借桥更新最短距离,将该点加入到S中,将该点加入到S中,借桥更新最短距离,V-S为空,算法停止。
由此,可求得从原点到其余各顶点的最短路径及长度,并可以通过前驱数组p逆向找到最短路径上经过的城市。
例如1到5的最短路径是:
1-2-3-5,算法正确性证明-贪心选择性质,
(1)根据算法可知,最短距离是最小的路长,故distxd(v,x)
(2)假设存在另外一条更短路红色线所示,故d(v,x)+d(x,u)=d(v,u)distu(3)由
(1)
(2)可知,distxdistu。
此为矛盾,因为若果(3)成立,此时应该选择x进入S集合,即选择具有最短特殊路径的顶点是x,而不是u。
(因为根据最短路径算法,总是选取最短路径的顶点进入S),最优子结构性质,该性质描述为:
如果S(i,j)=Vi.Vk.Vs.Vj是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么S(k,s)必定是从k到s的最短路径。
下面证明该性质的正确性。
假设S(i,j)=Vi.Vk.Vs.Vj是从顶点i到j的最短路径,则有S(i,j)=S(i,k)+S(k,s)+S(s,j)。
而S(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径S(k,s),那么S(i,j)=S(i,k)+S(k,s)+S(s,j)S(i,j)。
则与S(i,j)是从i到j的最短路径相矛盾。
因此该性质得证。
4.6最小生成树,设G=(V,E)是无向连通带权图,即一个网络。
E中每条边(v,w)的权为cvw。
如果G的子图G是一棵包含G的所有顶点的树,则称G为G的生成树。
生成树上各边权的总和称为该生成树的耗费。
在G的所有生成树中,耗费最小的生成树称为G的最小生成树。
网络的最小生成树在实际中有广泛应用。
例如,在设计通信网络时,用图的顶点表示城市,用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用,则最小生成树就给出了建立通信网络的最经济的方案。
51,1、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。
本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。
尽管这2个算法做贪心选择的方式不同,它们都利用了下面的最小生成树性质:
设G=(V,E)是连通带权图,U是V的真子集。
如果(u,v)E,且uU,vV-U,且在所有这样的边中,(u,v)的权cuv最小,那么一定存在G的一棵最小生成树,它以(u,v)为其中一条边。
这个性质有时也称为MST性质。
52,4.6最小生成树,2、Prim算法设G=(V,E)是连通带权图,V=1,2,n。
构造G的最小生成树的Prim算法的基本思想是:
首先置S=1,然后,只要S是V的真子集,就作如下的贪心选择:
选取满足条件iS,jV-S,且cij最小的边,将顶点j添加到S中。
这个过程一直进行到S=V时为止。
在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
53,4.6最小生成树,V1,3,6,5,2,1,6,5,5,4,6,V5,V4,V2,V6,V3,从UV1开始:
利用最小生成树性质和数学归纳法容易证明,上述算法中的边集合T始终包含G的某棵最小生成树中的边。
因此,在算法结束时,T中的所有边构成G的一棵最小生成树。
例如,对于右图中的带权图,按Prim算法选取边的过程如下页图所示。
动画演示,初始化,示例,将1放入U,更新边和结点,更新,将2加入U,更新边和结点,更新,将7加入U,更新边和结点,更新,将3加入U,更新边和结点,更新,58,将4加入U,更新边和结点,更新,将5加入U,选最小,更新边和结点,更新,完成最小生成树,prim算法正确性证明,60,反证法:
假设prim生成的不是最小生成树1).设prim生成的树为G02).假设存在Gmin使得cost(Gmin)不属于G03).将加入G0中可得一个环,且不是该环的最长边(这是因为Gmin),4).那环中必然存在一条边比长,这与prim每次生成最短边矛盾5).故假设不成立,命题得证.,3、Kruskal算法Kruskal算法构造G的最小生成树的基本思想是,首先将G的n个顶点看成n个孤立的连通分支。
将所有的边按权从小到大排序。
然后从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接2个不同的连通分支:
当查看到第k条边(v,w)时,如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时,就用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中,就直接再查看第k+1条边。
这个过程一直进行到只剩下一个连通分支时为止
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)