贪心算法-课件.ppt

1、 将问题的求解过程看作是一系列选择将问题的求解过程看作是一系列选择,每次选择一个每次选择一个输入输入,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择(局部最优解局部最优解).).每作一次选择后每作一次选择后,所求问题会简化为一个规模更小的子所求问题会简化为一个规模更小的子问题问题.从而通过每一步的最优解逐步达到整体的最优解。从而通过每一步的最优解逐步达到整体的最优解。4.1 基本思想 算法优点算法优点求解速度快,时间复杂性有较低的阶.算法缺点算法缺点需证明是最优解.常见应用背包问题,最小生成树,最短路径,作业调度等等适用问题适用问题 具备具备贪心选择贪心选择和和最优子结构最优

2、子结构性质的最优化问题性质的最优化问题贪心选择贪心选择性质：性质：整体的最优解可通过一系列局部最优解达到，即整体的最优解可通过一系列局部最优解达到，即贪心选择到达。贪心选择到达。贪心算法通常以自顶向下的方式进行，以迭代的方式作出相贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模更小的问题更小的问题 对于一个具体问题，要确定它是否具有贪心选择的性质，我对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常们必须证明每一步所作的贪

3、心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从可以首先证明问题的一个整体最优解，是从 贪心选择开始的，而贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体问题的一个整体 最优解。最优解。最优子结构性质最优子结构性质：当一个问题的最优解包含其子问题的最优解时当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。，称此问题具有最优子结构性质。A(1)A(2

4、)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，其中每个活动都要求使用同一资源，如

5、演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动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,

6、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;算

7、法设计与分析算法设计与分析 贪心算法贪心算法各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时间的非减序排列序排列 算法算法greedySelector greedySelector 的计算过程的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。由于输入的活动以其完成时间的非减序非减序排列，所以算法greedySelector每次总是选择具有最早完成时间具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下

8、尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。T(n)=O(nlogn)(未排序时)算法分析 T(n)=O(n)(排序时)算法证明 算法达到最优解.问题描述问题描述 输入输入:(x1,x2,.xn),xi=0,货箱货箱i不装船不装船;xi=1,货箱货箱i装船装船 可行解可行解:满足约束条件满足约

9、束条件 c 的输入的输入 优化函数优化函数:最优解最优解:使优化函数达到最大值的一种输入使优化函数达到最大值的一种输入.iniixw1niix14.3 最优装载算法设计与分析算法设计与分析 贪心算法贪心算法算法思路算法思路 将装船过程划为多步选择，每步装一个货箱，每次从将装船过程划为多步选择，每步装一个货箱，每次从剩下的货箱中选择重量最轻的货箱剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。船或船上不能再容纳其他任何一个货箱。例设n=8，w1，w8=100,200,50,90,150,50,20,80，c=400。所考察货

10、箱的次序为: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 0,1 i i n n4-4 背包问题(Knapsack Prob

11、lem)cxwniii1niiixv1max 问题描述问题描述 设有设有n个物体和一个背包个物体和一个背包,物体物体i的重量为的重量为wi,价值价值为为vi,背包的容量为背包的容量为C.若将物体若将物体i的的xi部分部分(1 i n,0 xi 1)装装入背包入背包,则具有价值为则具有价值为vi xi.目标是找到一个方案目标是找到一个方案,使放入背使放入背包的物体总价值最高包的物体总价值最高.约约束束条条件件优化函优化函数数算法设计与分析算法设计与分析 贪心算法贪心算法背包问题实例背包问题实例 考虑下列情况的背包问题考虑下列情况的背包问题 n=3,M=20,(v1,v2,v3)=(25,24,1

12、5),(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、用贪心策略求解背包问题时，首先要选出最优、用贪心策略求解背包问题时，首先要选出最优的度量标准的度量标准。可以。可以选取目标函数为量度标准选取目标函数为量度标准，每装入一，每装入一件物品就使背包获得最大可能的效益值增量。在这种量件物品就使背包获得

13、最大可能的效益值增量。在这种量度标准下的贪心方法就是度标准下的贪心方法就是按效益值的非增次序将物品一按效益值的非增次序将物品一件件放到背包中件件放到背包中。如上面的实例所示，可如上面的实例所示，可将物品按效益量非增次序排将物品按效益量非增次序排序：序：(v1,v2,v3)=(25,24,15)。先装入物品。先装入物品1重量为重量为18，即，即x1=1；然后再装物品；然后再装物品2，由于约束条为，由于约束条为wi xi M=20，所以物品所以物品2只能装入重量为只能装入重量为2的一小部分，即的一小部分，即x2=2/15。按上述的数据选择策略，按上述的数据选择策略，装入顺序是按照物品的效装入顺序是

14、按照物品的效益值从大到小的输入益值从大到小的输入，由刚才的方法可得这种情况下的，由刚才的方法可得这种情况下的总效益值为总效益值为v vixi=25+24*2/15=28.2，显然是一个次优，显然是一个次优解，原因是背包容量消耗过快。解，原因是背包容量消耗过快。算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(2)2、若以容量作为量度、若以容量作为量度，可让背包容量尽可能慢地，可让背包容量尽可能慢地被消耗。这就要求被消耗。这就要求按物品重量的非降次序来把物品放入按物品重量的非降次序来把物品放入背包背包，即，即(w3,w2,w1)=(10,15,18)。先

15、装入物品先装入物品3,x3=1,p3x3=15，再装入重量为，再装入重量为10的的物品物品2，vixi=15+24*10/15=31。由刚才的方法可得这种情况下的总效益值为由刚才的方法可得这种情况下的总效益值为31，仍，仍是一个次优解，原因是容量在漫漫消耗的过程中，效益是一个次优解，原因是容量在漫漫消耗的过程中，效益值却没有迅速的增加。值却没有迅速的增加。算法设计与分析算法设计与分析 贪心算法贪心算法贪心方法的数据选择策略贪心方法的数据选择策略(3)3、采用在效益值的增长速率和容量的消耗速率之间取采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准得平衡的量度标准。即每一次装入的物品应

16、使它占用的每一。即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需单位容量获得当前最大的单位效益。这就需使物品的装入次使物品的装入次序按序按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。此结果为最优解。此结果为最优解。算法设计与分析算法设计与分析 贪心

17、算法贪心算法算法思路1).将各物体按单位价值由高到低排序.2).取价值最高者放入背包.3).计算背包剩余空间.4).在剩余物体中取价值最高者放入背包.若背包剩余容量=0或物体全部装入背包为止 例例 n=3,c=20(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)niiixw1niiixv1x1,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,

18、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，然后，依贪，

19、然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过总重量未超过C C，则选择单位重量价值次高的物品并尽可，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包能多地装入背包。依此策略一直地进行下去，直到背包装满为止。装满为止。具体算法可描述如下页：具体算法可描述如下页：void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int

20、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美分的硬币。使用贪心美分的硬币。使用贪心算法求解最优结果。并证明找零钱问题的贪心算法算法求解最优结果。并证明找零钱

21、问题的贪心算法总能产生具有最少硬币数的零钱。总能产生具有最少硬币数的零钱。算法设计与分析算法设计与分析 贪心算法贪心算法问题问题:通讯过程中需将传输的信息转换为二进制码通讯过程中需将传输的信息转换为二进制码.由于由于英文英文字母使用频率不同字母使用频率不同,若频率高的字母对应短的编码若频率高的字母对应短的编码,频率低的频率低的字母对应长的编码字母对应长的编码,传输的数据总量就会降低传输的数据总量就会降低.要求找到一个要求找到一个编码方案编码方案,使传输的数据量最少使传输的数据量最少.见见P109-P109-表表4-14-1 算法设计与分析算法设计与分析 贪心算法贪心算法1、前缀码、前缀码 为能

22、正确译码为能正确译码,编码需采用编码需采用前缀码前缀码,对每一个字符规定一个对每一个字符规定一个0,1串作为其代码，并要求任一字符的串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。代码都不是其它字符代码的前缀。这种编码称为前缀码。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有结点都有2个儿子结点。个儿子结点。平均码长定义为：平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。的最优前缀码。4.4 哈夫曼编码)()(

23、)(cdcfTBTCc算法思路：算法思路：1)以以n个字母为结点构成个字母为结点构成n棵仅含一个点的二叉树集合棵仅含一个点的二叉树集合,字母的频率字母的频率 即为结点的权即为结点的权2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树每次从二叉树集合中找出两个权最小者合并为一棵二叉树:增加增加一个根结点将这两棵树作为左右子树一个根结点将这两棵树作为左右子树.新树的权为两棵子树的权之新树的权为两棵子树的权之和和.3)反复进行步骤反复进行步骤2)直到只剩一棵树为止直到只剩一棵树为止.2、构造哈夫曼编码、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码哈夫曼编码。

24、哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树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:/数组变成个最小堆 MinHeapHuf

25、fmanQ(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(

26、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

27、需O(logn).n-1次的合并总共需要O(nlogn)所以n个字符的哈夫曼算法的计算时间为O(nlogn)算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码4.5 单源最短路径问题:给定带权有向图G=(V,E),其中每条边的权是一个非负实数.要计算从V的一点v0(源)到所有其他各顶点的最短路长度.路长指路上各边权之和。算法设计与分析算法设计与分析 贪心算法贪心算法算法思路(Dijkstra):设最短路长已知的终点集合为S,初始时v0S,其最短路长为0,然后用贪心选择贪心选择逐步扩充S:每次在V-S中,选择路径长路径长度值最小的一条最短路径度值最小的一条最短路径的终点终点x加

28、入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算法设计与分析算法设计与分析

29、 贪心算法贪心算法产生最短路径的贪心方法产生最短路径的贪心方法 逐条构造这些最短路径，逐条构造这些最短路径，使用迄今已生成的所有路径长度使用迄今已生成的所有路径长度之和作为一种量度标准之和作为一种量度标准。为了使这一量度达到最小，其单独的每一条路径都必须具为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。有最小长度。使用这标准时，假定已构造了使用这标准时，假定已构造了i条最短路径，则下面要构条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。造的路径应该是下一条最短的最小长度路径。生成从生成从v0到所有其它结点的最短路径的贪心方法就是到所有其它结点的最短路径的贪心方法就是

30、按照按照路径长度的非降次序生成这些路径路径长度的非降次序生成这些路径。算法设计与分析算法设计与分析 贪心算法贪心算法产生最短路径的贪心方法产生最短路径的贪心方法 设设S表示对其已经生成了最短路径的那些结点表示对其已经生成了最短路径的那些结点(包包括括v0)的集合。的集合。扩张扩张S的过程：对于不在的过程：对于不在S中的结点中的结点w，设，设DIST(w)是从是从v0开始只经过开始只经过S中的结点而在结点中的结点而在结点w结束的那结束的那条最短路径的长度，则有条最短路径的长度，则有：如果下一条最短路径是到结点如果下一条最短路径是到结点u，则这条路径是从，则这条路径是从v0处处开始而在开始而在u处

31、终止，并且只通过那些在处终止，并且只通过那些在S中的结点。中的结点。所生成的下一条路径的终点所生成的下一条路径的终点u必定是所有不在必定是所有不在S内的结内的结点中具有最小距离点中具有最小距离DIST(u)的结点。的结点。算法设计与分析算法设计与分析 贪心算法贪心算法产生最短路径的贪心方法产生最短路径的贪心方法 选出了结点选出了结点u并生成了从并生成了从v0到到u的最短路径之后，结点的最短路径之后，结点u就就成为成为S中的一个成员。中的一个成员。此时，那些从此时，那些从v0开始，只通过开始，只通过S中的结点并且在中的结点并且在S外的结外的结点点w处结束的最短路径可能会减小。处结束的最短路径可能

32、会减小。如果长度改变了，则它必定是由一条从如果长度改变了，则它必定是由一条从v0开始，经过开始，经过u然然后到后到w的更短路径所造成的。的更短路径所造成的。其中从其中从v0到到u的路径是一条最短路径，从的路径是一条最短路径，从u到到w的路径是边的路径是边，于是这条路径的长度就是：，于是这条路径的长度就是：DIST(u)+c(u,w)算法设计与分析算法设计与分析 贪心算法贪心算法算法设计与分析算法设计与分析 贪心算法贪心算法 算法描述算法描述：(1)用带权的邻接矩阵c来表示带权有向图,cij表示弧 上的权值.若 V,则置cij为 设S为已知最短路径的终点的集合,它的初始状态为空集.从源点v到图上

33、其余各点vi的当前最短路径长度的初值为：disti=cvi，viV (2)选择vj,使得distj=Mindisti|viV-S vj就是长度最短的最短路径的终点。令S=SUj/更新S (3)修改从v到集合V-S上任一顶点vk的当前最短路径长度:如果 distj+cjk 贪心算法贪心算法 单源最短路径单源最短路径例例 题题迭代 Svid2d3d4d5初始 1 10 30100 1 1,2 2 10 60 30100 2 1,2,4 4 10 50 30 90 3 1,2,3,4 3 10 50 30 60 41,2,3,4,5 5 10 50 30 601)v1 v2:102)v1 v3:50

34、3)v1 v4:304)v1 v5:60103010050102060算法设计与分析算法设计与分析 贪心算法贪心算法 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；te

35、mp=distj；su=true；for(int j=1；j=n;j+)；if(!sj)(cujmaxint)Type newdist=distu)+cuj;if(newdist 贪心算法贪心算法 单源最短路径单源最短路径例例 题题迭代 Svid2d3d4d5初始 1 10 30100 1 1,2 2 10 60 30100 2 1,2,4 4 10 50 30 90 3 1,2,3,4 3 10 50 30 60 41,2,3,4,5 5 10 50 30 601)v1 v2:102)v1 v3:503)v1 v4:304)v1 v5:60103010050102060算法实例算法实例 求下

36、图中求下图中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,6020453070

37、80130SHORTEST-PATHS执行踪迹执行踪迹算法设计与分析算法设计与分析 贪心算法贪心算法算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树问题陈述问题陈述:设G(V,E)是一个无向连通带权图。E中每条边(v,w)的权为cvw,若G的一个子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树.抽象描述:输入:任一连通生成子图(该子图的边集合)可行解:图的生成树,优化函数:生成树的各边权值之和 最优解:使优化函数达到最小的生成树.4.6 最小生成树最小生成树算法设计与分析算法设

38、计与分析 贪心算法贪心算法 最小生成树最小生成树应用领域与图模型算法思路算法思路:首先置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。例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 最

39、小生成树最小生成树问题：如何选取满足条件iS,jV-S,且cij最小的边(i,j),成了算法难点问题。解决方法：设置两个数组closest和lowcost。对于每个j V-S，closestj是j在S中的邻接顶点，它与j在S中的其他邻接顶点k相比较有cjclosetj cjk。lowcostj的值就是cjclosestj图 Prim算法的执行过程 97248811276414104801da(b)eicaEXTRACT-MIN(Q)Q b,c,d,e,f,g,h,i V Q aAdj a b,hb a,key b4 h a,key h8fgbh972488112764141001da(a)ei

40、cfgbh注：灰色部分表示集合S 每个结点的上的数字表示S中的结点到该结点的最小消耗，即lowcost 用图示的边的连接表示closest图 Prim算法的执行过程 97248811276414104881701hdba(d)eic h EXTRACT-MIN(Q)Q c,d,e,f,g,i V Q a,b,hA dj h a,b,i,g i h,key i7 g h,key g1fg97248811276414104801hdba(c)eicbEXTRACT-MIN(Q)Q c,d,e,f,g,h,i V Q a,bA dj b a,c,hc b,key c8key h值不变fg8图 Pri

41、m算法的执行过程 97248811276414104881260g1hdba(e)eicg EXTRACT-MIN(Q)Q c,d,e,f,iV Q a,b,h,g A dj g f,h,i f g,key f 2 i g,key i6f图 Prim算法的执行过程 97248811276414107104481220fg1hcdba(g)cEXTRACT-MIN(Q)Q d,e,iV Q a,b,c,h,g,f Adj c b,d,f,i d c,key d 7 i c,key i2ei972488112764141014104481260ghdba(f)eicfEXTRACT-MIN(Q)Q

42、 c,d,e,iV Q a,b,h,g,f Adj f c,d,e,g c f,key c4 d f,key d 14 e f,key e10f1图 4-16Prim算法的执行过程 97248811276414107104481220fg1hicdba(h)iEXTRACT-MIN(Q)Q d,eV Q a,b,c,d,h,i,g,f Adj d c,e,f e9724881127641410794481220dEXTRACT-MIN(Q)Q eV Q a,b,c,d,h,i,g,f Adj d c,e,f e d,key e9g1hiceba(i)df2图 4-16Prim算法的执行过程 9

43、724881127641410794481220eEXTRACT-MIN(Q)QV Qa,b,c,d,h,i,g,f,eAdje d,f g1hiceba(j)dftemplate 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)

44、&(!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条边。直到只剩

45、下一个连通分支为止。此时，这个连通分枝就是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)例例 题题算法设计与分析

46、算法设计与分析 贪心算法贪心算法 最小生成树最小生成树优先队列 定义：优先队列定义：优先队列中元素出队列的顺序由元素的优先级决中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。而不是元素进入队列的次序。可以利用堆数据结构来高效地实现优先队列。可以利用堆数据结构来高效地实现优先队列。实现：优先队列（实现：优先队列（priority queuepriority queue）是）是0 0个或多个元素的个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行集合，每个元素都有一个优先权或

47、值，对优先队列执行的操作有的操作有1)1)查找；查找；2)2)插入一个新元素；插入一个新元素；3)3)删除。在最删除。在最小优先队列（小优先队列（min priority q u e u emin priority q u e u e）中，查找操作）中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列（对于最大优先队列（max priority queuemax priority queue），查找操作），查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。用来搜索优先权最大的元素，删除操作用来删除该元素。处理：

48、优先权队列中的元素可以有相同的优先权，查找处理：优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。与删除操作可根据任意优先权进行。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 x I n s e rt(x)I n s e rt(x)：将：将x x 插入队列插入队列并查集并查集 在一些应用问题中，我们

49、需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集 (给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。)并查集的数学模型并查集的数学模型 并查集的数学模型是若干不相交的动态集合的集合SA,B,C,.，它支持以下的运算：(1)INITIAL(A,x)：构造一个取名为A的集合，它只包含

50、一个元素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!