贪心算法ppt课件.ppt

将问题的求解过程看作是一系列选择将问题的求解过程看作是一系列选择, ,每次选择一个每次选择一个输入输入, ,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择( (局部最优解局部最优解).).每作一次选择后每作一次选择后, ,所求问题会简化为一个规模更小的子所求问题会简化为一个规模更小的子问题问题. .从而通过每一步的最优解逐步达到整体的最优解从而通过每一步的最优解逐步达到整体的最优解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 void GreedySelector(int n, Type s[ ], Type f[ ], bool A[] ){ A[ 1 ] = true; int j = 1; //从第二个活动开始检查是否与前一个相容 for (int i=2;i< =n;i+ +) { if (s[i]>=f[j]) { A[i] = 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, 1]1、最优装载的贪心算法算法设计与分析算法设计与分析 > > 贪心算法贪心算法template < class Type >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 ++) x[i] = 0;for (int i = 1;i<= n && w[t[i]] <= c; i++) { x[t[i]] = 1; c-= w[t[i]]; //调整剩余空间}}•2、贪心选择性质、贪心选择性质• 可以证明最优装载问题具有贪心选择性质。

可以证明最优装载问题具有贪心选择性质 •3、最优子结构性质、最优子结构性质•最优装载问题具有最优子结构性质最优装载问题具有最优子结构性质•算法证明算法证明:由最优装载问题的贪心选择性质和最优由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法子结构性质，容易证明算法loading的正确性的正确性•算法分析算法分析:算法算法loading的主要计算量在于将集装箱的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为依其重量从小到大排序，故算法所需的计算时间为 O(nlogn) [最优化描述最优化描述] 找一个找一个n元元向量向量(x1,…xn) 0  xi  1 使得使得 且且 . .其中其中 C, Wi, vi>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 xi∑∑vixi①①(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,1}{0,1,1/2} {...}{1,2/15,0}20202028.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++) x[i] = 0;float c = M; //c为背包剩余空间/for (i =1;i <= n;i ++) { if (w[t[i]]> c) break; x[t[i]]= 1; c-= w[t[i]]; }if(i<= n) x[t[i]] = c/w[t[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++) x[i]=0;• float c=M;• for (i=1;i<=n;i++) {• if (w[i]>c) break;• x[i]=1;• c-=w[i];• }• if (i<=n) x[i]=c/w[i];•} 算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。

因此，算法的计序因此，算法的计算时间上界为算时间上界为O O（（nlognnlogn）为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包问题具有贪心选择性问题具有贪心选择性质质对于0-10-1背包问题背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择由此就导出许多互相重叠的子问题这正是该问题可用动态规划动态规划算法算法求解的另一重要特征实际上也是如此，动态规划算法的确可以有效地解0-1背包问题 思考题思考题•0/10/1背背包包问问题题：：在在杂杂货货店店比比赛赛中中你你获获得得了了第第一一名名，，奖奖品品是是一一车车免免费费杂杂货货店店中中有有n n 种种不不同同的的货货物物规规则则规规定定从从每每种种货货物物中中最最多多只只能能拿拿一一件件，，车车子子的的容容量量为为c c，，物物品品i i 需需占占用用w wi i 的的空空间间，，价价值值为为p pi 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) {//根据权f[1:n]构造霍夫曼树 //创建一个单节点树的数组 Huffman *W=newHuffman [n+1]； BinaryTree z,zero； for(int i=1；i<=n；i++){ z.MakeTree(i, zero, zero)； W[i].weight=f[i]； W[i].tree=z: } //数组变成—个最小堆 MinHeap>Q(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经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T算法huffmanTree用最小堆实现优先队列Q初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间因此，关于n个字符的哈夫曼算法的计算时间计算时间为O(nlogn) 最优子结构: 设T为带权w1≤w2≤... ≤wt的最优树,若将以带权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶,得到一棵新树T', 则T'也是最优树贪心选择性 : 设T为带权w1≤w2≤... ≤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,初始时v0S, 其最短路长为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来表示带权有向图, c[i][j]表示弧 上的权值. 若 V,则置c[i][j]为 设S为已知最短路径的终点的集合,它的初始状态为空集. 从源点v到图上其余各点vi的当前最短路径长度的初值为： dist[i]=c[v][i] ，viV (2) 选择vj, 使得dist[j]=Min{dist[i] | viV-S} vj就是长度最短的最短路径的终点。

令S=SU{j}//更新S (3) 修改从v到集合V-S上任一顶点vk的当前最短路径长度: 如果 dist[j]+c[j][k]< dist[k] 则修改 dist[K]= dist[j]+c[j][k] //更新dist和prev (4) 重复操作(2),(3)共n-1次.算法设计与分析算法设计与分析 > > 贪心算法贪心算法 > >单源最短路径单源最短路径例例 题题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 s[maxint]； for (int i=1;i<=n; i++){ dist[i]=c[v][i]； s[i]=false； if(dist[i]= =maxint) prev[i]=0； else prev[i]=v ; } dist[v]=0；s[v]=true； for (int i=1;i > 贪心算法贪心算法 > >单源最短路径单源最短路径例例 题题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)置初值置初值--10205030∞∞∞121,20204530∞90∞231,2,402045308590∞341,2,4,302045307090∞451,2,4,3,502045307080140561,2,4,3,5,602045307080130SHORTEST-PATHS执行踪迹执行踪迹算法设计与分析算法设计与分析 > > 贪心算法贪心算法算法设计与分析算法设计与分析 > > 贪心算法贪心算法 > >最小生成树最小生成树问题陈述问题陈述:设G(V,E)是一个无向连通带权图。

E中每条边(v, w)的权为c[v][w],若G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树 生成树各边权的总和称为该生成树的耗费 在G的所有生成树中,耗费最小的生成树称为G的最小生成树.抽象描述: 输入:任一连通生成子图 (该子图的边集合) 可行解:图的生成树, 优化函数:生成树的各边权值之和 最优解:使优化函数达到最小的生成树.4. 6 最小生成树最小生成树算法设计与分析算法设计与分析 > > 贪心算法贪心算法 > >最小生成树最小生成树应用领域与图模型算法思路算法思路: 首先置S={1}, T= Ø .若SV, 就作如下的贪心选择： 选取满足条件iS, jV-S,且c[i][j]最小的边(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且 jV- S的最小权边; T=TU{(i,j)}; S= S U{j}; } }算法描述算法描述 Prim算法算法设G=(V,E)是一个连通带权图, y={l, 2, …, n}。

例例 题题算法设计与分析算法设计与分析 > > 贪心算法贪心算法 > >最小生成树最小生成树问题：如何选取满足条件iS, jV-S,且c[i][j]最小的边(i, j), 成了算法难点问题解决方法： 设置两个数组closest和lowcost对于每个j V-S，closest[j]是j在S中的邻接顶点，它与j在S中的其他邻接顶点k相比较有c[j][closet[j]] ≤c[j][k]lowcost[j]的值就是c[j][closest[j]]图 Prim算法的执行过程 注：灰色部分表示集合S 每个结点的上的数字表示S中的结点到该结点的最小消耗，即lowcost 用图示的边的连接表示closest图 Prim算法的执行过程 图 Prim算法的执行过程 图 Prim算法的执行过程 图 4-16Prim算法的执行过程 图 4-16Prim算法的执行过程 template < class Type >void Prim(int n, Type * * c) { Type lowcost[maxint]; int closest[ maxim]; bool s[maxint]; s[1] = true; for(int i = 2;i<= n; i++){ lowcost[i] = c[l][i]; closest[ i] = 1; s[i]= false; } for (int i = 1; i< n; i++){ Type min = inf; int j = 1; for (int k = 2;k<= n; k++) if ((lowcost[k] < min)&&(!s[k])) min = lowcost[ k]; j=k;} cout< < j < < ' ' < < closest[j] < < end}; s[j] = true; for(intk= 2; k<= n; k++) if ((c[j][k] < lowcost[k])&&(!s[k])) lowcost[i] = c[j][k]; closest[ k] =j; }}}Prim算法算法算法分析算法分析: O(n2).算法设计与分析算法设计与分析 > > 贪心算法贪心算法 > >最小生成树最小生成树算法思路算法思路:首先将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=<1, 2, …, n}例例 题题算法设计与分析算法设计与分析 > > 贪心算法贪心算法 > >最小生成树最小生成树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 x•I n s e rt (x)I n s e rt (x)：将：将x x 插入队列插入队列并查集并查集• 在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并其间要反复用到查找一个元素在哪一个集合的运算适合于描述这类问题的抽象数据类型称为并查集 (给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集)并查集的数学模型并查集的数学模型• 并查集的数学模型是若干不相交的动态集合的集合S＝{A,B,C,...}，它支持以下的运算：• (1)INITIAL(A,x)：构造一个取名为A的集合，它只包含一个元素x；• (2)MERGE(A,B)：将集合A和B合并，其结果取名为A或B；• (3)FIND(x)：找出元素x的所在集合，并返回该集合的名字。

template < class Type >bool Kruskal(int n, int e, EdgeNode < Type > E[ ], EdgeNode < Type > t[ ] ) MinHeap < EdgeNode < Type > > 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) { t[k ++] = 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) 森林由森林由3棵树组成棵树组成图 Kruskal算法的执行过程(续) 拒绝边拒绝边(h,i) 接受边接受边(a,h) UNION(a,h) 森林由森林由2棵树组成棵树组成 拒绝边拒绝边(b,c) 接受边接受边(d,e) UNION(d,e) 森林由森林由1棵树组成棵树组成图 Kruskal算法的执行过程(续) 正确性证明1、需要证明以下两点： 1) 只要存在生成树，K r u s k a l算法总能产生一棵生成树； 2) 产生的生成树具有最小耗费。

2、证明1：令G为任意加权无向图（即G是一个无向网络）从1 2 . 11 . 3节可知当且仅当一个无向图连通时它有生成树而且在Kruskal 算法中被拒绝（丢弃）的边是那些会产生环路的边删除连通图环路中的一条边所形成的图仍是连通图，因此如果G在开始时是连通的，则T与E中的边总能形成一个连通图也就是若G开始时是连通的，算法不会终止于E= 和| T |< n- 13、证明2：现在来证明所建立的生成树T具有最小耗费由于G具有有限棵生成树，所以它至少具有一棵最小生成树令U为这样的一棵最小生成树， T与U都刚好有n- 1条边如果T=U, 则T就具有最小耗费，那么不必再证明下去因此假设T≠U，令k(k >0) 为在T中而不在U中的边的个数，当然k 也是在U中而不在T中的边的数目通过把U变换为T来证明U与T具有相同的耗费，这种转化可在k 步内完成每一步使在T而不在U中的边的数目刚好减1而且U的耗费不会因为转化而改变经过k 步的转化得到的U将与原来的U具有相同的耗费，且转化后U中的边就是T中的边由此可知， T具有最小耗费•算法分析算法分析:当图的边数为e时，将其组成优先队列需要时间O(e)• while循环中,DeleteMin需要O(loge)时间因此关于优先队列所作运算需时间O(eloge)。

• 实现UnionFind所需的时间为O(eloge) • 所以Kruska的时间是O(eloge),适合求边数较少的最小生成树 反之，用Prim算法 [最小代价通讯网络] 在N城市之间架设通讯线路,要求造价最低.城市之间所有可能的通讯连接视作一个无向图G,G中每边的权值表示建成这段线路的代价. 问题转化为求一棵最小生成树.问题描述: 输入:任一连通图G (该图的边集合) 可行解:图G的生成树 优化函数:生成树的各边权值之和 最优解:使优化函数达到最小值的生成树.最优化问题(optimization problem):问题可描述为有n个输入(x1,x2,...xn),一组约束条件和一个优化(目标)函数满足约束条件的输入称为可行解可行解,它它是输入的一个子集.使优化函数取得极值的可行解称为最优解最优解.算法设计与分析算法设计与分析 > > 贪心算法贪心算法例例1 1*旅行商问题(货郎担问题)问题: 设一个由N个城市v1,v2,…vn组成的网络, ci,j 为从vi 到vj的代价不妨设ci,j = cj,i ,且ci,i= .一推销员要从某城市出发经过每城市一次且仅一次后返回出发地问如何选择路线使代价最小。

5143173422算法设计与分析算法设计与分析 > > 贪心算法贪心算法抽象描述抽象描述:将城市以及之间的道路抽象为一个无向图G, G中每边的权值表示这段线路的代价. 问题转化为求一条最佳周游路线:从一点出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小.v1v5v2v4v3C=输入:城市的数目n,代价矩阵c=c(1..n,1..n).输出: 最小代价路线1. tour:=0; // tour 纪录路线/2. cost:=0; // cost 纪录到目前为止的花费/3. v:=N; // N为起点城市, v为当前出发城市/4. for k:=1 to N-1 do 5. { tour:= tour+(v,w) //(v,w)为从v到其余城市代价中值最小的边/6. cost:= cost+c(v,w) 7 v:=w}8 tour:= tour+(v,N)9 cost:= cost+c(v,N) print tour, cost }算法的最坏时间复杂性为O(n2)*该算法不能求的最优解.算法设计与分析算法设计与分析 > > 贪心算法贪心算法该问题为该问题为NPNP难问题难问题. .算法设计与分析算法设计与分析 > > 贪心算法贪心算法问问题题:设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。

要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内 由m台机器加工处理完成 4.7 多机调度问题多机调度问题该问题为该问题为NPNP完全问题完全问题. .•调度问题是著名的NP-复杂问题（NP表示nondeterministic polynornial) 中的一种NP-复杂及NP -完全问题是指尚未找到具有多项式时间复杂性算法的问题•NP-完全问题是一类判断问题，也就是说，这类问题的答案为是或否机器调度问题不是一个判断题，因为它的答案是给出作业在机器间的分配方案（使完成时间最少）贪心近似算法贪心近似算法: 采用最长处理时间作业优先的贪心策略:当n≤m时, 只要将机器i的[0, ti]时间区间分配给作业i即可当n>m时, 将n个作业依其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机7个独立作业{1, 2, 3, 4, 5, 6, 7}由M1,M2和M3来加工处理各作业所需时间间分别为{2, 14, 4, 16, 6, 5, 3}161465423 图给出了七个作业在三台机器上进行调度的情形，七个作业所需时间分别为（2,14,4,16,6,5,3）三台机器分别被编号为M1、M2 和M3。

每个阴影区代表作业的运行区间，阴影区的编号代表作业的索引号• 作业4在0到16 时刻被调度到机器1（M1）上运行，在这16个时间单位中，机器1完成了对作业4的处理作业2在0到14时刻被调度到机器2上处理，之后机器2在1 4到17时刻处理作业7在机器3上，作业5在0～6时刻内完成，作业6在6～8时刻内完成，作业3在11～1 5时刻内完成，作业1在15～17时刻内完成注意到每个作业只能在一台机器上si 从时刻到si+ti 时刻内完成且任何机器在同一时刻仅能处理一个作业，完成所有作业的时刻为17，因此完成时间或调度长度为17算法设计与分析算法设计与分析 > > 贪心算法贪心算法class JobNode { friend void Greedy(JobNode * , int, int); friend void main(void); public: operator int () const {return time; } private: int ID, time; };class MachineNode { friend void Greedy(JobNode *, int, int); public: operator int( ) const { return avail; } private: int ID, avail; }多机调度问题的多机调度问题的贪心近似算法贪心近似算法多机调度问题的多机调度问题的贪心近似算法贪心近似算法templatevoid Greedy(Type a[]，，int n，，int m){if (n<=m){ cont<<”为每个作业分配一台机器为每个作业分配一台机器.“<H(m)；；MachineNode x；；for(int：：i=1；；i<=m; i++){ x．．avail=0；； x．．ID=i; H．．Insert(x)；；}for(inti：：n；；i>=1；；i--){ H．．DeleteMin(x)；； cout<<”将机器将机器”<