《第2章 贪心法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章 贪心法优秀课件.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2 章 贪心法第1 页，本讲稿共60 页第2 章 贪心法 目录 概述 会场安排问题 单源最短路径问题 哈夫曼编码 最小生成树第2 页，本讲稿共60 页第2 章 贪心法n 贪心算法总是作出在当前看来最好的选择v 并不从整体最优考虑v 局部最优选择n 不能对所有问题都得到整体最优解v 对许多问题它能产生整体最优解v 不能得到整体最优解，有时也是近似最优解。第3 页，本讲稿共60 页偷金块问题n 所有的金块大小一样，成色不一样n 背包的容积有限n 怎样偷，最划算？第4 页，本讲稿共60 页n 假设有四种硬币，它们的面值分别为：2 角5 分，1 角，5 分，1 分。现在要找给顾客6角3 分。怎样找使
2、得给顾客的硬币最少。找硬币问题第5 页，本讲稿共60 页找硬币问题要找给顾客1 角5 分，硬币的面值分别为：1角1 分，5 分和1 分。n 贪心算法：一个1 角1 分和四个1 分n 最优解：三个5 分n 不是对所有问题都能得到整体最优解第6 页，本讲稿共60 页贪心法的基本思想n 基本思想v 在每一个阶段都根据贪心策略来做出当前最优的决策，逐步降低问题的规模（难度），逐渐逼近目标。n 得出的结论v 每次面临选择时,都采用对眼前最有利的选择 v 选择一旦做出不可更改v 根据贪心策略来逐步构造问题的解 第7 页，本讲稿共60 页贪心法的基本要素n 最优子结构性质v 当一个问题的最优解一定包含其子问
3、题的最优解时 v 采用反证法证明n 贪心选择性质v 所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最优选择使得最终的选择方案是全局最优的 第8 页，本讲稿共60 页贪心法的解题步骤n 分解：将原问题分解为若干个相互独立的阶段。n 解决：对于每个阶段依据贪心策略进行贪心选择，求出局部的最优解。n 合并：将各个阶段的解合并为原问题的一个可行解。第9 页，本讲稿共60 页会场安排问题n 设有n 个会议的集合C=1,2,n，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i 都有要求使用该资源的起始时间bi和结束时间ei，且b
4、i ei。n 在所给的会议集合中选出最大的活动子集，互相不冲突。第10 页，本讲稿共60 页会场安排问题n 选择最早开始时间且不与已安排会议重叠的会议n 选择使用时间最短且不与已安排会议重叠的会议n 选择具有最早结束时间且不与已安排会议重叠的会议 第1 1 页，本讲稿共60 页设有11 个会议等待安排，11 个会议按结束时间的非减序排列表：会议i 1 2 3 4 5 6 7 8 9 10 11开始时间bi1 3 0 5 3 5 6 8 8 2 12结束时间ei4 5 6 7 8 9 10 11 12 13 14会议集合为1,4,8,11 会场安排问题第12 页，本讲稿共60 页n 步骤1：初始
5、化。n 步骤2：根据贪心策略，A1=true；n 步骤3：找到下一个与前面不冲突的会议；会场安排问题第13 页，本讲稿共60 页Void GreedySelector(int n,struct time b,struct time e,bool A)/起始时间bi，结束时间ei/e 中元素按非递减序排列，b 中对应元素做相应调整;int I,j;A1=true;/初始化选择会议的集合A，只包含会议1；j=1;i=2;/从第二(i)个会议开始寻找与会议1(j)相容的会议；while(i=ej)Ai=true;j=I;else Ai=false;会场安排问题时间复杂度：O(nlogn)空间复杂度：
6、O(1)第14 页，本讲稿共60 页n 问题存在从贪心选择开始的最优解v 贪心选择性质n 一步一步的贪心选择能够得到问题的最优解v 最优子结构性质 采用反证法会场安排问题第15 页，本讲稿共60 页n 使用贪心算法并不能保证最终的解就是最优解，但是对会场安排问题，该贪心算法却总能求得问题的最优解。n 证明贪心选择性质v 采用归纳法n 证明最优子结构性质v 采用反证法会场安排问题第16 页，本讲稿共60 页单源最短路径问题 n 给定一个有向带权图 G=(V，E)，其中每条边的权是一个非负实数。n 给定V 中的一个顶点，称为源点。n 现在要计算从源点到所有其它各个顶点的最短路径长度。第17 页，本
7、讲稿共60 页如下的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。单源最短路径问题 第18 页，本讲稿共60 页单源最短路径问题 n 按各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径的方法，即先求出长度最短的一条路径，再参照它求出长度次短的一条路径，依此类推，直到从源点到其它各个顶点的最短路径全部求出为止。第19 页，本讲稿共60 页单源最短路径问题 nu:源点。集合S 中的顶点到源点的最短路径的长度已经确定，集合V-S 中所包含的顶点到源点的最短路径的长度待定。n 特殊路径：从源点出发只经过S 中的点到达V-S 中的点的路径。n 贪心策略：选择特殊路径长度最短
8、的路径，将其相连的V-S 中的顶点加入到集合S 中。第20 页，本讲稿共60 页单源最短路径问题 S V-Sdist1dist2dist3dist4t初始 01,2,3,48 32 max max 110,12,3,4-24 23 max 320,1,3 2,4-24-30 230,1,3,24-30 440,1,3,2,4第21 页，本讲稿共60 页0 1 2 3 4初始-1 0 0-1-11-1 0 1 1-12-1 0 1 1 33-1 0 1 1 34-1 0 1 1 3前驱数组P变化情况源点0 到顶点4 的最短路径为：0，1，3，4；源点0 到顶点3 的最短路径为：0，1，3；源点0
9、 到顶点2 的最短路径为：0，1，2；源点0 到顶点1 的最短路径为：0，1。顶点迭代单源最短路径问题 第22 页，本讲稿共60 页void dijkstra(int n,int u,float dist,int p,int cnn)bool sn;/如果si 等于true，说明顶点i 已经加入集合s；/否则，顶点i 属于集合v-s for(int i=1;i=n;i+)disti=cui;si=false;/初始化源点u 到其他各个顶点的最短路径长度 if(disti=Float.Max_Value)pi=-1/说明顶点i 与源点u 不相邻 else pi=u;/说明顶点i 与源点u 相邻
10、distu=0;su=true;/初始时，集合s 中只有源点u 见下页。单源最短路径问题 第23 页，本讲稿共60 页单源最短路径问题 for(int i=1;i=n;i+)float temp=Float.Max_Value;int t=u;for(int j=1;j=n;j+)/在集合v-s 中寻找距离源点u 最近的顶点tif(!s j)&(dist jtemp)t=j;temp=dist j;if(t=u)break;/找不到t，跳出循环st=true;/否则，将t 加入集合sfor(int j=1;j=n;j+)/更新与t 相邻接的顶点到源点u 的距离if(!s j)&(ct j(di
11、stt+ct j)dist j=distt+ct j;p j=t;第24 页，本讲稿共60 页n 时间复杂性为O(n2)n 实现该算法所需的辅助空间包含为数组s 和变量i、j、t 和temp 所分配的空间v 空间复杂性为O(n)n 算法证明：证明贪心选择性质和最优子结构性质单源最短路径问题 第25 页，本讲稿共60 页哈夫曼编码n 已知某系统在通信联络中只可能出现8 种字符，分别为a，b，c，d，e，f，g，h，其使用频率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计编码。第26 页，本讲稿共60 页n 不等长编码方法：v 任何一个字符的编码都不能
12、是其它字符编码的前缀（即前缀码特性），否则译码时将产生二义性。v 约定在二叉树中用叶子结点表示字符，从根结点到叶子结点的路径中，左分支表示“0”，右分支表示“1”。那么，从根结点到叶子结点的路径分支所组成的字符串做为该叶子结点字符的编码，二叉树即为编码树。哈夫曼编码 第27 页，本讲稿共60 页n 每个字符作为一棵树，放到森林中。n 每次从树的集合中权值最小的两棵树作为左、右子树，构造一棵新树，新树根结点的权值为其左右孩子结点权之和，将新树插入到树的集合中。哈夫曼编码 第28 页，本讲稿共60 页n 步骤1：确定合适的数据结构。n 步骤2：初始化。构造n 棵结点为n 个字符的单结点树集合F=T
13、1，T2,Tn，每棵树中只有一个带权的根结点，权值为该字符的使用频率；n 步骤3：如果F 中只剩下一棵树，则哈夫曼树构造成功，转步骤6；否则，从集合F 中取出双亲为0 且权值最小的两棵树Ti 和Tj，将它们合并成一棵新树Zk，新树以Ti 为左儿子，Tj 为右儿子（反之也可以）。新树Zk 的根结点的权值为Ti 与Tj 的权值之和；n 步骤4：从集合F 中删去Ti、Tj，加入Zk；n 步骤5：重复步骤3 和4；n 步骤6：从叶子结点到根结点逆向求出每个字符的哈夫曼编码（约定左分支表示字符“0”，右分支表示字符“1”）。则从根结点到叶子结点路径上的分支字符组成的字符串即为叶子字符的哈夫曼编码。算法结
14、束。哈夫曼编码 第29 页，本讲稿共60 页哈夫曼编码n 设权w=(5，29，7，8，14，23，3，11)，n=8，按哈夫曼算法的设计步骤构造一棵哈夫曼编码树，具体过程如下：第30 页，本讲稿共60 页（1）（2）（3）（4）哈夫曼编码 第31 页，本讲稿共60 页（5）（6）（7）哈夫曼编码 第32 页，本讲稿共60 页（8）哈夫曼编码 第33 页，本讲稿共60 页n 哈夫曼树中结点的存储结构struct HtNode double weight;int parent,lchild,rchild;n 哈夫曼树的存储结构Struct HtTree struct HtNode htMaxNod
15、e;int root;Typedef struct HtTree*PHtTree;哈夫曼编码 第34 页，本讲稿共60 页PHtTree Huffman(int n,double wn)PHtTree pht;int I,j,p1,p2;double min1,min2;if(nht=(struct HtNode*)malloc();for(i=0;ihti.parent=0;if(ihti.weight=wi;else pht-hti.weight=-1;哈夫曼编码 第35 页，本讲稿共60 页.for(i=0;in-1;i+)/执行n-1 次合并操作，构造哈夫曼树中的n-1 个内部结点 p
16、1=p2=0;min1=min2=max.value;for(j=0;jhtj.parent=0)if(pht-htj.weighthtj.weight;p2=p1;p1=j;else if(pht-htj.weighthtj.weight;p2=j;pht-htp1.parent=n+I;/将htp1 和htp2 合并，其双亲是n+i pht-htp2.parent=n+I;pht-htn+i.weight=min1+min2;pht-htn+i.lchild=p1;pht-htn|i.rchild=p2;Return pht;哈夫曼编码 第36 页，本讲稿共60 页n 从叶结点逆向求出每个
17、字符的哈夫曼编码Void HuffmanCode(char*HC,int n,PHtTree pht)char cn;/每个字符的编码长度不超过n HC=(char*)malloc(n*sizeof(char*);/分配n 个字符指针空间 cn-1=0;/第n-1 个单元存储编码串的结束符 for(i=1;ihti.parent;f!=0;k=f,f=pht-htk.parent)/f 指向k 的父亲 if(pht-htf.lchild=k)c-start=0;else c-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/为每个字符编码分配空间
18、 strcpy(HCi,&cstart);/将结果拷贝到HCi 中 哈夫曼编码 第37 页，本讲稿共60 页n 证明哈夫曼算法的正确性v 贪心选择性质v 最优子结构性质哈夫曼编码 第38 页，本讲稿共60 页n 采用线性结构实现的算法，其复杂性为O(n2)。n 算法的改进：采用极小堆实现，其复杂性为O(nlogn)。哈夫曼编码 第39 页，本讲稿共60 页最小生成树n 设G=(V,E)是无向连通带权图。E中每条边(v,w)的权为cvw。n 生成树：如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。n 耗费：生成树上各边权的总和n 最小生成树在G的所有生成树中，耗费最小的生成树第40
19、 页，本讲稿共60 页最小生成树n 最小生成树应用v 在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用第41 页，本讲稿共60 页最小生成树：Prim 算法nPrim 算法v 设G=(V，E)是无向连通带权图，V=1,2,n；设最小生成树T=(U，TE)。v 令U=u0，TE=。v 选取满足条件i U，j V-U，且边(i，j)是连接U 和V-U 的所有边中的最短边，即该边的权值最小。然后，将顶点j 加入集合U，边(i，j)加入集合TE。v 继续上面的贪心选择一直进行到U=V 为止第42 页，本讲稿共60 页最小生成树：Prim 算法
20、n 实现Prim 算法的关键vclosestj 表示V-U 中的顶点j 在集合U 中的最近邻接顶点vlowcostj 表示V-U 中的顶点j 到U 中的所有顶点的最短边的权值，即边(j，closestj)的权值。第43 页，本讲稿共60 页n 步骤1：确定合适的数据结构。设置带权邻接矩阵Cnn，bool 数组s，如果si=true，说明顶点i 已加入集合U；设置两个数组closest 和lowcost；n 步骤2：初始化。令集合U=u0，TE=，并初始化数组closest、lowcost 和s；n 步骤3：在集合V-U 中寻找使得lowcost 具有最小值的顶点t，t 就是集合V-U 中连接集
21、合U 中的所有顶点中最近的邻接顶点；n 步骤4：将顶点t 加入集合U，边(t，closestt)加入集合TE；n 步骤5：如果集合V=U，算法结束，否则，转步骤6；n 步骤6：对集合V-U 中的所有顶点k，更新其lowcost 和closest，用下面的公式更新：if(Ctklowcostk)lowcostk=Ctk;closestk=t;，转步骤3。最小生成树：Prim 算法第44 页，本讲稿共60 页最小生成树：Prim 算法n 求下图的最小生成树第45 页，本讲稿共60 页n 假定初始顶点为顶点1，即U=1；t：集合V-U 中距离集合U 最近的顶点。U V-U顶点编号t2 3 4 5 6
22、closestlowcost1 2,3,4,5,61611153closestlowcost1,3 2,4,5,635-1536346closestlowcost1,3,6 2,4,535-6236-4closestlowcost1,3,4,6 2,535-36-2closestlowcost1,2,3,4,6 5-23-5closestlowcost1,2,3,4,5,6-最小生成树：Prim 算法第46 页，本讲稿共60 页（1）（2）（3）（4）（5）（6）n 构造过程最小生成树：Prim 算法第47 页，本讲稿共60 页Void Prim(int n,int u0,int cnn)bo
23、ol sn;int closestn,I,j;double lowcostn;su0=true;/初始化 for(i=0;in;i+)if(i!=u0)lowcosti=cu0i;closesti=u0;si=false;见下页。最小生成树：Prim 算法第48 页，本讲稿共60 页最小生成树：Prim 算法for(i=0;in;i+)double temp=float.MaxValue;int t=u0;for(j=0;jn;j+)/找最小的lowcostj if(!sj&(lowcostjtemp)t=j;temp=lowcostj;if(t=u0)break;st=true;/将顶点t
24、加入集合U for(j=0;jn;j+)/更新当前的lowcostj 和closestj if(!sj&(ctjlowcostj)lowcostj=ctj;closestj=t;第49 页，本讲稿共60 页最小生成树：Prim 算法n 时间复杂度：O(n2)n 复杂性与图中的边数无关nPrim 算法适合于求边稠密的网的最小生成树。第50 页，本讲稿共60 页最小生成树：Kruskal 算法n 将所有的边按权从小到大排序。n 只要T 中的连通分支数目不为1，就做如下的贪心选择：在边集E 中选取权值最小的边(i，j)，v 如果将边(i，j)加入集合TE 中不产生回路（或环），则将边(i，j)加入边
25、集TE 中，v 否则继续选择下一条最短边。n 直到T 中所有顶点都在同一个连通分支上为止。第51 页，本讲稿共60 页最小生成树：Kruskal 算法n 回路判断：v 如果所选择加入的边的起点和终点都在T的集合里，那么就可以断定一定会形成回路。第52 页，本讲稿共60 页算法设计求解步骤n 步骤1：初始化。将图G 的边集E 中的所有边按权从小到大排序，边集TE=，把每个顶点都初始化为一个孤立的分支，即一个顶点对应一个集合；n 步骤2：在E 中寻找权值最小的边(i，j)；n 步骤3：如果顶点i 和j 位于两个不同连通分支，则将边(i，j)加入边集TE，并执合并操作将两个连通分支进行合并；n 步骤
26、4：将边(i，j)从集合E 中删去，即E=E-(i，j)；n 步骤5：如果连通分支数目不为1，转步骤2；否则，算法结束，生成最小生成树T。第53 页，本讲稿共60 页构造实例图2-12 所示n 首先，将图的边集E 中的所有边按权从小到大排序为：1(1，3)、2(4，6)、3(2，5)、4(3，6)、5(1，4)和(2，3)和(3，4)、6(1，2)和(3，5)和(5，6)。（1）（2）（3）（4）（5）第54 页，本讲稿共60 页算法描述边的结点信息存储结构：Struct edge double weight;int u,v;bian;Void Kruskal(int n,struct edg
27、e bian,double cnn)int nodesetn,count=1;bool flagn+1;if(n=1)return;for(int i=1;i=n;i+)nodeseti=I;flagi=false;for(int j=1;j=n;j+)biancount.u=I;biancount.v=j;biancount.weight=cij;count+;sort(bian+1,bian+count);第55 页，本讲稿共60 页算法描述Count=1;int edgeset=0,w=0;While(edgeset(n-1)if(!flagbiancount.u)&(flagbianc
28、ount.v)w+=biancount.weight;edgeset+;flagbiancount.u=true;nodesetbiancount.u=nodesetbiancount.v;else if(flagbiancount.u)&(!flagbiancount.v)w+=biancount.weight;edgeset+;flagbiancount.v=true;nodesetbiancount.v=nodesetbiancount.u;else if(!flagbiancount.u)&(!flagbiancount.v)w+=biancount.weight;edgeset+;f
29、lagbiancount.u=true;flagbiancount.v=true;nodesetbiancount.u=nodesetbiancount.v;else if(nodesetbiancount.u!=nodesetbiancount.v)w+=biancount.weight;edgeset+;int tmp=nodesetbiancount.v;for(int i=1;i=n;i+)if(nodeseti=tmp)nodeseti=nodesetbiancount.u;count+;/end-while/end-Kruskal第56 页，本讲稿共60 页算法描述及分析n 从算法
30、的基本思想和设计步骤可以看出，要实现Kruskal 算法必须解决以下两个关键问题：（1）选取权值最小的边的同时，要判断加入该条边后树中是否出现回路；（2）不同的连通分支如何进行合并。n 为了便于解决这两大问题，必须了解每条边的信息。那么，在Kruskal算法中所设计的每条边的结点信息存储结构如下：n struct edgen double weight;/边的权值n int u，v;/u 为边的起点，v 为边的终点。n bian;n sort 函数耗时最大，为此算法的时间复杂性为O(eloge)。第57 页，本讲稿共60 页Prim 和Kruskal 算法的比较n 如果图G 中的边数较小时，可以采用KruskalnKruskal 适用于稀疏图，而Prim 适用于稠密图。nPrim 算法的时间复杂度为O(n2)nKruskal 算法的时间复杂度为O(eloge)n 对于很大的图而言，Kruskal 算法需要占用比Prim 算法大得多的空间。第58 页，本讲稿共60 页贪心总结算法n 贪心算法是一个简单而高效的算法n 可以用贪心算法求解的问题必须满足两个性质：贪心选择性质和最优子结构性质n 贪心算法的时间复杂度大多数情况是排序的复杂度第59 页，本讲稿共60 页作业nP60 2-4、2-5第60 页，本讲稿共60 页