《算法设计》由会员分享，可在线阅读，更多相关《算法设计（58页珍藏版）》请在金锄头文库上搜索。
1、计算机算法计算机算法设计与分析设计与分析第四章第四章 贪心算法贪心算法24.1 4.1 活动安排问题活动安排问题n n问题的提出问题的提出 n n个活动的集合个活动的集合E=1,2,E=1,2,n,n,在某一时间内要在某一时间内要 独占使用某个资源。每个活动独占使用某个资源。每个活动i i使用资源的使用资源的 起始时间为起始时间为Si Si，终止时间为，终止时间为FiFi。n n活动活动i i和活动和活动j j相容：是指相容：是指Si,Fi)Si,Fi)与与Sj,Fj)Sj,Fj)不相不相 交，即：交，即：Sj=Fi Sj=Fi 或或Si=FjSi=Fjn n要求尽可能多地安排活动。即从活动集
2、合要求尽可能多地安排活动。即从活动集合E E 中选出最大相容活动子集。中选出最大相容活动子集。3n n思路：最早结束的活动，优先安排。思路：最早结束的活动，优先安排。n n对对f1,f2,f1,f2,fn,fn从小到大排序从小到大排序 , , 时间时间O(n log n)O(n log n)n n算法：算法：n ntemplate template void greedyselector(int n,T s ,T f ,bool A )void greedyselector(int n,T s ,T f ,bool A ) A1=true; int j=1; /j A1=true; int j
3、=1; /j记录最近入选的活动记录最近入选的活动for(int i=2; i=fj) / if(si=fj) /活动活动i i和活动和活动j j相容相容Ai=true; j=i; Ai=true; j=i; else Ai=false; else Ai=false; /时间复杂性：时间复杂性：O(n) O(n) （不包括排序）（不包括排序）4算法思路将n个活动按结束时间非减序排列,依 次考虑活动i, 若i与已选择的活动相容, 则添加此 活动到相容活动子集.设待安排的11个活动起止时间按结束时间的非减序排列1 2 3 4 5 6 7 8 9 10 11 1 3 0 5 3 5 6 8 8 2 1
4、24 5 6 7 8 9 10 11 12 13 14i sifi最大相容活动子集(1, 4, 8, 11),也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1)思考如下具有11个活动安排的问题？ 1 2 3 4 5 6 7 8 9 10 11 5 0 3 5 3 1 8 6 8 12 2 9 6 5 7 8 4 11 10 12 14 135n nFjFj总是当前活动集合中结束最晚的活动总是当前活动集合中结束最晚的活动n n一旦一旦Si=FjSi=Fj，则活动，则活动i i和活动和活动j j相容，将活动相容，将活动i i加加 入入A A中，中， i i取
5、代取代j j成为最近加入的活动成为最近加入的活动n n直观上，该算法每次总是选取最早完成时间的直观上，该算法每次总是选取最早完成时间的 活动，这样就为安排其它活动留下尽可能多的活动，这样就为安排其它活动留下尽可能多的 时间，从而能安排更多的活动。时间，从而能安排更多的活动。n n证明上述贪心算法一定能得到最优解：证明上述贪心算法一定能得到最优解： 设设n n个活动已经按照结束时间的非减次序排列，个活动已经按照结束时间的非减次序排列， 集合集合E=1,2,E=1,2,n,n。 首先，活动首先，活动1 1包含在最优解中。包含在最优解中。67n n设设A A是一个最优解，且是一个最优解，且A A中活
6、动也按中活动也按FiFi递增排序递增排序 ，A A中第一个活动为中第一个活动为k k。假如。假如k 1k 1，那么构造，那么构造 B=A-kU1B=A-kU1， 由由F1 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 BinaryTreeHuffmanTree(T f, int n)/根据权f1:n构造霍夫曼树/创建一个单节点树的数组Huffman *W=newHuffman n+1；BinaryTree z,zero；f
7、or(int i=1；i Q(1)；Q.Initialize(w,n,n)；/将堆中的树不断合并Huffman x, yfor(i=1;i=0 =(f(b)-f(x)(dt(b)-dt(x)=0n n同理可证，同理可证，B(T )-B(T )=0B(T )-B(T )=0n n B(T B(T )根树及其应用w(T)= wi L(wi)1234512453 3452127设在1000个字母的文章中各字母出现的频率为:a:83, b:14, c:28, d:38, e:131, f:29, g:20, h:53.14 20 28 29 38 53 83 13134 28 29 38 53 83
8、13134 57 38 53 83 13157 72 53 83 13172 110 83 131110 155 131 155 241 3963961552411101315357728334382829142010101010101010最佳编码:a:10 ; b:1111; c:0101; d:110; e:00; f:0100; g:1110; h:0111)将权从小到大排序 2)每次选取最小权合并例 题算法设计与分析 贪心算法 哈夫曼编码284.5 4.5 单源最短路径问题单源最短路径问题有向图有向图GG的每条边都有一的每条边都有一 个非负的长度个非负的长度c ijc ij，路，路
9、径的长度即为此路径所径的长度即为此路径所 经过的边的长度之和。经过的边的长度之和。1 15 54 43 32 210301050 6010020例：具有五个顶点的有向图，各边上的数即为例：具有五个顶点的有向图，各边上的数即为 长度。对于给定源顶点长度。对于给定源顶点v1v1，需找出从它到图中，需找出从它到图中 其他任意顶点的最短路径。其他任意顶点的最短路径。29n nE. DijkstraE. Dijkstra的贪婪算法的贪婪算法n n通过分步方法求出最短路径。每一步产生通过分步方法求出最短路径。每一步产生 一个到达新的目的顶点的最短路径。一个到达新的目的顶点的最短路径。n n下一步所能达到的
10、目的顶点通过如下下一步所能达到的目的顶点通过如下贪婪贪婪 准则准则选取：在还未产生最短路径的顶点中选取：在还未产生最短路径的顶点中 ，选择路径长度最短的目的顶点。即按路，选择路径长度最短的目的顶点。即按路 径长度顺序产生最短路径。径长度顺序产生最短路径。n n最初产生从最初产生从v v 到它自身的路径，这条路径没到它自身的路径，这条路径没 有边，其长度为有边，其长度为0 0。在贪婪算法的每一步中。在贪婪算法的每一步中 ，产生下一个最短路径。，产生下一个最短路径。30n n设设u u是图中某个顶点，将从源点是图中某个顶点，将从源点v v到到u u且中间只经过且中间只经过 S S中顶点的路径称为从
11、源点中顶点的路径称为从源点v v到到u u的的特殊路径特殊路径。n n用用distudistu来记录从源点来记录从源点v v到到u u的特殊路径长度。的特殊路径长度。n n每次从每次从V-SV-S中寻找中寻找distudistu最小的最小的u u，将，将u u从从V-SV-S中去掉中去掉 ，加入，加入S S中。中。u u加入加入S S可能导致可能导致distjdistj减少，减少， ( (j jV-S)V-S) ，这是由于新增的路径这是由于新增的路径(v)(v)(u)(j)(u)(j)有可能比原路径有可能比原路径 (v)(v)(j)(j)短，故用短，故用distu+c(u,j)distu+c(
12、u,j)取代原来的取代原来的distjdistj。S Sv vu1u1u2u2V-SV-S用贪心选择来扩充集合用贪心选择来扩充集合S S 。起初，。起初，S S中仅包含源点中仅包含源点 v v。某顶点某顶点u uS S 从源点从源点 v v到到u u的最短路径已知。的最短路径已知。31算法设计与分析 贪心算法算法描述：(1) 用带权的邻接矩阵c来表示带权有向图, cij表示弧上的权值. 若 V,则置cij为设S为已知最短路径的终点的集合,它的初始状态为空集.从源点v到图上其余各点vi的当前最短路径长度的初值为：disti=cvi viV(2) 选择vj, 使得distj=Mindisti |
13、viV-Svj就是长度最短的最短路径的终点。令S=SUj(3) 修改从v到集合V-S上任一顶点vk的当前最短路径长度:如果 distj+cjk 贪心算法 单源最短路径例 题1) v1 v2: 102) v1 v3: 503) v1 v4: 304) v1 v5: 6034算法设计与分析 贪心算法voidDijkstra(int n, int v,Type dist, int prev, Type *c) bool smaxint；for (int i=1;i0dx,u0n ndv,x+dx,u 贪心算法 最小生成树问题陈述:设G(V,E)是一个无向连通带权图。E中每条边(v, w)的权 为cv
14、w,若G的一个子图G是一棵包含G的所有顶点的树，则称 G为G的生成树。生成树各边权的总和称为该生成树的耗费。在G 的所有生成树中,耗费最小的生成树称为G的最小生成树. 抽象描述: 输入:任一连通生成子图 (该子图的边集合)可行解:图的生成树, 优化函数:生成树的各边权值之和最优解:使优化函数达到最小的生成树.4.6 最小生成树39n n最小生成树性质：最小生成树性质： 设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，U U是是V V的真子集。的真子集。 若若(u,v) (u,v) E,uE,uU, vU, vV-U, V-U, 且在所有这样且在所有这样 的边中，的边中， (u,v) (u,v) 的权的权cuvcuv最小，那么一定最小，那么一定 存在存在GG的一棵最小生成树包含边的一棵最小生成树包含边(u,v)(u,v)。U V-Uu uu u v v v v40算法思路: 首先置S=1, T= .若SV, 就作
