第四章贪心算法.pptx
《第四章贪心算法.pptx》由会员分享,可在线阅读,更多相关《第四章贪心算法.pptx(77页珍藏版)》请在咨信网上搜索。
1、第四章.贪心算法贪心算法(Greed method)例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。目的:用以求解最优化问题 将问题的求解过程看作是一系列选择将问题的求解过程看作是一系列选择,每次选择一个每次选择
2、一个输入输入,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择(局部最优解局部最优解).).每作一次选择后每作一次选择后,所求问题会简化为一个规模更小的子所求问题会简化为一个规模更小的子问题问题.从而通过每一步的最优解逐步达到整体的最优解。从而通过每一步的最优解逐步达到整体的最优解。4.1 基本思想 算法优点算法优点求解速度快,时间复杂性有较低的阶.算法缺点算法缺点需证明是最优解.常见应用背包问题,最小生成树,最短路径,作业调度等等适用问题适用问题 具备具备贪心选择贪心选择和和最优子结构最优子结构性质的最优化问题性质的最优化问题贪心选择贪心选择性质:性质:整体的最优解可通过一系
3、列局部最优解达到,即整体的最优解可通过一系列局部最优解达到,即贪心选择到达。贪心选择到达。贪心算法通常以自顶向下的方式进行,以迭代的方式作出相贪心算法通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每做一次贪心选择就将所求解的问题化简为规模继的贪心选择,每做一次贪心选择就将所求解的问题化简为规模更小的问题更小的问题 对于一个具体问题,要确定它是否具有贪心选择的性质,我对于一个具体问题,要确定它是否具有贪心选择的性质,我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解,是从可以首先证明问题的
4、一个整体最优解,是从 贪心选择开始的,而贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。且作了贪心选择后,原问题简化为一个规模更小的类似子问题。然后,用数学归纳法证明,通过每一步作贪心选择,最终可得到然后,用数学归纳法证明,通过每一步作贪心选择,最终可得到问题的一个整体问题的一个整体 最优解。最优解。最优子结构性质最优子结构性质:当一个问题的最优解包含其子问题的最优解时,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。称此问题具有最优子结构性质。A(1)A(2)A(n-1)A(n)某一问题的n个输入B1(1)B1(2)B1(m)该问题的一种解(可
5、行解)是A的一个子集满足一定的条件约束条件Bk(1)Bk(2)Bk(m)目标函数取极值最优解算法设计与分析算法设计与分析 贪心算法贪心算法4.2.活动安排问题算法设计与分析算法设计与分析 贪心算法贪心算法活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。问题陈述问题陈述 设有n个活动的集合E=1,2,n,其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的
6、起始时间si和一个结束时间fi,且si fi。如果选择了活动i,则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交,则称活动i与活动j是相容的。也就是说,当sifj或sjfi时,活动i与活动j相容。1 2 3 4 5 6 7 8 9 10 11例例1 3 0 5 3 5 6 8 8 2 12 4 5 6 7 8 9 10 11 12 13 14isifi设待安排的设待安排的1111个活动起止时间按结束时间的非减序排列个活动起止时间按结束时间的非减序排列最大相容活动子集(1,4,8,111,4,8,11),也可表示为等长n元数组:(1,0,0,1,0,0,0,1
7、,0,0,1)算法思路算法思路将将n个活动按结束时间非减序排列个活动按结束时间非减序排列,依次考虑活动依次考虑活动i,若若i与已选择的活动相容与已选择的活动相容,则添加此活动到相容活动子集则添加此活动到相容活动子集.活动安排问题贪心算法templatevoid GreedySelector(int n,Type s,Type f,bool A)A 1 =true;int j=1;/从第二个活动开始检查是否与前一个相容 for(int i=2;i=fj)Ai=true;j=i;else A i=false;算法设计与分析算法设计与分析 贪心算法贪心算法各活动的起始时间和结各活动的起始时间和结束时
8、间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时间的非减序排列序排列 算法算法greedySelector greedySelector 的计算过程的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动,而空白长条表示的活动是当前正在检查相容性的活动。由于输入的活动以其完成时间的非减序非减序排列,所以算法greedySelector每次总是选择具有最早完成时间具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化使剩余的可安
9、排时间段极大化,以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。T(n)=O(nlogn)(未排序时)算法分析 T(n)=O(n)(排序时)算法证明 算法达到最优解.问题描述问题描述 输入输入:(x1,x2,.xn),xi=0,货箱货箱i不装船不装船;xi=1,货箱货箱i装船装船 可行解可行解:满足约束条件满足约束条件 c 的输入的输入 优化函数优化函数:最优解最优解:使优化函数达到最大值的一种输入
10、使优化函数达到最大值的一种输入.4.3 最优装载算法设计与分析算法设计与分析 贪心算法贪心算法算法思路算法思路 将装船过程划为多步选择,每步装一个货箱,每次从将装船过程划为多步选择,每步装一个货箱,每次从剩下的货箱中选择重量最轻的货箱剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。船或船上不能再容纳其他任何一个货箱。例设n=8,w1,w8=100,200,50,90,150,50,20,80,c=400。所考察货箱的次序为:7,3,6,8,4,1,5,2。货箱7,3,6,8,4,1的总重量为390个单位且已被装载,剩下的装
11、载能力为10,小于任意货箱.所以得到解x1,.x8=1,0,1,1,0,1,1,11、最优装载的贪心算法算法设计与分析算法设计与分析 贪心算法贪心算法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&wti 0,1 i n4-4 背包问题(Knapsack Problem)问题描述问题描述设有设有n个物体和一个背包个物体和一个背包,物体物体i的重量为的重量为wi,价值价值为为vi,背包的容量
12、为背包的容量为C.若将物体若将物体i的的xi部分部分(1 i n,0 xi 1)装装入背包入背包,则具有价值为则具有价值为vi xi.目标是找到一个方案目标是找到一个方案,使放入背使放入背包的物体总价值最高包的物体总价值最高.约约束束条条件件优化函优化函数数算法设计与分析算法设计与分析 贪心算法贪心算法背包问题实例背包问题实例考虑下列情况的背包问题考虑下列情况的背包问题n=3,M=20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的其中的4个可行解是:个可行解是:(x1,x2,x3)wi xivixi(1/2,1/3,1/4)16.524.25(1
13、,2/15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(1)1、用用贪贪心心策策略略求求解解背背包包问问题题时时,首首先先要要选选出出最最优优的的度度量量标标准准。可可以以选选取取目目标标函函数数为为量量度度标标准准,每每装装入入一一件件物物品品就就使使背背包包获获得得最最大大可可能能的的效效益益值值增增量量。在在这这种种量量度度标标准准下下的的贪贪心心方方法法就就是是按按效效益益值值的的非非增增次次序序将将物物品品一一件件件放到背包中件放到背包中。如如上上面面的的实实例例所
14、所示示,可可将将物物品品按按效效益益量量非非增增次次序序排排序序:(v1,v2,v3)=(25,24,15)。先先装装入入物物品品1重重量量为为18,即即x1=1;然然后后再再装装物物品品2,由由于于约约束束条条为为wi xi M=20,所所以物品以物品2只能装入重量为只能装入重量为2的一小部分,即的一小部分,即x2=2/15。按按上上述述的的数数据据选选择择策策略略,装装入入顺顺序序是是按按照照物物品品的的效效益益值值从从大大到到小小的的输输入入,由由刚刚才才的的方方法法可可得得这这种种情情况况下下的的总总效效益益值值为为v vixi=25+24*2/15=28.2,显显然然是是一一个个次次
15、优优解,原因是背包容量消耗过快。解,原因是背包容量消耗过快。算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(2)2、若若以以容容量量作作为为量量度度,可可让让背背包包容容量量尽尽可可能能慢慢地地被被消消耗耗。这这就就要要求求按按物物品品重重量量的的非非降降次次序序来来把把物物品品放放入入背包背包,即,即(w3,w2,w1)=(10,15,18)。先装入物品先装入物品3,x3=1,p3x3=15,再装入重量为,再装入重量为10的的物品物品2,vixi=15+24*10/15=31。由由刚刚才才的的方方法法可可得得这这种种情情况况下下的的总总效效益益值值
16、为为31,仍仍是是一一个个次次优优解解,原原因因是是容容量量在在漫漫漫漫消消耗耗的的过过程程中中,效效益益值却没有迅速的增加。值却没有迅速的增加。算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(3)3、采采用用在在效效益益值值的的增增长长速速率率和和容容量量的的消消耗耗速速率率之之间间取取得得平平衡衡的的量量度度标标准准。即即每每一一次次装装入入的的物物品品应应使使它它占占用用的的每每一一单单位位容容量量获获得得当当前前最最大大的的单单位位效效益益。这这就就需需使使物物品品的的装装入入次次序按序按vi/wi比值的非增次序来考虑比值的非增次序来考虑。这
17、种策略下的量度是已装入物品的累计效益值与所用这种策略下的量度是已装入物品的累计效益值与所用容量之比。容量之比。(v2/w2,v3/w3,v1/w1)=(24/15,15/10,25/18)先装入重量为先装入重量为15的物品的物品2,在装入重量为,在装入重量为5的物品的物品3,pixi=24+15*5/10=31.5。此结果为最优解。此结果为最优解。算法设计与分析算法设计与分析 贪心算法贪心算法算法思路1).将各物体按单位价值由高到低排序.2).取价值最高者放入背包.3).计算背包剩余空间.4).在剩余物体中取价值最高者放入背包.若背包剩余容量=0或物体全部装入背包为止 例例 n=3,c=20(
18、v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)x1,x2,x3 0,2/3,10,1,1/2.1,2/15,020202028.23131.5.算法设计与分析算法设计与分析 贪心算法贪心算法void Knapsack(int n,float M,float v,float w ,float x)Sort(n,v,w,t);/按单位价值排序/int i;for(i=1;i=n;i+)xi=0;float c=M;/c为背包剩余空间/for(i=1;i c)break;xti=1;c-=wti;if(i 贪心算法贪心算法算法分析算法分析:排序为主要算法时间,所
19、以 T(n)=O(nlogn)背包问题中的物体不能分拆背包问题中的物体不能分拆,只能整个装入称为只能整个装入称为0-10-1背背包问题包问题.算法证明算法证明:该算法能得到在最优解 用贪心算法能得到用贪心算法能得到0-10-1背包的最优解吗背包的最优解吗?首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值V Vi i/W/Wi i,然后,依贪,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过总重量未超过C C,则选择单位
20、重量价值次高的物品并尽可,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包能多地装入背包。依此策略一直地进行下去,直到背包装满为止。装满为止。具体算法可描述如下页:具体算法可描述如下页:void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for(i=1;i=n;i+)xi=0;float c=M;for(i=1;ic)break;xi=1;c-=wi;if(i 贪心算法贪心算法思考题找找零零钱钱问问题题:一一个个小小孩孩买买了了价价值值为为3333美美分分的的糖糖,并并将将
21、1 1美美元元的的钱钱交交给给售售货货员员。售售货货员员希希望望用用数数目目最最少少的的硬硬币币找找给给小小孩孩。假假设设提提供供了了数数目目不不限限的的面面值值为为2525美美分分、1010美美分分、5 5美美分分、及及1 1美美分分的的硬硬币币。使使用用贪贪心心算算法法求求解解最最优优结结果果。并并证证明明找找零零钱钱问问题题的的贪贪心心算算法法总总能能产产生具有最少硬币数的零钱。生具有最少硬币数的零钱。算法设计与分析算法设计与分析 贪心算法贪心算法问题问题:通讯过程中需将传输的信息转换为二进制码通讯过程中需将传输的信息转换为二进制码.由于英文由于英文字母使用频率不同字母使用频率不同,若频
22、率高的字母对应短的编码若频率高的字母对应短的编码,频率低的频率低的字母对应长的编码字母对应长的编码,传输的数据总量就会降低传输的数据总量就会降低.要求找到一个要求找到一个编码方案编码方案,使传输的数据量最少使传输的数据量最少.见见P109-P109-表表4-14-1 算法设计与分析算法设计与分析 贪心算法贪心算法1、前缀码、前缀码 为能正确译码为能正确译码,编码需采用编码需采用前缀码前缀码,对每一个字符规定一个对每一个字符规定一个0,1串作为其代码,并要求任一字符的串作为其代码,并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。代码都不是其它字符代码的前缀。这种编码称为前缀码。
23、表示最优前缀码的二叉树总是一棵完全二叉树,即树中任一表示最优前缀码的二叉树总是一棵完全二叉树,即树中任一结点都有结点都有2个儿子结点。个儿子结点。平均码长定义为:平均码长定义为:使平均码长达到最小的前缀码编码方案称为给定编码字符集使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。的最优前缀码。4.4 哈夫曼编码算法思路:算法思路:1)以以n个字母为结点构成个字母为结点构成n棵仅含一个点的二叉树集合棵仅含一个点的二叉树集合,字母的频率字母的频率 即为结点的权即为结点的权2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树每次从二叉树集合中找出两个权最小者合并为一棵二叉树:增加
24、增加一个根结点将这两棵树作为左右子树一个根结点将这两棵树作为左右子树.新树的权为两棵子树的权之新树的权为两棵子树的权之和和.3)反复进行步骤反复进行步骤2)直到只剩一棵树为止直到只剩一棵树为止.2、构造哈夫曼编码、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始,执行|C|1次的“合并”运算后产生最终所要求的树T。算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码 template BinaryTreeHuffmanTree(T f,int n)/根据
25、权f1:n构造霍夫曼树 /创建一个单节点树的数组 Huffman*W=newHuffman n+1;BinaryTree z,zero;for(int i=1;i=n;i+)z.MakeTree(i,zero,zero);Wi.weight=fi;Wi.tree=z:/数组变成个最小堆 MinHeapHuffmanQ(1);Q.Initialize(w,n,n);/将堆中的树不断合并 Huffman x,y for(i=1;i 贪心算法贪心算法 哈夫曼编码哈夫曼编码 在书上给出的算法huffmanTree中,编码字符集中每一字符c的频率是f(c)。以以f f为键值的优先队列为键值的优先队列Q
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 贪心 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。