陈卫东chenwdscnu.edu.cn华南师范大学计算机科学系,Algorithms :Design Techniques and Analysis 算法设计技巧与分析,The Greedy Approach,The OutlineThe basic idea of the greedy approach8.1 IntroductionApplications8.2 The Shortest Path Problem8.3 Minimum Cost Spanning Tree(Kruskals Algorithm)8.4 Minimum Cost Spanning Tree(Prims Algorithm)8.5 File Compression,8.1 Introduction,贪心法又叫优先策略，顾名思义就是“择优录取”，它是一种非常简单好用的求解最优化问题的方法，在好些方面的应用是非常成功的。The Basic Idea of Greedy Approach 贪心算法是根据一种贪心准则(greedy criterion)来逐步构造问题的解的方法。在每一个阶段，都作出了相对该准则最优的决策。决策一旦作出，就不可更改。由贪心法得到的问题的解可能是最优解，也可能只是近似解。能否产生问题的最优解需要加以证明。所选的贪心准则不同，则得到的贪心算法不同，贪心解的质量当然也不同。因此，贪心算法的好坏关键在于正确的选择贪心准则。,8.1 Introduction,The Knapsack Problem 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.1 Introduction,The Knapsack ProblemAn instance n=3, C=20, (s1,s2,s3)=(18,15,10), (v1,v2,v3)=(25,24,15). Greedy criterionsCriterion 1根据物品的价值由大到小来放。 （由例子可知，它不是最优量度标准）Criterion 2根据物品的重量由小到大来放。 （由例子可知，它也不是最优量度标准）Criterion 3根据价值/重量（即单位价值）由大到小来放。 （可以证明它是最优量度标准）,The greedy algorithm based on criterion 3. 1. Time complexity: O(nlogn) 2. Correctness: 贪心解: X=(x1, x2, xk-1, xk, xk+1, , xn) : : : : 最优解: Z=(x1, x2, xk-1, xk, zk+1, , zn) 最优解: Y=(x1, x2, xk-1, yk, yk+1, , yn),8.1 Introduction,8.2 The Shortest Path Problem,The 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 simply 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 Problem,The greedy criterionThe basic idea of Dijkstras algorithm(1) X1;YV-1(2) For each 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 Problem,Dijkstras algorithmAn Instance Fig.8.1Algorithm 8.1 DIJKSTRATime Complexity: (n2)Correctness 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 vertices leave the set Y and enter X.,8.2 The Shortest Path Problem,An Improvement: A linear time algorithm for dense graphsThe 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 asscioated with each vertex v is its label v.Algorithm 8.2 SHORTESTPATHThe time complexity: Theorem 8.2,8.3 Minimum Cost Spanning Trees (Kruskals Algorithm),The 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 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),The greedy criterionThe basic idea of Kruskals algorithm(1) Sort the edges in G by nondecreasing weight.(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),Kruskals algorithmAn Instance Fig.8.4Algorithm 8.3 KRUSKALTime Complexity: (mlogm)Correctness: 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),The Problem The problem discussed here is the same as the one discussed above.The greedy criterion,8.4 Minimum Cost Spanning Trees (Prims Algorithm),The 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 while,8.4 Minimum Cost Spanning Trees (Prims Algorithm),Prims algorithmAn Instance Fig.8.5Algorithm 8.4 PRIMTime Complexity: (n2)Correctness: 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 spanning tree.,