《算法分析与设计8.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计8.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、陈卫东华南师范大学计算机科学系Algorithms:Design Techniques and Analysis 算法设计算法设计技巧与分析技巧与分析TheGreedyApproachTheOutlinenThebasicideaofthegreedyapproachn8.1IntroductionnApplicationsn8.2 The Shortest Path Problemn8.3 Minimum Cost Spanning Tree(Kruskals Algorithm)n8.4 Minimum Cost Spanning Tree(Prims Algorithm)n8.5 Fil
2、e Compression8.1Introduction 贪心法又叫优先策略，顾名思义就是“择优录取”，它是一种非常简单好用的求解最优化问题的方法，在好些方面的应用是非常成功的。nTheBasicIdeaofGreedyApproachn 贪心算法是根据一种贪心准则贪心准则(greedycriterion)来逐步构造问题的解的方法。在每一个阶段，都作出了相对该准则最优的决策。决策一旦作出，就不可更改。n由贪心法得到的问题的解可能是最优解，也可能只是近似解。能否产生问题的最优解需要加以证明。n所选的贪心准则不同，则得到的贪心算法不同，贪心解的质量当然也不同。因此，贪心算法的好坏关键在于正确的选择
3、贪心准则。8.1IntroductionnTheKnapsackProblem Given n items of sizes s1,s2,sn,and values v1,v2,vn and size C,the knapsack capacity,the objective is to find nonnegative real numbers x1,x2,xn that maximize the sum i=1n xivisubject to the constraint i=1n xisi C.8.1IntroductionnTheKnapsackProblemnAninstance n
4、=3,C=20,(s1,s2,s3)=(18,15,10),(v1,v2,v3)=(25,24,15).nGreedycriterionsCriterion 1根据物品的价值由大到小来放。（由例子可知，它不是最优量度标准）Criterion 2根据物品的重量由小到大来放。（由例子可知，它也不是最优量度标准）Criterion 3根据价值/重量（即单位价值）由大到小来放。（可以证明它是最优量度标准）nThe greedy algorithm based on criterion 3.1.Time complexity:O(nlogn)2.Correctness:贪心解贪心解:X=(x1,x2,x
5、k-1,xk,xk+1,xn):最优解最优解:Z=(x1,x2,xk-1,xk,zk+1,zn)最优解最优解:Y=(x1,x2,xk-1,yk,yk+1,yn)8.1Introduction8.2 The Shortest Path ProblemnThe problem Let G=be a directed graph in which each edge has a nonnegative length,and a distinguish vertex s called the source.The single-source shortest path problem,or simpl
6、y the shortest path problem,is to determine the distance from s to every other vertex in V,where the distance from vertex s to vertex x is defined as the length of a shortest path from s to x.8.2 The Shortest Path ProblemnThe greedy criterionnThe basic idea of Dijkstras algorithm(1)X1;YV-1(2)For eac
7、h vertex vY if there is an edge from 1 to v then let v(the label of v)be the length of that edge;otherwise let v=.Let 1=0.(3)while Y(4)Let yY be such that y is minimum.(5)Move y from Y to X.(6)update the labels of those vertices in Y that are adjacent to y.(7)end while.8.2 The Shortest Path Problemn
8、Dijkstras algorithmnAn Instance Fig.8.1nAlgorithm 8.1 DIJKSTRAnTime Complexity:(n2)nCorrectness Lemma 8.1 In Algorithm Dijkstra,when a vertex y is chosen in step 5,if its label y is finite then y=y,where y denotes the distance from the source vertex to y.Proof.By induction the order in which vertice
9、s leave the set Y and enter X.8.2 The Shortest Path ProblemnAn Improvement:A linear time algorithm for dense graphsnThe basic idea is to use the min-heap data structure to maintain the vertices in the set Y so that the vertex y in Y closest to a vertex in X can be extracted in O(log n)time.The key a
10、sscioated with each vertex v is its label v.nAlgorithm 8.2 SHORTESTPATHnThe time complexity:Theorem 8.2 8.3 Minimum Cost Spanning Trees (Kruskals Algorithm)nThe Problem Let G=be a connected undirected graph with weights on its edges.A spanning tree(V,T)of G is a subgraph of G that is a tree.If G is
11、weighted and the sum of the weights of the edges in T is minimum,then(V,T)is called a minimum cost spanning tree or simply a minimum spanning tree.8.3 Minimum Cost Spanning Trees (Kruskals Algorithm)nThe greedy criterionnThe basic idea of Kruskals algorithm(1)Sort the edges in G by nondecreasing wei
12、ght.(2)For each edge in the sorted list,include that edge in the spanning tree T if it does not from a cycle with the edges currently included in T;otherwise discard it.8.3 Minimum Cost Spanning Trees (Kruskals Algorithm)nKruskals algorithmnAn Instance Fig.8.4nAlgorithm 8.3 KRUSKALnTime Complexity:(
13、mlogm)nCorrectness:Lemma8.2Algorithm Kruskal correctly finds a minimum cost spanning tree in a weighted undirected graph.Proof.Prove By induction on the size of T that T is a subset of the set of edges in a minimum cost spanning tree.8.4 Minimum Cost Spanning Trees (Prims Algorithm)nThe Problem The
14、problem discussed here is the same as the one discussed above.nThe greedy criterion8.4 Minimum Cost Spanning Trees (Prims Algorithm)nThe basic idea of Prims algorithm(1)T;X1;YV-1(2)while Y(3)Let(x,y)be of minimum weight such that xX and yY.(4)XXy(5)YY-y(6)TT(x,y)(7)end while8.4 Minimum Cost Spanning
15、 Trees (Prims Algorithm)nPrims algorithmnAn Instance Fig.8.5nAlgorithm 8.4 PRIMnTime Complexity:(n2)nCorrectness:Lemma8.3 Algorithm PRIM correctly finds a minimum cost spanning tree in a connected undirected graph.Proof.Prove by induction on the size of T that(X,T)is a subtree of a minimum cost span
16、ning tree.8.4 Minimum Cost Spanning Trees (Prims Algorithm)nAn Improvement:A linear time algorithm for dense graphsnthe basic idea is to use the min-heap data structure to maintain the set of bordering vertices so that the vertex y in Y incident to an edge of lowest cost that is connected to a verte
17、x in V-Y can be extracted in O(log n)time.nAlgorithm 8.5 MSTnThe time complexity:Theorem 8.58.5 File Compression (Huffmans Algorithm)nThe Problem Let f is a file,which is a string of characters.Let the set of characters in the file be C=c1,c2,cn.Let also f(ci),1in,be the frequency of character ci in
18、 the file,i.e.,the number of times ci appears in the file.We wish to compress the file as much as possible in such a way that the original file can easily be reconstructed.8.5 File Compression (Huffmans Algorithm)nA straightforward algorithm:use a fixed number of bits to represent(encode)each charac
19、ter.nHuffmans algorithm:use a variable length encodings.Those characters with large frequencies should be assigned short encodings,whereas long encodings may be assigned to those characters with small frequencies.8.5 File Compression (Huffmans Algorithm)n实例实例 数据压缩问题数据压缩问题 假设有一个数据文件包含100 000个字符，我们要用压
20、缩的方式来存储它。该文件中各个字符出现的频率如下表所示。文件中共有6个不同字符出现，字符a出现45 000次，字符b出现13 000次等。要压缩表示这个文件中的信息有多种方法。我们考虑用0，1码串来表示字符的方法，即每个字符用唯一的一个0，1串来表示。问题要求使用二进制数字0，1码串来编码，保证编码是前缀码的前提下使得压缩文件最短。（为了使得译码容易，编码必须具有性质：任一字符的代码都不是其它字符代码的前缀。我们称这样的编码为前缀码。）8.5 File Compression (Huffmans Algorithm)abcdef频率（千次）频率（千次）4513121695定长码定长码00000
21、1010011100101变长码变长码0101100111110111008.5 File Compression (Huffmans Algorithm)若使用定长码，则表示每个不同的字符最少需要3位。用这种方法对整个文件编码需要300 000位。那么，给这个文件编码最少需要多少位呢？采用上表中的变长码给文件编码需要224 000位，它比定长码减少了约25%。事实上，这是该文件的一个最优编码方案。容易证明，任何一个前缀码都对应一棵二叉树。反之，任意一棵二叉树的树叶可对应一个前缀码。例如，表中的两个前缀码对应的二叉树为下图。显然，最优编码应该满足：出现频率高的字符应该使用较短的编码。请根据该例
22、描述构造最优前缀码的方法。8.5 File Compression (Huffmans Algorithm)a:45b:13c:12d:16e:9f:51008614582814010100001118.5 File Compression (Huffmans Algorithm)b:13c:12f:5d:16302555a:45100e:90101100011148.5 File Compression (Huffmans Algorithm)nHuffmans AlgorithmnExample 8.5nAlgorithm 8.6 HUFFMANnTime Complexity O(n log n)n CorrectnessnRelevant problem:The Optimal Mergering Problem