第四次(贪心).ppt

《第四次(贪心).ppt》由会员分享，可在线阅读，更多相关《第四次(贪心).ppt（58页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法第八章第八章 NPNP完全性理论简介完全性理论简介算法设计与分析算法设计与分析 目录目录14.1 4.1 最优化问题简介最优化问题简介4.2 4.2 贪心算法思路贪心算法思路4.3 4.3 任务安排问题任务安排问题4.4 4.4 装载问题装载问题4.5 4.5 背包问题背包问题4.6 4.6 哈夫曼编码哈夫曼编码4.7 4.7 最短路径最短路径 4.8 4.8 最小生成树最小

2、生成树算法设计与分析算法设计与分析 目录目录 4.9 4.9 多机调度问题多机调度问题2第四章.贪心算法贪心算法(Greed method)用以求解用以求解最优化问题最优化问题算法设计与分析算法设计与分析 贪心算法贪心算法34-1.贪心算法贪心算法基本思想基本思想将问题的求解过程看作一系列选择（每次选择确定一个输将问题的求解过程看作一系列选择（每次选择确定一个输入值）入值）,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择(局部最优解局部最优解).).每作一次选择后每作一次选择后,所求问题会简化为一个规模更小的子所求问题会简化为一个规模更小的子问题问题.从而通过每一步的最优解逐

3、步达到整体最优解从而通过每一步的最优解逐步达到整体最优解 算法设计方法算法设计方法 贪心算法贪心算法 贪心算法的一般模式 procedure greedy(A,n)solusion for i 1 to n do xselese(A)if feasible(solusion,x)solusionunion(solusion,x)repeat return(solusion)/从从A中选择一个当前最好输入中选择一个当前最好输入/判断判断X是否包含在当前解中是否包含在当前解中./将将X与解合并与解合并,修改目标函数修改目标函数算法设计与分析算法设计与分析 贪心算法贪心算法4 适用问题 具备具备贪心

4、选择贪心选择和和最优子结构最优子结构性质的最优化问题性质的最优化问题 算法优点 求解速度快求解速度快,时间复杂性有较低的阶时间复杂性有较低的阶.整体的最优解可通过一系列局整体的最优解可通过一系列局部最优解达到部最优解达到.每次的选择可每次的选择可以依赖以前作出的选择以依赖以前作出的选择,但不但不能依赖于后面的选择能依赖于后面的选择.问题的整体最优解中问题的整体最优解中包含着它的子问题的包含着它的子问题的最优解最优解.算法缺点 需证明是最优解需证明是最优解.常见应用 背包问题背包问题,最小生成树最小生成树,最短路径最短路径,作业调度等作业调度等等等 算法设计方法算法设计方法 贪心算法贪心算法算法

5、设计与分析算法设计与分析 贪心算法贪心算法5例例1 最小代价通讯网络:在在N个城市之间架设通讯线路个城市之间架设通讯线路,要求造价最低要求造价最低.问题描述问题描述 输入输入:任一连通图任一连通图G(G的邻接矩阵的邻接矩阵)可行解可行解:图图G的生成树的生成树 优化函数优化函数:生成树的权生成树的权 最优解最优解:使优化函数达到最小值的生成树使优化函数达到最小值的生成树.问题可描述为有问题可描述为有n个输入个输入(x1,x2,.xn),一组约束条件和一组约束条件和一个优化一个优化(目标目标)函数。满足约束条件的输入称为函数。满足约束条件的输入称为可行解可行解,使优化函数取得极值的可行解称为使优

6、化函数取得极值的可行解称为最优解最优解.算法设计与分析算法设计与分析 贪心算法贪心算法4.2最优化问题最优化问题 简介简介(optimization problem)城市间的通讯连接视作一个无向图城市间的通讯连接视作一个无向图G,G中每边的权值表中每边的权值表示建成这段线路的代价示建成这段线路的代价.问题转化为求一棵最小生成树问题转化为求一棵最小生成树.6e1(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)依次添加各边依次添加各边,若出

7、现回路若出现回路 则忽略此边则忽略此边.4)加入加入n-1条边后就得到最小条边后就得到最小 生成树生成树.12537图论图论 树与生成树树与生成树求最小生成树求最小生成树(Kruscal)最优解最优解:(e1,e6,e11,e5,e4)7算法思路算法思路1.将活动按结束时间排序将活动按结束时间排序,得到活动集得到活动集E=e1,e2en；2.先将先将e1选入结果集合选入结果集合A中，即中，即A=e1；3.依次扫描每一个活动依次扫描每一个活动 ei:如果如果ei的的si 最后最后 一个选入一个选入A的活动的活动ej的的 fj,则将则将ei选入选入A中中,否则放弃否则放弃ei4.3.活动安排问题问

8、题陈述问题陈述有有n个活动个活动E=1,2,n要使用同一资源要使用同一资源,同一时间只允许一个活动使用该资源同一时间只允许一个活动使用该资源.设活动设活动i的起止的起止时间区间时间区间si,fi),如果选择活动如果选择活动i,则它在时间区间则它在时间区间si,fi)内占用该资源内占用该资源;若区间若区间 si,fi)与与sJ,fJ)不不相交相交,则称活动则称活动i与与j是是相容的相容的.要求在所给的活动集合要求在所给的活动集合中选出最大相容活动子集中选出最大相容活动子集.算法设计与分析算法设计与分析 贪心算法贪心算法8算法设计与分析算法设计与分析 贪心算法贪心算法 1 2 3 4 5 6 7

9、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,11),也可表示为等长也可表示为等长n元数组元数组:(1,0,0,1,0,0,0,1,0,0,1)9算法操作过程算法操作过程算法设计与分析算法设计与分析 贪心算法贪心算法10活动安排问题贪心算法Template void GreedySelector(int n,T s,T f,bool A )A1=true;int j=1;

10、/从第二个活动开始检查是否与前一个相容 for(int i=2;i=f j)Ai=true;j=i;else A i=false;T(n)=O(nlogn)(未排序时未排序时)算法分析 T(n)=O(n)(排序时排序时)各活动的起始时间和结束各活动的起始时间和结束时间存储于数组时间存储于数组s s和和f f中且中且按结束时间的非减序排列按结束时间的非减序排列算法设计与分析算法设计与分析 贪心算法贪心算法11 装装载载问问题题:一一艘艘大大船船装装载载货货物物。所所有有待待装装货货物物都都装装在在 n个个大大小小一一样样的的集集装装箱箱中中,集集装装箱箱的的重重量量各各不不相相同同。设设第第i个

11、个集集装装 箱箱 的的 重重 量量 为为wi(1 i n).船船 的的 最最 大大载重量为载重量为c,求装载方案使装船的箱子数最多求装载方案使装船的箱子数最多.问题描述问题描述 输入输入:(x1,x2,xn),xi=0:货箱货箱i不装船不装船;xi=1,货箱货箱i装装船船可行解可行解:满足约束条件满足约束条件 c 的输入的输入优化函数优化函数:最优解最优解:max 4.4 最优装载12问题描述问题描述 输入输入:(x1,x2,.xn),xi=0,货箱货箱i不装船不装船;xi=1,货箱货箱i装船装船.可行解可行解:满足约束条件满足约束条件 c 的输入的输入 优化函数优化函数:最优解最优解:使优化

12、函数达到最大值的可行解使优化函数达到最大值的可行解.算法设计与分析算法设计与分析 贪心算法贪心算法设设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算法思路算法思路 将装船过程化为多步选择，每步装一个货箱将装船过程化为多步选择，每步装一个货箱每次从剩下的货箱中选择重量最轻的

13、货箱每次从剩下的货箱中选择重量最轻的货箱.如此下去直到如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱所有货箱均装上船或船上不能再容纳其他任何一个货箱13最优装载的贪心算法template void Loading(int x,T w,T c,int n)int*t=new int n+1;/w 的游标 Sort(w,t,n);/按货箱重量递增排序/for(int i=1;i =n;i+)xi=0;for(int i=1;i=n&w t i 算法设计方法算法设计方法 贪心算法贪心算法X:解向量w:货箱重量c:船的载重量n:货箱数量算法设计与分析算法设计与分析 贪心算法贪心算法14最

14、优化描述最优化描述 输入输入:n元元向量向量(x1,xn)0 xi 1 约束条件约束条件:.:.4-54-5 背包问题背包问题 (Knapsack Problem)问题描述问题描述设有设有n个物体和一个背包个物体和一个背包,物体物体i的重量为的重量为wi,价值为价值为vi,背包的承载的重量为背包的承载的重量为C.若将物体若将物体i的的xi部分部分(1 i n,0 xi 1)装入背包装入背包,则具有价值为则具有价值为vi xi.求解目标求解目标是找到一个方案是找到一个方案,使放入背包的物体总价值最高使放入背包的物体总价值最高.算法设计与分析算法设计与分析 贪心算法贪心算法其中其中 C,Wi,vi

15、0,1 i n 目标函数目标函数:15例例 n=3,c=20,(n=3,c=20,(v1,1,v2,2,v3)=(25,24,15),3)=(25,24,15),(w1,w2,w3)=(18,15,10)(w1,w2,w3)=(18,15,10)x1,x2,x3x1,x2,x3 0,2/3,10,2/3,1 0,1,1/20,1,1/2 .1,2/15,01,2/15,0 20202028.23131.5.算法设计与分析算法设计与分析 贪心算法贪心算法 算法思路算法思路 1).1).将各物体按单位价值由高到低排序将各物体按单位价值由高到低排序.2).2).取价值最高者放入背包取价值最高者放入背

16、包.3).3).计算背包剩余空间计算背包剩余空间.4).4).在剩余物体中取价值最高者放入背包在剩余物体中取价值最高者放入背包.当背包剩余容量当背包剩余容量=0=0或物体全部装入背包为止或物体全部装入背包为止16void 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;/c为背包剩余空间/for(i=1;i c)break;xi=1;c-=wi;if(i 贪心算法贪心算法X:解向量w:物体重量V:物体价值M:背包容量n:物体数量17背

17、包问题中的物体不能分拆背包问题中的物体不能分拆,只能整个装入称为只能整个装入称为0-1背包问题背包问题.用贪心算法能得到用贪心算法能得到0-1背包的最优解吗背包的最优解吗?算法设计与分析算法设计与分析 贪心算法贪心算法 n=3,c=25,(v1,v2,v3)=(35,24,15),(w1,w2,w3)=(18,15,10)例分析:单位价值(v1/w1,v2/w2,v3/w3)=(35/18,24/15,15/10)=(1.94,1.6,1.5)装入顺序:(x1,x2,x3)贪心解:(1,0,0),总价值 35 最优解:(0,1,1),总价值 3918 问问题题 设设一一个个由由N个个城城市市v

18、1,v2,vn组组成成的的网网络络,ci,j 为为从从vi 到到vj的的代代价价不不妨妨设设ci,j=cj,i,且且ci,i=.一一推推销销员员要要从从某某城城市市出出发发经经过过每每城城市市一一次次且且仅仅一一次次后后返返回回出出发发地地问如何选择路线使代价最小。问如何选择路线使代价最小。问题抽象问题抽象将城市以及之间的道路抽象为一个无向图将城市以及之间的道路抽象为一个无向图G,G中每边的权值表示这段线路的代价中每边的权值表示这段线路的代价.问题转化为求一问题转化为求一条最佳周游路线条最佳周游路线:从一点出发从一点出发,经过每点一次且仅一次并经过每点一次且仅一次并返回原点返回原点,且该路线的

19、总代价最小且该路线的总代价最小.算法设计与分析算法设计与分析 贪心算法贪心算法*旅行商问题(货郎担问题)输入输入:任一连通图任一连通图G 可行解可行解:从从v0v0的汉密顿回路的汉密顿回路 优化函数优化函数:回路各边的权之和回路各边的权之和 最优解最优解:使优化函数达到最小值的回路使优化函数达到最小值的回路.195143173422v1v5v2v4v3C=算法设计与分析算法设计与分析 贪心算法贪心算法*旅行商问题旅行商问题(货郎担问题货郎担问题)贪心解:最优解:12543 1,路长10 12534 1,路长1420输入:城市的数目n,代价矩阵c=c(1.n,1.n).输出:最小代价路线1.to

20、ur:=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难问题难问题.旅行商问题

21、贪心近似算法旅行商问题贪心近似算法21算法设计与分析算法设计与分析 贪心算法贪心算法上机作业：上机作业：1.编写一个完整的背包问题贪心算法程序编写一个完整的背包问题贪心算法程序.2.找零钱找零钱.设集合设集合1,2,5,10,50,100 是货币单位。是货币单位。1)编写贪心算法编写贪心算法,使买东西时找回的硬币数目最小使买东西时找回的硬币数目最小.2)分析你的算法复杂性分析你的算法复杂性.3)货币单位集满足何条件可确保贪心法获最优解货币单位集满足何条件可确保贪心法获最优解?22算法设计与分析算法设计与分析 贪心算法贪心算法 贪心算法贪心算法要点要点将问题的求解过程看作一系列选择将问题的求解过

22、程看作一系列选择,每次选择一个输入每次选择一个输入,每次选择都是当前状态下的最好选择每次选择都是当前状态下的最好选择(局部最优解局部最优解).).每作每作一次选择后一次选择后,所求问题会简化为一个规模更小的子问题所求问题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体最优解从而通过每一步的最优解逐步达到整体最优解.一一.最优化问题最优化问题1.1.输入输入(或问题的解或问题的解):):可表为可表为n n元向量元向量(x1,x2,.(x1,x2,.xnxn).).2.约束条件约束条件:满足约束条件的向量为可行解满足约束条件的向量为可行解.3.优化函数优化函数:是与可行解分量相关的

23、函数是与可行解分量相关的函数.4.最优解最优解:使优化函数达到极限值的可行解使优化函数达到极限值的可行解.二二.算法思路算法思路23算法设计与分析算法设计与分析 贪心算法贪心算法三三.算法模式 for i 1 to n do xselese(A)if feasible(solusion,x)solusionunion(solusion,x)retur n(solusion)/从从A中选择一个当前最好输入中选择一个当前最好输入/判断判断X是否包含在当前解中是否包含在当前解中./将将X与解合并与解合并,同同时修改目标函数时修改目标函数.四四.适用问题适用问题具备具备贪心选择贪心选择和和最优子结构最

24、优子结构性质的最优化问题性质的最优化问题24 问问题题 通通讯讯过过程程中中需需将将传传输输的的信信息息转转换换为为二二进进制制码码.由由于于英英文文字字母母使使用用频频率率不不同同,若若频频率率高高的的字字母母对对应应短短的的编编码码,频频率率低低的的字字母母对对应应长长的的编编码码,传传输输的的数数据据总总量量就就会会降降低低.要要求求找找到到一一个个编编码码方方案案,使使传传输输的的数数据量最少据量最少(最佳编码最佳编码).).算法设计与分析算法设计与分析 贪心算法贪心算法找最佳前缀编码问题可化为求一棵找最佳前缀编码问题可化为求一棵为能正确译码为能正确译码,编码需采用编码需采用前缀码前缀

25、码.前缀码和二叉树一一对应前缀码和二叉树一一对应.最优二叉树最优二叉树是是 编编 码码 的的 集集 合合.其其任任一一编编码码不不能能是是另另一一编编码码的的前前缀缀.4.6 哈夫曼编码25最优二叉树最优二叉树树的权树的权:在在叶带权二叉树叶带权二叉树中中,若若带权为带权为wi的叶的叶,其通路长度为其通路长度为L(wi),则称则称 为该叶带权二叉树的为该叶带权二叉树的权权.最优二叉树最优二叉树:在所有叶带权为在所有叶带权为w1,w2,wt的二叉树的二叉树T中中 w(T)最小者称之最小者称之.图论图论 根根树及其应用树及其应用w(T)=wi L(wi)123451245334521w(T)为33

26、w(T)为39w(T)为5026算法设计与分析算法设计与分析 贪心算法贪心算法输入输入(x1,xn):):叶权叶权 (各字符出现的频率各字符出现的频率)约束条件约束条件:叶带权二叉树叶带权二叉树(前缀码前缀码)最优解最优解:树权树权 最小的二叉树（最佳编码）最小的二叉树（最佳编码）抽象描述抽象描述w(T)27设在设在1000个字母的文章中各字母出现的频率为个字母的文章中各字母出现的频率为:a:83,b:14,c:28,d:38,e:131,f:29,g:20,h:53.14 20 28 29 38 53 83 131 34 28 29 38 53 83 131 34 57 38 53 83 1

27、31 57 72 53 83 131 72 110 83 131 110 155 131155 241396最佳编码最佳编码:a:10;b:1111;c:0101;d:110;e:00;f:0100;g:1110;h:0111)将权从小到大排序将权从小到大排序2)每次选取最小权合并每次选取最小权合并例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码28算法设计与分析算法设计与分析 贪心算法贪心算法1)以以n个字母为结点构成个字母为结点构成n棵仅含一个点的二叉树棵仅含一个点的二叉树 集合集合,字母的频率即为结点的权字母的频率即为结点的权2)每次从二叉树集合中找出两个权

28、最小者合并每次从二叉树集合中找出两个权最小者合并 为一棵二叉树为一棵二叉树:增加一个根结点将这两棵树作增加一个根结点将这两棵树作 为左右子树为左右子树.新树的权为两棵子树的权之和新树的权为两棵子树的权之和.3)反复进行步骤反复进行步骤2)直到只剩一棵树为止直到只剩一棵树为止.算法思路算法思路29算法设计与分析算法设计与分析 贪心算法贪心算法 哈夫曼编码哈夫曼编码30 template BinaryTree HuffmanTree(T f,int n)/根据权根据权 f 1:n构造霍夫曼树构造霍夫曼树 /创建一个单节点树的数组创建一个单节点树的数组 Huffman*W=newHuffman n+

29、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 贪心算法贪心算法 哈夫曼编码哈夫曼编码32 问题问题 给定带权有向图给定带权有向图G=(V,E),要求找出从要求找出从V的一点的一点v0(源点源点)到其他任意顶点的最短路径到其他任意顶点的最短路径.算法设计与分析算法设计与分析 贪

30、心算法贪心算法算法思路(Dijkstra):设最短路长已知的终点集合为设最短路长已知的终点集合为S,初始时初始时v0 S,其最短路长为其最短路长为0.然后用贪心选择逐步扩充然后用贪心选择逐步扩充S:每次在每次在V-S中中,选择选择长度最短的一条最短路径长度最短的一条最短路径的终点加的终点加入入S例例 题题求路长最短的最短路径求路长最短的最短路径:只需只需求出求出v0到到V-S中各点的中各点的当前最当前最短路长短路长并取最小者的终点并取最小者的终点u加入加入S即可即可.例例 题题计算计算v0到到V-S中各点的中各点的当前最短路长：当前最短路长：该长度或者是弧该长度或者是弧(v0,u),或者是从或

31、者是从v0出发出发,中途只经过中途只经过S中的顶点到达中的顶点到达u的路的路径长径长.4.7 4.7 单源最短路径单源最短路径33算法设计与分析算法设计与分析 贪心算法贪心算法例如例如:v1到其他各点的最短路到其他各点的最短路34算法设计与分析算法设计与分析 贪心算法贪心算法 算法描述算法描述 (1)用代价矩阵用代价矩阵c来表示带权有向图来表示带权有向图,cij表示弧表示弧 上的权值上的权值.若若 E,则置则置cij为为 设设S为已知最短路径的终点的集合为已知最短路径的终点的集合,初值为空初值为空.从源点从源点v到图上其余各点到图上其余各点vi的当前最短路径长度为的当前最短路径长度为 Di,其

32、初值为其初值为 Di=cvi vi V (2)选择选择vj,使得使得Dj=Min Di|vi V-S vj就是长度最短的最短路径的终点。令就是长度最短的最短路径的终点。令S=S j (3)修改从修改从v到集合到集合V-S上任一顶点上任一顶点vk的当前最短路径长度的当前最短路径长度:如果如果Dj+cjk 贪心算法贪心算法 单源最短路径单源最短路径例例 题题1)v1 v2:102)v1 v3:503)v1 v4:304)v1 v5:6036算法设计与分析算法设计与分析 贪心算法贪心算法 void Dijkstra(int n,int v,T d,int prev,Type*c)bool smaxi

33、nt；for(int i=1;i=n;i+)di=cvi；si=false；if(di=maxint)previ=0；else previ=v;dv=0；sv=true；for(int i=1;in；i+)int temp=maxint；int u=v；for(int j=1；j=n；j+)if(!sj)&(djtemp)u=j；temp=dj；su=true；for(int j=1；j=n;j+)；if(!sj)(cujmaxint)Type newdist=du)+cuj;if(newd 贪心算法贪心算法算法分析算法分析用带权邻接矩阵表示有用带权邻接矩阵表示有n个顶点和个顶点和e条边的带权

34、有向图条边的带权有向图,主循环体需要主循环体需要O(n)时间时间,循环需要执行循环需要执行n-1次次,所以完所以完成循环需要成循环需要O(n2).38算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树问题陈述问题陈述设设G(V,E)是一个无向连通带权图。是一个无向连通带权图。E中每条中每条边边(v,w)的权为的权为cvw,若若G的一个子图的一个子图G是一棵包含是一棵包含G的所有顶点的树，则称的所有顶点的树，则称G为为G的生成树。生成树各边权的生成树。生成树各边权的总和称为该生成树的耗费。在的总和称为该生成树的耗费。在G的所有生成树中的所有生成树中,耗耗费最小的生成树称为费最小

35、的生成树称为G的最小生成树的最小生成树.抽象描述抽象描述 输入输入:任一连通图任一连通图(该图的边集合该图的边集合)可行解可行解:图的生成树图的生成树,优化函数优化函数:生成树的各边权值之和生成树的各边权值之和 最优解最优解:使优化函数达到最小的生成树使优化函数达到最小的生成树.4.8 最小生成树最小生成树例例 题题39e1(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)依次添加各边依次添加各边,若出现回路若出现回路 则忽略此边则忽略此

36、边.4)加入加入n-1条边后就得到最小条边后就得到最小 生成树生成树.12537图论图论 树与生成树树与生成树求最小生成树求最小生成树(Kruscal)最优解最优解:(e1,e6,e11,e5,e4)40算法思路算法思路将将G的的n个顶点看成个顶点看成n个孤立的连通分支个孤立的连通分支,1).将所有的边按权从小到大排序将所有的边按权从小到大排序.2).从第一条边开始从第一条边开始,依边权递增的顺序依次查看每一边依边权递增的顺序依次查看每一边 (v,w):如果端点如果端点u和和w分别是当前两个不同的连通分支分别是当前两个不同的连通分支 T1,T2中的顶点时中的顶点时,就用边就用边(u,w)将将T

37、I和和T2连接成一个连接成一个 连通分支连通分支.3).查看第查看第k+1条边条边.4).直到只剩下一个连通分支为止。直到只剩下一个连通分支为止。Kruskal算法算法 G=(V,E),V=1,2,n,c=(c i j)为代价矩阵为代价矩阵例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树41算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树例例 题题42template bool Kruskal(int n,int e,EdgeNode E,EdgeNode t )MinHeap EdgeNode H(1);H.Initialize(E,e,e)

38、;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算法算法算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树43当图的边数为当图的边数为e时，将其组成优先队列需时，将其组成优先队列需O(e)时间时间while循环中循环中,DeleteMin需要需要O(log

39、e)时间时间.故优先故优先队列所需时间队列所需时间O(eloge)。实现实现UnionFind所需时间为所需时间为O(eloge)所以所以Kruska的时间是的时间是O(eloge).适合求边数较少的最小生成树适合求边数较少的最小生成树。算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树算法分析算法分析44算法思路算法思路 1.置置S=1,T=.2.若若S V,选取边选取边(i,j):i S,j V-S,且且cij最最小小.3.将顶点将顶点j添加到添加到S中中,边边(i,j)添加到添加到T中中.4.直到直到S=V时为止时为止.T中的所有边构成中的所有边构成G的一棵最小生成树。

40、的一棵最小生成树。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)是连通带权图是连通带权图,v=l,2,n.c=(cij)为代价矩阵为代价矩阵算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树45例例 题题算法设计与分析算法设计与分析 贪心算法贪心算法 最小生成树最小生成树46template void Prim(int n,Type*c)Type lowcostmaxint;int closest

41、 maxim;bool smaxint;s1=true;for(int i=2;i=n;i+)lowcosti=cli;closest i=1;si=false;for(int i=1;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 贪心算法贪心算法 4.9 多机调度问题多机调度问题问问题题描描述述要要求求给给出出一一种种作作业业调调度

42、度方方案案，使使所所给给的的 n n个个作作业业在在尽尽可可能能短短的的时时间间内内由由 m m台台机机器器加加工工处处理理完完成成.作作 业业 i i所所需需时时间间为为 t ti i.约约定定，每每个个作作业业均均可可在在任任何何一一台台 机机 器器 上上 加加 工工 处处 理理，但但 未未 完完 工工 前前 不不 允允 许许 中中 断断,作业不能拆分成更小的子作业。作业不能拆分成更小的子作业。该问题是该问题是NPNP完全问题，到目前为止还没有有效的解法。完全问题，到目前为止还没有有效的解法。用贪心选择策略有时可设计出较好的近似算法。用贪心选择策略有时可设计出较好的近似算法。贪贪心心近近似

43、似算算法法 采采用用最最长长处处理理时时间间作作业业优优先先 的的贪贪心心策策略略.当当nm时时,只只要要将将机机器器i的的0,ti时时间间区区间间分分配配给给作作业业i即即可可;当当nm时时,将将n个个作作业业依依其其所所需需的的处处理理时时间间从从大到小排序大到小排序,然后依次将作业分配给空闲的处理机然后依次将作业分配给空闲的处理机。48算法设计与分析算法设计与分析 贪心算法贪心算法例题例题 设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为:2,14,4,16,6,5,3。按算法按算法greedygreedy产生的作业调度如下图所示产生

44、的作业调度如下图所示:所需的加工时间为所需的加工时间为1749算法设计与分析算法设计与分析 贪心算法贪心算法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,ava

45、il;多机调度问题的贪心近似算法多机调度问题的贪心近似算法50templatevoid Greedy(Type a，int n，int m)if(n=m)cont”为每个作业分配一台机器为每个作业分配一台机器.“endl return；Sort(a，n)；MinHeapH(m)；MachineNode x；for(int：i=1；i=1；i-)HDeleteMin(x)；cout”将机器将机器”xID“从从”xavail到到”(xavail十十aitime)”的时间段分配给作业的时间段分配给作业”ai.ID 贪心算法贪心算法基本思想基本思想：菲波那契提出的贪心算法菲波那契提出的贪心算法用变量用

46、变量A表示分子，变量表示分子，变量B表示分母；表示分母；（1）把）把B除以除以A的商的整数部分加的商的整数部分加1后的值作为埃及分后的值作为埃及分 数的某一个分母数的某一个分母C；（2）将）将A乘以乘以C减去减去B作为新的作为新的A；（3）将）将B乘以乘以C作为新的作为新的B；(4)输出输出1/C;（5）如果）如果A大于大于1且能整除且能整除B，则最后一个分母为，则最后一个分母为B/A（6）如果）如果A1，则最后一个分母为，则最后一个分母为B；（7）否则转步骤（）否则转步骤（2）。）。53伪代码1.用变量A表示分子，变量B表示分母；2.C=BA+13.A=A*C-B,B=B*C4.打印1/C5

47、.若A1且B/A=BA，则C=B/A6.若A1，则C=B,打印1/C7.转步骤（2）。54程序清单：程序清单：CLSDO INPUT a,b=;a,bLOOP UNTIL a 1 THEN PRINT+;LOOP WHILE a 1PRINT+1;bEND55算法设计与分析算法设计与分析 贪心算法贪心算法作业作业3、一辆汽车加满油后可行驶一辆汽车加满油后可行驶n n公里公里,途中设有若干加途中设有若干加 油油 站站,若若要要使使沿沿途途加加油油次次数数最最少少,设设计计一一个个有有效效算算 法法,给出应该在那些加油站加油给出应该在那些加油站加油.56算法设计与分析算法设计与分析 贪心算法贪心算

48、法本上机实验是本上机实验是算法设计与分析算法设计与分析课程的重要组成部分，是该课程的重要组成部分，是该课程的重要实践环节。通过上机编程，使学生加深理解、课程的重要实践环节。通过上机编程，使学生加深理解、验证、巩固课堂教学内容。本上机实验的主要任务是：验证、巩固课堂教学内容。本上机实验的主要任务是：1 1加深对所学算法设计方法的理解，加深对所学算法设计方法的理解，掌握算法设计方法掌握算法设计方法 和技巧；和技巧；2掌握算法复杂性分析的方法掌握算法复杂性分析的方法,学会分析算法的实际执学会分析算法的实际执 行效率。行效率。3运用所学算法设计方法解决简单的实际应用问题运用所学算法设计方法解决简单的实

49、际应用问题.上机目的上机目的57算法设计与分析算法设计与分析 贪心算法贪心算法实验报告要求实验报告要求 算法上机实验报告算法上机实验报告学号姓名学号姓名 班级班级1.实验名称实验名称2.实验目的实验目的3.问题描述问题描述:4.算法描述算法描述:可用伪码描述可用伪码描述,也可用流程图也可用流程图.5.源代码：要求可读性源代码：要求可读性(有注释有注释),交互性交互性(有输入提示有输入提示)结构化程序设计风格结构化程序设计风格(分层缩进分层缩进)6.实验数据和结果实验数据和结果:要求用运行画面给出要求用运行画面给出(抓图抓图).7.算法时间复杂性分析算法时间复杂性分析:最坏时间复杂性的阶最坏时间复杂性的阶.58