第四章贪心算法.pptx

第四章.贪心算法贪心算法(Greed method)例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。目的：用以求解最优化问题 将问题的求解过程看作是一系列选择将问题的求解过程看作是一系列选择,每次选择一个每次选择一个输入输入,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择(局部最优解局部最优解).).每作一次选择后每作一次选择后,所求问题会简化为一个规模更小的子所求问题会简化为一个规模更小的子问题问题.从而通过每一步的最优解逐步达到整体的最优解。从而通过每一步的最优解逐步达到整体的最优解。4.1 基本思想 算法优点算法优点求解速度快,时间复杂性有较低的阶.算法缺点算法缺点需证明是最优解.常见应用背包问题,最小生成树,最短路径,作业调度等等适用问题适用问题 具备具备贪心选择贪心选择和和最优子结构最优子结构性质的最优化问题性质的最优化问题贪心选择贪心选择性质：性质：整体的最优解可通过一系列局部最优解达到，即整体的最优解可通过一系列局部最优解达到，即贪心选择到达。贪心选择到达。贪心算法通常以自顶向下的方式进行，以迭代的方式作出相贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模更小的问题更小的问题 对于一个具体问题，要确定它是否具有贪心选择的性质，我对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从可以首先证明问题的一个整体最优解，是从 贪心选择开始的，而贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体问题的一个整体 最优解。最优解。最优子结构性质最优子结构性质：当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。称此问题具有最优子结构性质。A(1)A(2)A(n-1)A(n)某一问题的n个输入B1(1)B1(2)B1(m)该问题的一种解（可行解）是A的一个子集满足一定的条件约束条件Bk(1)Bk(2)Bk(m)目标函数取极值最优解算法设计与分析算法设计与分析 贪心算法贪心算法4.2.活动安排问题算法设计与分析算法设计与分析 贪心算法贪心算法活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。问题陈述问题陈述 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间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,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;算法设计与分析算法设计与分析 贪心算法贪心算法各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时间的非减序排列序排列 算法算法greedySelector greedySelector 的计算过程的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。由于输入的活动以其完成时间的非减序非减序排列，所以算法greedySelector每次总是选择具有最早完成时间具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。T(n)=O(nlogn)(未排序时)算法分析 T(n)=O(n)(排序时)算法证明 算法达到最优解.问题描述问题描述 输入输入:(x1,x2,.xn),xi=0,货箱货箱i不装船不装船;xi=1,货箱货箱i装船装船 可行解可行解:满足约束条件满足约束条件 c 的输入的输入 优化函数优化函数:最优解最优解:使优化函数达到最大值的一种输入使优化函数达到最大值的一种输入.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个单位且已被装载,剩下的装载能力为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,背包的容量为背包的容量为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,2/15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(1)1、用用贪贪心心策策略略求求解解背背包包问问题题时时，首首先先要要选选出出最最优优的的度度量量标标准准。可可以以选选取取目目标标函函数数为为量量度度标标准准，每每装装入入一一件件物物品品就就使使背背包包获获得得最最大大可可能能的的效效益益值值增增量量。在在这这种种量量度度标标准准下下的的贪贪心心方方法法就就是是按按效效益益值值的的非非增增次次序序将将物物品品一一件件件放到背包中件放到背包中。如如上上面面的的实实例例所所示示，可可将将物物品品按按效效益益量量非非增增次次序序排排序序：(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，显显然然是是一一个个次次优优解，原因是背包容量消耗过快。解，原因是背包容量消耗过快。算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(2)2、若若以以容容量量作作为为量量度度，可可让让背背包包容容量量尽尽可可能能慢慢地地被被消消耗耗。这这就就要要求求按按物物品品重重量量的的非非降降次次序序来来把把物物品品放放入入背包背包，即，即(w3,w2,w1)=(10,15,18)。先装入物品先装入物品3,x3=1,p3x3=15，再装入重量为，再装入重量为10的的物品物品2，vixi=15+24*10/15=31。由由刚刚才才的的方方法法可可得得这这种种情情况况下下的的总总效效益益值值为为31，仍仍是是一一个个次次优优解解，原原因因是是容容量量在在漫漫漫漫消消耗耗的的过过程程中中，效效益益值却没有迅速的增加。值却没有迅速的增加。算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(3)3、采采用用在在效效益益值值的的增增长长速速率率和和容容量量的的消消耗耗速速率率之之间间取取得得平平衡衡的的量量度度标标准准。即即每每一一次次装装入入的的物物品品应应使使它它占占用用的的每每一一单单位位容容量量获获得得当当前前最最大大的的单单位位效效益益。这这就就需需使使物物品品的的装装入入次次序按序按vi/wi比值的非增次序来考虑比值的非增次序来考虑。这种策略下的量度是已装入物品的累计效益值与所用这种策略下的量度是已装入物品的累计效益值与所用容量之比。容量之比。(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(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 贪心算法贪心算法算法分析算法分析:排序为主要算法时间,所以 T(n)=O(nlogn)背包问题中的物体不能分拆背包问题中的物体不能分拆,只能整个装入称为只能整个装入称为0-10-1背背包问题包问题.算法证明算法证明:该算法能得到在最优解 用贪心算法能得到用贪心算法能得到0-10-1背包的最优解吗背包的最优解吗?首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值V Vi i/W/Wi i，然后，依贪，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过总重量未超过C C，则选择单位重量价值次高的物品并尽可，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包能多地装入背包。依此策略一直地进行下去，直到背包装满为止。装满为止。具体算法可描述如下页：具体算法可描述如下页：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美美分分的的糖糖，并并将将1 1美美元元的的钱钱交交给给售售货货员员。售售货货员员希希望望用用数数目目最最少少的的硬硬币币找找给给小小孩孩。假假设设提提供供了了数数目目不不限限的的面面值值为为2525美美分分、1010美美分分、5 5美美分分、及及1 1美美分分的的硬硬币币。使使用用贪贪心心算算法法求求解解最最优优结结果果。并并证证明明找找零零钱钱问问题题的的贪贪心心算算法法总总能能产产生具有最少硬币数的零钱。生具有最少硬币数的零钱。算法设计与分析算法设计与分析 贪心算法贪心算法问题问题:通讯过程中需将传输的信息转换为二进制码通讯过程中需将传输的信息转换为二进制码.由于英文由于英文字母使用频率不同字母使用频率不同,若频率高的字母对应短的编码若频率高的字母对应短的编码,频率低的频率低的字母对应长的编码字母对应长的编码,传输的数据总量就会降低传输的数据总量就会降低.要求找到一个要求找到一个编码方案编码方案,使传输的数据量最少使传输的数据量最少.见见P109-P109-表表4-14-1 算法设计与分析算法设计与分析 贪心算法贪心算法1、前缀码、前缀码 为能正确译码为能正确译码,编码需采用编码需采用前缀码前缀码,对每一个字符规定一个对每一个字符规定一个0,1串作为其代码，并要求任一字符的串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。代码都不是其它字符代码的前缀。这种编码称为前缀码。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有结点都有2个儿子结点。个儿子结点。平均码长定义为：平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。的最优前缀码。4.4 哈夫曼编码算法思路：算法思路：1)以以n个字母为结点构成个字母为结点构成n棵仅含一个点的二叉树集合棵仅含一个点的二叉树集合,字母的频率字母的频率 即为结点的权即为结点的权2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树每次从二叉树集合中找出两个权最小者合并为一棵二叉树:增加增加一个根结点将这两棵树作为左右子树一个根结点将这两棵树作为左右子树.新树的权为两棵子树的权之新树的权为两棵子树的权之和和.3)反复进行步骤反复进行步骤2)直到只剩一棵树为止直到只剩一棵树为止.2、构造哈夫曼编码、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码 template BinaryTreeHuffmanTree(T f,int n)/根据权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 Q用在贪心选择贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间计算时间为O(nlogn)。最优子结构:设T为带权w1w2.wt的最优树,若将以带权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶,得到一棵新树T,则T也是最优树。贪心选择性:设T为带权w1w2.wt的最优树,a).带权w1和w2的树叶vw1和vw2是兄弟.b).以vw1和vw2为儿子的分枝点,其通路长度最长.算法证明算法证明算法分析算法分析HuffmanTree初始化优先队列Q需要O(n)DeleteMin和Insert需O(logn).n-1次的合并总共需要O(nlogn)所以n个字符的哈夫曼算法的计算时间为O(nlogn)算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码4.5 单源最短路径问题:给定带权有向图G=(V,E),其中每条边的权是一个非负实数.要计算从V的一点v0(源)到所有其他各顶点的最短路长度.路长指路上各边权之和。算法设计与分析算法设计与分析 贪心算法贪心算法算法思路(Dijkstra):设最短路长已知的终点集合为S,初始时v0S,其最短路长为0,然后用贪心选择贪心选择逐步扩充S:每次在V-S中,选择路径长路径长度值最小的一条最短路径度值最小的一条最短路径的终点终点x加入S.例例 题题构造路长最短的最短路径构造路长最短的最短路径:设已构造i条最短路径,则下一个加入S的终点u必是V-S中具有最小路径长度的终点,其长度或者是弧(v0,u),或者是中间只经过S中的顶点而最后到达顶点u的路径.例例 题题已已知知一一个个n 结结点点的的有有向向图图G=(V,E)和和边边的的权权函函数数c(e)，求求由由G中中某某指指定定结结点点v0到到其其他他各各个个结结点点的的最短路径。最短路径。v0v2v1v3v4v5204550101515201035303路径长度(1)v0v210(2)v0v2v325(3)v0v2v3v145(4)v0v445算法设计与分析算法设计与分析 贪心算法贪心算法产生最短路径的贪心方法产生最短路径的贪心方法逐条构造这些最短路径，逐条构造这些最短路径，使用迄今已生成的所有路径长度使用迄今已生成的所有路径长度之和作为一种量度标准之和作为一种量度标准。为了使这一量度达到最小，其单独的每一条路径都必须具为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。有最小长度。使用这标准时，假定已构造了使用这标准时，假定已构造了i条最短路径，则下面要构造条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。的路径应该是下一条最短的最小长度路径。生成从生成从v0到所有其它结点的最短路径的贪心方法就是到所有其它结点的最短路径的贪心方法就是按照按照路径长度的非降次序生成这些路径路径长度的非降次序生成这些路径。算法设计与分析算法设计与分析 贪心算法贪心算法产生最短路径的贪心方法产生最短路径的贪心方法设设S表示对其已经生成了最短路径的那些结点表示对其已经生成了最短路径的那些结点(包包括括v0)的集合。的集合。扩张扩张S的过程：对于不在的过程：对于不在S中的结点中的结点w，设，设DIST(w)是从是从v0开始只经过开始只经过S中的结点而在结点中的结点而在结点w结束的那条最短路径的长度，则有结束的那条最短路径的长度，则有：如果下一条最短路径是到结点如果下一条最短路径是到结点u，则这条路径是从，则这条路径是从v0处处开始而在开始而在u处终止，并且只通过那些在处终止，并且只通过那些在S中的结点。中的结点。所生成的下一条路径的终点所生成的下一条路径的终点u必定是所有不在必定是所有不在S内的结内的结点中具有最小距离点中具有最小距离DIST(u)的结点。的结点。算法设计与分析算法设计与分析 贪心算法贪心算法产生最短路径的贪心方法产生最短路径的贪心方法选出了结点选出了结点u并生成了从并生成了从v0到到u的最短路径之后，结点的最短路径之后，结点u就就成为成为S中的一个成员。中的一个成员。此时，那些从此时，那些从v0开始，只通过开始，只通过S中的结点并且在中的结点并且在S外的结点外的结点w处结束的最短路径可能会减小。处结束的最短路径可能会减小。如果长度改变了，则它必定是由一条从如果长度改变了，则它必定是由一条从v0开始，经过开始，经过u然然后到后到w的更短路径所造成的。的更短路径所造成的。其中从其中从v0到到u的路径是一条最短路径，从的路径是一条最短路径，从u到到w的路径是边的路径是边，于是这条路径的长度就是：，于是这条路径的长度就是：DIST(u)+c(u,w)算法设计与分析算法设计与分析 贪心算法贪心算法算法设计与分析算法设计与分析 贪心算法贪心算法 算法描述算法描述：(1)用带权的邻接矩阵c来表示带权有向图,cij表示弧 上的权值.若 V,则置cij为 设S为已知最短路径的终点的集合,它的初始状态为空集.从源点v到图上其余各点vi的当前最短路径长度的初值为：disti=cvi，viV (2)选择vj,使得distj=Mindisti|viV-S vj就是长度最短的最短路径的终点。令S=SUj/更新S (3)修改从v到集合V-S上任一顶点vk的当前最短路径长度:如果 distj+cjk 贪心算法贪心算法 单源最短路径单源最短路径例例 题题1)v1 v2:102)v1 v3:503)v1 v4:304)v1 v5:60算法设计与分析算法设计与分析 贪心算法贪心算法 voidDijkstra(int n,int v,Type dist,int prev,Type*c)bool smaxint；for(int i=1;i=n;i+)disti=cvi；si=false；if(disti=maxint)previ=0；else previ=v;distv=0；sv=true；for(int i=1;in；i+)int temp=maxint；int u=v；for(int j=1；j=n；j+)if(!sj)&(distjtemp)u=j；temp=distj；su=true；for(int j=1；j=n;j+)；if(!sj)(cujmaxint)Type newdist=distu)+cuj;if(newdist 贪心算法贪心算法 单源最短路径单源最短路径例例 题题1)v1 v2:102)v1 v3:503)v1 v4:304)v1 v5:60算法实例算法实例求下图中求下图中v1到其余各结点的最短路径到其余各结点的最短路径v1v4v2v3v6v7v52030504055257050251070500 20 50 30 0 25 70 0 40 25 50 0 55 0 10 70 0 50 0算法设计与分析算法设计与分析 贪心算法贪心算法算法实例算法实例迭代迭代选取选取结点结点SDIST(1)(2)(3)(4)(5)(6)(7)置初值置初值-10205030121,2020453090231,2,402045308590341,2,4,302045307090451,2,4,3,502045307080140561,2,4,3,5,602045307080130SHORTEST-PATHS执行踪迹执行踪迹算法设计与分析算法设计与分析 贪心算法贪心算法算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树问题陈述问题陈述:设G(V,E)是一个无向连通带权图。E中每条边(v,w)的权为cvw,若G的一个子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树.抽象描述:输入:任一连通生成子图(该子图的边集合)可行解:图的生成树,优化函数:生成树的各边权值之和 最优解:使优化函数达到最小的生成树.4.6 最小生成树最小生成树算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树应用领域与图模型算法思路算法思路:首先置S=1,T=.若SV,就作如下的贪心选择：选取满足条件iS,jV-S,且cij最小的边(i,j),将顶点j添加到S中边(i,j)添加到T中.这个过程一直进行到S=V时为止.T中的所有边构成G的一棵最小生成树。void Prim(int n,Type *c)T=;S=1;while(S!=V)(i,j)=i S且 jV-S的最小权边;T=TU(i,j);S=S Uj;算法描述算法描述 Prim算法算法设G=(V,E)是一个连通带权图,y=l,2,n。例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树问题：如何选取满足条件iS,jV-S,且cij最小的边(i,j),成了算法难点问题。解决方法：设置两个数组closest和lowcost。对于每个j V-S，closestj是j在S中的邻接顶点，它与j在S中的其他邻接顶点k相比较有cjclosetj cjk。lowcostj的值就是cjclosestj图 Prim算法的执行过程 注：灰色部分表示集合S 每个结点的上的数字表示S中的结点到该结点的最小消耗，即lowcost 用图示的边的连接表示closest图 Prim算法的执行过程 图 Prim算法的执行过程 图 Prim算法的执行过程 图 4-16Prim算法的执行过程 图 4-16Prim算法的执行过程 template void Prim(int n,Type*c)Type lowcostmaxint;int closest maxim;bool smaxint;s1=true;for(int i=2;i=n;i+)lowcosti=cli;closest i=1;si=false;for(int i=1;i n;i+)Type min=inf;int j=1;for(int k=2;k=n;k+)if(lowcostk min)&(!sk)min=lowcost k;j=k;cout j closestj end;sj=true;for(intk=2;k=n;k+)if(cjk 贪心算法贪心算法 最小生成树最小生成树算法思路算法思路:首先将G的n个顶点看成n个孤立的连通分支,将所有的边按权从小到大排序,然后从第一条边开始,依边权递增的顺序查看每一条边，并按下述方法连接两个通分支：当查看到第k条边(v,w)时,如果端点u和w分别是当前两个不同的连通分支T1,T2中的顶点时,就用边(u,w)将TI和T2连接成一个连通分支，然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中，就直接再查看第k十1条边。直到只剩下一个连通分支为止。此时，这个连通分枝就是G的一颗最小生成树 Kruskal算法算法 G=(V,E),V=贪心算法贪心算法 最小生成树最小生成树e1(1)e2(6)e8(9)e6(2)e9(4)e5(5)e4(7)e10(8)e11(3)e7(10)e3(11)1)以以G 中全部点为点作图中全部点为点作图2)按权的大小次序依次添加按权的大小次序依次添加 各边各边,若出若出 现回路则忽略此边现回路则忽略此边.3)加入加入n-1条边后就得到最小条边后就得到最小 生成树生成树.12537求最小生成树求最小生成树(Kruscal)最优解最优解:(e1,e6,e11,e5,e4)例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树优先队列定义：优先队列定义：优先队列中元素出队列的顺序由元素的优先级决中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。而不是元素进入队列的次序。可以利用堆数据结构来高效地实现优先队列。可以利用堆数据结构来高效地实现优先队列。实现：优先队列（实现：优先队列（priority queuepriority queue）是）是0 0个或多个元素的个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行集合，每个元素都有一个优先权或值，对优先队列执行的操作有的操作有1)1)查找；查找；2)2)插入一个新元素；插入一个新元素；3)3)删除。在最删除。在最小优先队列（小优先队列（min priority q u e u emin priority q u e u e）中，查找操作）中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列（对于最大优先队列（max priority queuemax priority queue），查找操作），查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。用来搜索优先权最大的元素，删除操作用来删除该元素。处理：优先权队列中的元素可以有相同的优先权，查找处理：优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。与删除操作可根据任意优先权进行。I n i t i a l i z eI n i t i a l i z e函数：使用数组函数：使用数组a a中的元素对最大堆中的元素对最大堆进行初始化。进行初始化。DeleteMin(x)DeleteMin(x)：从队列中删除具有最小优先权的元素，：从队列中删除具有最小优先权的元素，并将该元素返回至并将该元素返回至x xI n s e rt(x)I n s e rt(x)：将：将x x 插入队列插入队列并查集并查集 在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集 (给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。)并查集的数学模型并查集的数学模型 并查集的数学模型是若干不相交的动态集合的集合SA,B,C,.，它支持以下的运算：(1)INITIAL(A,x)：构造一个取名为A的集合，它只包含一个元素x；(2)MERGE(A,B)：将集合A和B合并，其结果取名为A或B；(3)FIND(x)：找出元素x的所在集合，并返回该集合的名字。template bool Kruskal(int n,int e,EdgeNode E,EdgeNode t )MinHeap EdgeNode H(1);H.Initialize(E,e,e);UnionFind U(n);iht k=0;while(e&k n-1)EdgeNode x;x.u=2;x.v=1;x.weight=5;H.DeleteMin(x);e-;int a=U.Find(x.u);int b=U.Eind(x.v);if(a!=b)tk+=x;U.Union(a,b);H.Deactivate()renturn(k=n-1)Kruska算法算法算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树A=（选出的边）E=(h,g,1),(g,f,2),(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)（原图中的边）初始状态初始状态森林由森林由9棵树组成棵树组成A=(h,g)E=(g,f,2),(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)接受边接受边(h,g)UNION(g,h)森林由森林由8棵树组成棵树组成（a）（b）图 Kruskal算法的执行过程 E=(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)（c）E=(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)（d）接受边接受边(c,i)UNION(c,i)森林由森林由6棵树组成棵树组成接受边接受边(g,f)UNION(g,f)森林由森林由7棵树组成棵树组成图 Kruskal算法的执行过程 E=(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)接受边接受边(a,b)UNION(a,b)森林由森林由5棵树组成棵树组成图 Kruskal算法的执行过程 E=(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)E=(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)接受边接受边(c,f)UNION(c,f)森林由森林由4棵树组成棵树组成 选取边（选取边（g,I,6）但因为）但因为g和和i在一个连通子图中，即在一个连通子图中，即U.Find(g)和和U.Find(i)相同，所相同，所以拒绝边以拒绝边(g,i)接受边接受边(c,d)UNION(c,d)森林由森林由