计算机常用算法与程序设计教程 第5章 贪心算法.ppt

1常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5.1贪心算法概述贪心算法概述5.2贪心算法的理论基础贪心算法的理论基础5.3删数字问题删数字问题5.4背包问题背包问题5.5覆盖问题覆盖问题5.6图的着色问题图的着色问题5.7遍历问题遍历问题5.8最小生成树最小生成树5.9哈夫曼编码哈夫曼编码2常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5.1贪心算法概述贪心算法概述5.1.1贪心算法贪心算法 有一艘大船准备用来装载货物。所有待装货物都装在有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第相同。设第i个货箱的重量为个货箱的重量为wi（1in），而货船的最大），而货船的最大载重量为载重量为c，我们的目的是在货船上装入最多的货物。，我们的目的是在货船上装入最多的货物。这个问题可以作为最优化问题进行描述：设存在一组这个问题可以作为最优化问题进行描述：设存在一组变量变量xi，其可能取值为，其可能取值为0或或1。如。如xi为为0，则货箱，则货箱i将不被装将不被装上船；如上船；如xi为为1，则货箱，则货箱i将被装上船。我们的目的是找到将被装上船。我们的目的是找到一组一组xi，使它满足限制条件，使它满足限制条件ni=wixic且且xi0,1,1in。相应的优化函数是。相应的优化函数是ni=wixi取极值取极值。满足限制条。满足限制条件的每一组件的每一组xi都是一个可行解，能使都是一个可行解，能使ni=wixi取得极大值取得极大值的方案是最优解。的方案是最优解。3常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计贪心算法（也称贪心策略）总是作出在当前看来是最好贪心算法（也称贪心策略）总是作出在当前看来是最好的选择。如上面的找硬币问题本身具有最优子结构性质，的选择。如上面的找硬币问题本身具有最优子结构性质，它可以用动态规划算法来解。但我们看到，用贪心算法更它可以用动态规划算法来解。但我们看到，用贪心算法更简单，更直接且解题效率更高。这利用了问题本身的一些简单，更直接且解题效率更高。这利用了问题本身的一些特性。特性。贪心算法在求解最优化问题时，从初始阶段开始，每一贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择，不断把将问题个阶段总是作一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优最优考虑，它所作出的选择只是在某种意义上的局部最优选择。这样处理，对大多数优化问题来说能得到最优解，选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。从求解效率来说，贪心算法比动态规但也并不总是这样。从求解效率来说，贪心算法比动态规划更高，且不存在空间限制的影响。另外，对一些划更高，且不存在空间限制的影响。另外，对一些NP完全完全问题或规模很大的优化问题，可通过仿贪心算法能得到很问题或规模很大的优化问题，可通过仿贪心算法能得到很好的近世解，而用动态规划根本无法解。好的近世解，而用动态规划根本无法解。4常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5.1.2.贪心算法的基本思想贪心算法的基本思想 贪心算法的基本思想是通过一系列选择步骤来构造问题贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：的完整解。所做的每一步选择都必须满足：(1)可行的：必须满足问题的约束。可行的：必须满足问题的约束。(2)局部最优：当前所有可能的选择中最佳的局部选择。局部最优：当前所有可能的选择中最佳的局部选择。(3)不可取消不可取消:选择一旦做出，在后面的步骤中就无法选择一旦做出，在后面的步骤中就无法改变了。改变了。贪心算法是通过做一系列的选择来给出某一问题的最优贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择。这种启发式策略并不总是能产生出最优解。的选择。这种启发式策略并不总是能产生出最优解。5常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5.2贪心算法的理论基础贪心算法的理论基础1.“矩阵胚矩阵胚”理论理论 2.2.“矩阵胚矩阵胚”理论是一种能够确定贪心算法理论是一种能够确定贪心算法何时能够产生最优解的理论，虽然这套理论还何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来很不完善，但在求解最优化问题时发挥着越来越重要的作用。越重要的作用。定义定义矩阵胚是一个序对矩阵胚是一个序对M=S，I，其中，其中S是是一个有序非空集合，一个有序非空集合，I是是S的一个非空子集，成的一个非空子集，成为为S的一个独立子集。的一个独立子集。6常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计如果如果M是一个是一个NM的矩阵的话，即的矩阵的话，即:若若M是无向图是无向图G的矩阵胚的话，则的矩阵胚的话，则S为图的边为图的边集，集，I是所有构成森林的一组边的子集。是所有构成森林的一组边的子集。如果对如果对S的每一个元素的每一个元素X（XS）赋予一个正）赋予一个正的权值的权值W（X），则称矩阵胚），则称矩阵胚M=（S，I）为一）为一个加权矩阵胚。个加权矩阵胚。7常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计适宜于用贪心算法来求解的许多问题都可以归结为适宜于用贪心算法来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，问题，即给定一个加权矩阵胚，M=（S，I），若能），若能找出一个独立且具有最大可能权值的子集找出一个独立且具有最大可能权值的子集A，且，且A不不被被M中比它更大的独立子集所包含，那么中比它更大的独立子集所包含，那么A为最优为最优子集，也是一个最大的独立子集。子集，也是一个最大的独立子集。矩阵胚理论对于我们判断贪心算法是否适用于某一矩阵胚理论对于我们判断贪心算法是否适用于某一复杂问题是十分有效的。复杂问题是十分有效的。8常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计对给定的对给定的n位高精度正整数位高精度正整数,去掉其中去掉其中k(k1(当然小于当然小于n),按上述操作一个一个删除。按上述操作一个一个删除。删除一个达到最大后删除一个达到最大后,再从头即从串首开始再从头即从串首开始,删除第删除第2个个,依此分解为依此分解为k次完成。次完成。若删除不到若删除不到k个后已无左边小于右边的增序个后已无左边小于右边的增序,则停止删除操作则停止删除操作,打印剩下串的左边打印剩下串的左边n-k个数个数字即可字即可(相当于删除了若干个最右边的数字相当于删除了若干个最右边的数字)。下面我们给出采用贪心算法的删数字问题下面我们给出采用贪心算法的删数字问题的的部分部分c语言代码：语言代码：10常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 while(kx&m=0)i=i+1;if(ai-1ai)/*出现递增,删除递增的首数字*/printf(%d,ai-1);for(j=i-1;j=n-x-2;j+)aj=aj+1;x=x+1;/*x统计删除数字的个数*/i=0;/*从头开始查递增区间*/if(i=n-x-1)/*已无递增区间,m=1脱离循环*/m=1;printf(n删除后所得最大数:);for(i=1;i=n-k;i+)/*打印剩下的左边n-k个数字*/printf(%d,ai-1);11常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 5.4背包问题背包问题已知已知n种物品和一个可容纳种物品和一个可容纳c重量的背包，物品重量的背包，物品i的重量的重量为，产生的效益为。装包时物品可拆，即可只装每种物为，产生的效益为。装包时物品可拆，即可只装每种物品的一部分。显然物品品的一部分。显然物品i的一部分放入背包可产生的效的一部分放入背包可产生的效益为，这里。问如何装包，使所得整体效益最大。益为，这里。问如何装包，使所得整体效益最大。(1)算法设计算法设计应用贪心算法求解。每一种物品装包，由可以整个装入，应用贪心算法求解。每一种物品装包，由可以整个装入，也可以只装一部分，也可以不装。也可以只装一部分，也可以不装。约束条件：目标函数：要使整体效益即目标函数最大，约束条件：目标函数：要使整体效益即目标函数最大，按单位重量的效益非增次序一件件物品装包，直至某一按单位重量的效益非增次序一件件物品装包，直至某一件物品装不下时，装这种物品的一部分把包装满。件物品装不下时，装这种物品的一部分把包装满。解背包问题贪心算法的时间复杂度为解背包问题贪心算法的时间复杂度为O(n)。12常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计物品可拆背包问题物品可拆背包问题C程序设计代码如下：程序设计代码如下：for(i=1;i=n-1;i+)/*对对n件物品按单位重量的效益从件物品按单位重量的效益从大到小排序大到小排序*/for(j=i+1;j=n;j+)if(pi/wipj/wj)h=pi;pi=pj;pj=h;h=wi;wi=wj;wj=h;cw=c;s=0;/*cw为背包还可装的重量为背包还可装的重量*/for(i=1;icw)break;xi=1.0;/*若若w(i)cw,装入一部分装入一部分x(i)*/s=s+pi*xi;13常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计printf(装包：装包：);/*输出装包结果输出装包结果*/for(i=1;i=n;i+)if(xi0&xi0)设设v是具有最大的是具有最大的Newi的顶点；的顶点；Cm+=v;for(所有邻接于所有邻接于v的顶点的顶点j)if(!Covj)Covj=true;对于所有邻接于对于所有邻接于j的顶点，使其的顶点，使其Newk减减117常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计if(有些顶点未被覆盖有些顶点未被覆盖)失败失败else找到一个覆盖找到一个覆盖该算法的时间复杂度取决于数据的存储方式，该算法的时间复杂度取决于数据的存储方式，若使用邻接矩阵，则需花若使用邻接矩阵，则需花(n2)的时间来寻找的时间来寻找图中的边，若用邻接链表，则需图中的边，若用邻接链表，则需(n+e)的时的时间。故覆盖算法总的复杂性为间。故覆盖算法总的复杂性为O(n2)或或O(n+e)18常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计图着色问题是其实对应很多应用的例子，假设要在图着色问题是其实对应很多应用的例子，假设要在足够多的会场里安排一批活动，并希望使用尽可能少足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。的会场。设计一个有效的贪心算法进行安排。(这个问这个问题实际上是著名的图着色问题。若将每一个活动作为题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场着有不同颜色的最小着色数，相应于要找的最小会场数。数。)活动安排问题：设有活动安排问题：设有n个活动个活动a1,a2,an,每个活每个活动都要求使用同一资源，而同一时间内只允许一个活动都要求使用同一资源，而同一时间内只允许一个活动使用这一资源。已知活动动使用这一资源。已知活动ai要求使用该资源的起始要求使用该资源的起始时间为时间为si，结束时间为，结束时间为fi，且，且si=fi。要求在。要求在a1,a2,an中选出最大的相容活动子集。中选出最大的相容活动子集。两活动两活动ai,aj(ij)相容是指：相容是指：5.6图的着色问题图的着色问题19常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计例：例：n=4,活动：活动：a1a2a3a4si：4218fi：74510贪心选择策略：贪心选择策略：按结束时间从早到晚安排活动，每按结束时间从早到晚安排活动，每次选择与已选出的活动相容的结束时间尽可能早的次选择与已选出的活动相容的结束时间尽可能早的活动。活动。局部最优性：局部最优性：每次为资源留下尽可能多的时间以容每次为资源留下尽可能多的时间以容纳其它活动。纳其它活动。该算法的时间复杂性：该算法的时间复杂性：(nlogn)。使用贪心算法求解图的着色问题并不总能得到最优使用贪心算法求解图的着色问题并不总能得到最优解解,只保证得到近似最优解。其实，顶点的编号方只保证得到近似最优解。其实，顶点的编号方法决定了这种算法的结果。至少存在一种编号方法法决定了这种算法的结果。至少存在一种编号方法使这个贪心算法能得到最优解。使这个贪心算法能得到最优解。20常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计voidcolor_up(intnodes)/着色函数着色函数inti,j,k=1;int*color;color=(int*)malloc(sizeof(int)*(nodes+1);/初始初始化颜色数化颜色数for(i=1;i=nodes;i+)colori=0;color1=1;dofor(i=2;i0)continue;下面给出图的着色问题的下面给出图的着色问题的c语言程序语言程序:21常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计for(j=1;j0)&(j=nodes)j+;k+;while(j=nodes);for(i=1;i64输出一个解，返回上一步骤输出一个解，返回上一步骤c-(x,y)c计算计算(x,y)的八个方位的子结点，选出那此可行的的八个方位的子结点，选出那此可行的子结点子结点循环遍历所有可行子结点，循环遍历所有可行子结点，c+重复重复25.7遍历问题遍历问题23常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计显然（）是一个递归调用的过程，大致如下：显然（）是一个递归调用的过程，大致如下：voiddfs(intx,inty,intcount)inti,tx,ty;if(countN*N)output_solution();/输入一个解输入一个解return;for(I=0;i8;+i)tx=hni.x;/hn保存八个方位子结点保存八个方位子结点ty=hni.y;stxty=count;dfs(tx,ty,count+1);/递归调用递归调用stxty=0;24常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计这样做是完全可行的，它输入的是全部解，但是马遍历当这样做是完全可行的，它输入的是全部解，但是马遍历当时解是非常之多的，用天文数字形容也不为过，这时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。样一来求解的过程就非常慢，并且出一个解也非常慢。怎么才能快速地得到部分解呢？怎么才能快速地得到部分解呢？其实马踏棋盘的问题很早就有人提出，且早在其实马踏棋盘的问题很早就有人提出，且早在1823年，年，J.C.Warnsdorff就提出了一个有名的算就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选法。在每个结点对其子结点进行选取时，优先选择择出口出口最小的进行搜索，最小的进行搜索，出口出口的意思是的意思是在这些子结点中它们的可行子结点的个数，也就在这些子结点中它们的可行子结点的个数，也就是是孙子孙子结点越少的越优先跳，为什么要这样结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法选取，这是一种局部调整最优的做法.25常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计 其实这种求解就是利用了贪心算法，它对整个求其实这种求解就是利用了贪心算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。其效率可想而知。26常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计下面我们给出马踏棋盘问题的下面我们给出马踏棋盘问题的c代码（代码（）：intways_out(intx,inty)/计算结点出口多少计算结点出口多少inti,count=0,tx,ty;if(x0|y=N|y=N|sxy0)return-1;/-1表示该结点非法或者已经跳过了表示该结点非法或者已经跳过了for(i=0;i8;+i)tx=x+dxi;ty=y+dyi;if(tx0|ty=N|ty=N)continue;if(stxty=0)+count;returncount;27常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计voidsortnode(h_node*hn,intn)/采用简单排序法，采用简单排序法，因为子结点数最多只有因为子结点数最多只有8/按结点出口进行排序按结点出口进行排序inti,j,t;h_nodetemp;for(i=0;in;+i)for(t=i,j=i+1;jn;+j)if(hnj.waysouti)temp=hni;hni=hnt;hnt=temp;28常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计void dfs(int x,int y,int count)/修改后的搜索函数 int i,tx,ty;h_node hn8;if(countN*N)output_solution();return;for(i=0;i8;+i)/求子结点和出口 hni.x=tx=x+dxi;hni.y=ty=y+dyi;hni.waysout=ways_out(tx,ty);sortnode(hn,8);29常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计for(i=0;hni.waysout0;+i);/不考虑无用结点 for(;i8;+i)tx=hni.x;ty=hni.y;stxty=count;dfs(tx,ty,count+1);stxty=0;30常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5.8最小生成树最小生成树 假设已知一无向连通图假设已知一无向连通图G=(V,E)，其加权函数为，其加权函数为w:ER，我们希望找到图，我们希望找到图G的最小生成树。后文所讨论的两种的最小生成树。后文所讨论的两种算法都运用了贪心方法，但在如何运用贪心法上却有所算法都运用了贪心方法，但在如何运用贪心法上却有所不同。不同。下列的算法下列的算法GENERNIC-MIT正是采用了贪心算法，每正是采用了贪心算法，每步形成最小生成树的一条边。算法设置了集合步形成最小生成树的一条边。算法设置了集合A，该集，该集合一直是某最小生成树的子集。在每步决定是否把边合一直是某最小生成树的子集。在每步决定是否把边(u,v)添加到集合添加到集合A中，其添加条件是中，其添加条件是A(u,v)仍然是仍然是最小生成树的子集。我们称这样的边为最小生成树的子集。我们称这样的边为A的安全边，因的安全边，因为可以安全地把它添加到为可以安全地把它添加到A中而不会破坏上述条件。中而不会破坏上述条件。GENERNIC-MIT(G,W)1.A2.whileA没有形成一棵生成树没有形成一棵生成树3do找出找出A的一条安全边的一条安全边(u,v);4.AA(u,v);5.returnA31常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计定理定理5.1设图设图G(V,E)是一无向连通图，且在是一无向连通图，且在E上定义了上定义了相应的实数值加权函数相应的实数值加权函数w，设，设A是是E的一个子集且包含于的一个子集且包含于G的某个最小生成树中，割的某个最小生成树中，割(S,V-S)是是G的不妨害的不妨害A的任的任意割且边意割且边(u,v)是穿过割是穿过割(S,V-S)的一条轻边，则边的一条轻边，则边(u,v)对集合对集合A是安全的。是安全的。下面介绍两个算法：下面介绍两个算法：Kruskal算法和算法和Prim算法算法(1)Kruskal算法算法 Kruskal算法是直接基于上面中给出的一般最小生成树算法是直接基于上面中给出的一般最小生成树算法的基础之上的。该算法找出森林中连结任意两棵树算法的基础之上的。该算法找出森林中连结任意两棵树的所有边中具有最小权值的边的所有边中具有最小权值的边(u,v)作为安全边，并把作为安全边，并把它添加到正在生长的森林中。设它添加到正在生长的森林中。设C1和和C2表示边表示边(u,v)连连结的两棵树。因为结的两棵树。因为(u,v)必是连必是连C1和其他某棵树的一条和其他某棵树的一条轻边，所以由轻边，所以由推推论论2可知可知(u,v)对对C1是安全边。是安全边。Kruskal算法同时也是一种贪心算法，因为算法每一步添加到森算法同时也是一种贪心算法，因为算法每一步添加到森林中的边的权值都尽可能小林中的边的权值都尽可能小 32常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计Kruskal算法的实现类似于算法的实现类似于计算连通支计算连通支的算法。它使用的算法。它使用了了分离集合数据结构分离集合数据结构以保持数个互相分离的元素集合。以保持数个互相分离的元素集合。通过通过FIND-SET(v)来确定两结点来确定两结点u和和v是否属于同一棵树，是否属于同一棵树，通过操作通过操作UNION来完成树与树的联结。来完成树与树的联结。MST-KRUSKAL(G,w)1.A2.for每个结点每个结点vVG3.doMAKE-SET(v)4.根据权根据权w的非递减顺序对的非递减顺序对E的边进行排序的边进行排序5.for每条边每条边(u,v)E，按权的非递减次序，按权的非递减次序6.doifFIND-SET(u)FIND-SET(v)7.thenAA(u,v)8.UNION(u,v)9returnA33常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计Kruskal算法在图算法在图G=(V,E)上的运行时间取决于分离集合这一数据上的运行时间取决于分离集合这一数据结构如何实现。我们采用在结构如何实现。我们采用在分离集合分离集合中描述的中描述的按行结合和通路压按行结合和通路压缩的启发式方法来实现分离集合森林的结构缩的启发式方法来实现分离集合森林的结构，这是由于从渐近意，这是由于从渐近意义上来说，这是目前所知的最快的实现方法。义上来说，这是目前所知的最快的实现方法。(2)Prim算法算法Prim算法的特点是集合算法的特点是集合A中的边总是只形成单棵树。因中的边总是只形成单棵树。因为每次添加到树中的边都是使树的权尽可能小的边，因为每次添加到树中的边都是使树的权尽可能小的边，因此上述策略也是此上述策略也是贪心贪心的。有效实现的。有效实现Prim算法的关键是设算法的关键是设法较容易地选择一条新的边添加到由法较容易地选择一条新的边添加到由A的边所形成的树的边所形成的树中，在下面的伪代码中，算法的输入是连通图中，在下面的伪代码中，算法的输入是连通图G和将生和将生成的最小生成树的根成的最小生成树的根r。在算法执行过程中，不在树中。在算法执行过程中，不在树中的所有结点都驻留于优先级基于的所有结点都驻留于优先级基于key域的队列域的队列Q中。对中。对每个结点每个结点v，keyv是连接是连接v到树中结点的边所具有的最到树中结点的边所具有的最小权值；按常规，若不存在这样的边则小权值；按常规，若不存在这样的边则keyv=。域。域pv说明树中说明树中v的的“父母父母”。34常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计在算法执行中，GENERIC-MST的集合A隐含地满足：A=(v,pv)|vV-r-Q当算法终止时，优先队列Q为空，因此G的最小生成树A满足:A=(v,pv)|v V-r MST-PRIM(G,w,r)1.QVG2.for 每个uQ3.do keyu4.keyr05.prNIL6.while Q7.do uEXTRACT-MIN(Q)8.for 每个vAdju9.do if vQ and w(u,v)keyv10.then pvu11.keyvw(u,v)35常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计Prim算法的性能分析算法的性能分析Prim算法的性能取决于我们如何实现优先队列算法的性能取决于我们如何实现优先队列Q。若。若用二用二叉堆来实现叉堆来实现Q,我们可以使用过程我们可以使用过程BUILD-HEAP来实现第来实现第1-4行的初始化部分，其运行时间为行的初始化部分，其运行时间为O(V)。循环需执行。循环需执行|V|次，次，且由于每次且由于每次EXTRACT-MIN操作需要操作需要O(V)的时间，所以的时间，所以对对EXTRACT-MIN的全部调用所占用的时间为的全部调用所占用的时间为O(VV)。第第8-11行的行的for循环总共要执行循环总共要执行O(E)次，这是因为所有邻次，这是因为所有邻接表的长度和为接表的长度和为2|E|。在。在for循环内部，第循环内部，第9行对队列行对队列Q的的成员条件进行测试可以在常数时间内完成，这是由于我们成员条件进行测试可以在常数时间内完成，这是由于我们可以为每个结点空出可以为每个结点空出1位位(bit)的空间来记录该结点是否在的空间来记录该结点是否在队列队列Q中，并在该结点被移出队列时随时对该位进行更新。中，并在该结点被移出队列时随时对该位进行更新。第第11行的赋值语句隐含一个对堆进行的行的赋值语句隐含一个对堆进行的DECREASE-KEY操作，该操作在堆上可用操作，该操作在堆上可用0(V)的时间完成。因此，的时间完成。因此，Prim算法的整个运行时间为算法的整个运行时间为O(VV+EV)=O(EV)，从渐近，从渐近意义上来说，它和实现意义上来说，它和实现Kruskal算法的运行时间相同。算法的运行时间相同。36常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计通过使用通过使用Fibonacci堆，堆，Prim算法的渐近意义算法的渐近意义上的运行时间可得到改进。在上的运行时间可得到改进。在Fibonacci堆堆中中我们己经说明，如果我们己经说明，如果|V|个元素被组织成个元素被组织成Fibonacci堆，可以在堆，可以在O(V)的平摊时间内完的平摊时间内完成成EXTRACT-MIN操作，在操作，在O(1)的平摊时间里的平摊时间里完成完成DECREASE-KEY操作（为实现第操作（为实现第11行的行的代码），因此，若我们用代码），因此，若我们用Fibonacci堆来实现堆来实现优先队列优先队列Q，Prim算法的运行时间可以改进为算法的运行时间可以改进为O(E+VV)。37常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计5.9哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在效的编码方法。其压缩率通常在20%90%之间。之间。哈夫曼编码算法用字符在文件中出现的频率表来哈夫曼编码算法用字符在文件中出现的频率表来建立一个用建立一个用0，1串表示各字符的最优表示方式。串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。的字符以较长的编码，可以大大缩短总码长。例如一个包含例如一个包含100,000个字符的文件，各字符出现个字符的文件，各字符出现频率不同，如下表所示。定长变码需要频率不同，如下表所示。定长变码需要300,000位，位，而按表中变长编码方案，文件的总码长为：而按表中变长编码方案，文件的总码长为：（451+133+123+163+94+54）1000=224,000。比用定长码方案总码长较少约比用定长码方案总码长较少约45%。38常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计对每一个字符规定一个对每一个字符规定一个0,1串作为其代码，并要求任一字串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前符的代码都不是其它字符代码的前缀。这种编码称为前缀码。缀码。编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。表示最优前缀码的二叉树总是一棵完全二叉树，即树中表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有任一结点都有2个儿子结点。个儿子结点。平均码长定义为：平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字使平均码长达到最小的前缀码编码方案称为给定编码字符集符集C的最优前缀码。的最优前缀码。哈夫曼提出构造最优前缀码的贪心算法，由此产生的编哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。码方案称为哈夫曼编码。39常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以算法以|C|个叶结点开始，执行个叶结点开始，执行|C|1次的次的“合并合并”运算后产生最运算后产生最终所要求的树终所要求的树T。HUFFMAN(c)1n|c|2QC3foriton-14doallocateanewcodez5leftzxEXTRACT-MIN(Q)6rightzyEXTRACT-MIN(Q)7fz=fx+fy8INSERT(Q,z)9returnEXTRACT-MIN(Q)时间分析，我们假设时间分析，我们假设Q是作为最小二叉堆实现的。对包含个字符是作为最小二叉堆实现的。对包含个字符的集合的集合C，第二行中对，第二行中对Q的初始化可用在前面建堆章节中介绍所的初始化可用在前面建堆章节中介绍所用的时间用的时间O(n)内完成。第内完成。第3-8行中的行中的for循环执行了循环执行了n-1次，又因次，又因每一次堆操作需要每一次堆操作需要O(lgn）时间，故整个循环需要）时间，故整个循环需要O(nlgn）时间。）时间。这样，作用于这样，作用于n个字符集合的个字符集合的HUFFMAN的总的运行时间为的总的运行时间为O(nlgn）。）。40常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计习题习题51.一个数列由一个数列由n个正整数组成。对该数列进行一次操作：个正整数组成。对该数列进行一次操作：去除其中两项去除其中两项a，b，添加一项，添加一项a*b+1。经。经n-1次操作后次操作后该数列剩一个数该数列剩一个数a，试求，试求a的最大值。的最大值。2.随机产生一个随机产生一个n位高精度正整数位高精度正整数,去掉其中去掉其中k(kn)个个数字后按原左右次序将组成一个新的正整数。对给定的数字后按原左右次序将组成一个新的正整数。对给定的n,k寻找一种方案寻找一种方案,使得剩下的数字组成的新数最小。使得剩下的数字组成的新数最小。3.利用贪心利用贪心kruscal算法和算法和prim算法求出下图的最小生算法求出下图的最小生成树（要求画出生成树，过程可以省略）。成树（要求画出生成树，过程可以省略）。41常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计4.一个有向图一个有向图G，它的每条边都有一个非负，它的每条边都有一个非负的权值的权值ci,j，“路径长度路径长度”就是所经过的就是所经过的所有边的权值之和。对于源点需要找出从所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径，源点出发到达其他所有结点的最短路径，试用贪心算法解此问题。试用贪心算法解此问题。E1=7ABEE4=1E2=8E3=2DGCFGE12=6E5=4E10=3E11=4E14=4E8=2E6=2E7=3E13=5E15=1E16=3E17=6E9=742常用算法与程序设计常用算法与程序设计常用算法与程序设计常用算法与程序设计