《算法设计技巧与分析课件(英文版)：ch8 The greedy approach》由会员分享，可在线阅读，更多相关《算法设计技巧与分析课件(英文版)：ch8 The greedy approach（51页珍藏版）》请在金锄头文库上搜索。
1、Algorithms Design Techniques and AnalysisChapter 8The greedy approach An efficient approach for optimization problemsAlgorithms Design Techniques and AnalysisWhat we have known after previous learningDynamic programming and its general diagramOptimal substructureThe longest common subsequence proble
2、mMatrix chain multiplicationThe all-pairs shortest path problemThe knapsack problemAlgorithms Design Techniques and AnalysisContents of current chapter Introduction of the Greedy ApproachThe shortest path problemMinimum cost spanning treesKruskals AlgorithmPrims AlgorithmFile compressionAlgorithms D
3、esign Techniques and Analysis8.1 IntroductionCompared with the Dynamic Programming Algorithms:Greedy algorithms are designed to solve optimization problems in which a quantity is to be minimized or maximized, too.But Greedy algorithms typically consist of an iterative procedure that tries to find a
4、local optimal solution. In some instances, these local optimal solutions translate to global optimal solutions. In others, they fail to give optimal solutions. Algorithms Design Techniques and AnalysisBasic ideaA greedy algorithm makes a correct guess on the basis of little calculation without worry
5、ing about the future. It builds a solution step by step. Each step increases the size of the partial solution and is based on local optimization.The choice made is that which produces the largest immediate gain while maintaining feasibility. Since each step consists of little work based on a small a
6、mount of information, the resulting algorithms are typically efficient. Algorithms Design Techniques and AnalysisAn example: Fractional Knapsack Problem Problem description: Given n items of sizes s1, s2,. , sn, and values v1 ,v2,.,vn and size C, the knapsack capacity, the objective is to find nonne
7、gative real numbers x1,x2,xn that maximize the sum Subject to the constraintAlgorithms Design Techniques and AnalysisExamplen=3, C=20, (v1,v2,v3)=(25,24,15),(s1,s2,s3)=(18,15,10)Feasible solutions: (x1,x2,x3)sixi vixi(1)(1/2,1/3,1/4)16.524.5 (2)(1,2/15,0)2028.2(3)(0,2/3,1)2031(4)(0,1,1/2)2031.5Algor
8、ithms Design Techniques and AnalysisSelection strategy-1Choose the one with the maximal value from the remain items into the knapsack.Solution (2)(1,2/15,0)2028.2 (sub-optimal)reason：the consumption rate of capacity of knapsack is too fast.Algorithms Design Techniques and AnalysisSelection strategy-
9、2Choose the one with the minimal size from the remain items into the knapsack.Solution(3) (0,2/3,1)2031 (sub-optimal)reason：the value increase slowly though the consumption rate of capacity of knapsack becomes slow.Algorithms Design Techniques and AnalysisSelection strategy- 3Choose the one with the
10、 maximal ratio vi/si from the remain items into the knapsack.Solution (4) (0,1,1/2)2031.5 (optimal)Algorithms Design Techniques and AnalysisGreedy algorithm to solve KnapsackStep 1:For each item compute yi=vi/si, the ratio of its value to its size. Step 2: Sort the items by decreasing ratio, and fil
11、l the knapsack with as much as possible from the first item, then the second, and so forth. Algorithms Design Techniques and AnalysisAlgorithm Greedy-KNAPSACKInput: size vector s1.n and value vector v1.n of n items that are both sorted as non-increasing order according to the ratio v(i)/s(i); the ca
12、pacity C of the knapsack, the total number of items nOutput: the greedy optimal solution x1.n for i 0 to n xi 0end forcu Cfor i 0 to n if si cu then exit end if x(i) 1 cu cu-s(i)end forif i n then x(i) cu/s(i) end ifreturn xAlgorithms Design Techniques and AnalysisDiagram of greedy algorithmAlgorith
13、m GREEDY(A,n)solutionfor i1 to n doxSELECT(A)if FEASIBLE(solution,x)then solutionUNION(solution,x)end ifend forreturn (solution)Algorithms Design Techniques and AnalysisCharacteristics of a greedy algorithmThe algorithm consists of a simple iterative procedure that selects that item which produces t
14、he largest immediate gain while maintaining feasibility.The selection strategy is the most important for a greedy algorithm to generate the global optimal solution.Algorithms Design Techniques and Analysis8.2 The Shortest Path Problem Problem description:Let G = (V, E) be a directed graph in which e
15、ach edge has a nonnegative length, and a distinguished 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 t is defined as the length of a
16、shortest path from s to t. Algorithms Design Techniques and AnalysisDijkstras Algorithm Basic idea Greedy Criterion: Select the path in nonincreasing order.For simplicity, assume that V=1,2,n, s=1.Initially, the set of vertices is partitioned into two sets X = 1 and Y = 2,3,.,n. The intention is tha
17、t X contains the set of vertices whose distance from the source has already been determined. At each step, we select a vertex y Y whose distance from the source vertex has already been found and move it to X. Associated with each vertex y in Y is a label y, which is the length of a shortest path tha
18、t passes only through vertices in X. Once a vertex y Y is moved to X, the label of each vertex w Y that is adjacent to y is updated indicating that a shorter path to w via y has been discovered.Algorithms Design Techniques and AnalysisAlgorithm 8.1 DIJKSTRA Input: A weighted directed graph G=(V,E),
19、where V=1,2,n.Output: The distance from vertex 1 to every other vertex in G.1. X=1; YV-1; 102. for y2 to n3. if y is adjacent to 1 then ylength1,y4.else y 5.end if6.end for7.for j1 to n-18. Let y Y be such that y is minimum9.XX y add vertex y to X10.YY-y delete vertex y form Y11.for each edge (y,w)1
20、2.if w Y and y+lengthy,w w then13. w y+lengthy,w14.end for15. end forAlgorithms Design Techniques and AnalysisAn example 261534112531549413X11,21,2,41,2,4,31,2,4,3,51,2,4,3,5,6Y34561221356104456171938619513617Success!Algorithms Design Techniques and AnalysisData structure123456T FFFFF123456F TTTTT12
21、3456213 123943553451361564X:Y:Algorithms Design Techniques and AnalysisCorrectnessLemma 8.1:In Algorithm DIJKSTRA, when a vertex y is chosen in Step 8, if its label y is finite then y = y. (y denotes the distance from the source vertex to y)ProofBy induction on the order in which vertices leave the
22、set Y and enter X. The first vertex to leave is 1 and we have 1=1=0. Assume that the statement is true for all vertices which left Y before y.Since y is finite, there must exists a path from 1 to y whose length is y. Let =1,x,w,y be a shortest path from 1 to y, where x is the rightmost vertex to lea
23、ve Y before y. We have y w x+length(x,w)=x+length(x,w)= w y. The above proof is based on the assumption that all edge lengths are nonnegetive.Algorithms Design Techniques and AnalysisAlgorithm analysisStep 1: (n) time. Steps 3 and 4: (n) and O(n,), respectively. Step 8: (n2). Steps 9 and 10: cost (1
24、) time per iteration for a total of (n) time. Steps 11 and 12 is (m). Where m=|E|.The time complexity of the algorithm is (m+n2) = (n2). Theorem 8.1 Given a directed graph G with nonnegative weights on its edges and a source vertex s, Algorithm DIJKSTRA finds the length of the distance from s to eve
25、ry vertex in (n2).Algorithms Design Techniques and Analysis8.2.1 A linear time algorithm for dense graphsBasic idea: 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 V-Y can be extracted in O(log n) time. The key associated with e
26、ach vertex v is its label v. The final algorithm is shown as Algorithm SHORTESTPATH.Algorithms Design Techniques and AnalysisAlgorithm 8.2 SHORTESTPATHInput: A weighted directed graph G=(V,E), where V=1,2,.,n.Output: The distance from vertex 1 to every other vertex in G. Assume that we have an empty
27、 heap H at the beginning.1.YV-1; 10; key(1) 12.for y2 to n3.if y is adjacent to 1 then4. y=length1,y5. key(y) y6. INSERT(H,y)7.else8. y 9. keyy y10.end if 11. end for NEXT PAGEAlgorithms Design Techniques and AnalysisAlgorithm 8.2 SHORTESTPATH 12. for j1 to n-113.yDELETEMIN(H)14.YY-y15.for each vert
28、ex w Y that is adjacent to y16. if y+lengthy,w0, then it can be further improved to run in time O(m/).Algorithms Design Techniques and Analysis8.3 Minimum Cost Spanning Trees (Kruskals Algorithm) Definition 8.1:Let g = (V, E) be a connected undirected graph with weights on its edges. A spanning tree
29、 (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. Problem descriptionAssume G is connected, how to find the minimum spanning tree (MST)?Algorith
30、ms Design Techniques and AnalysisKruskals algorithm basic ideaIt works by maintaining a forest consisting of several spanning trees that are gradually merged until finally the forest consists of exactly one tree: a minimum cost spanning tree. Step 1: sorting the edges in nondecreasing order by weigh
31、t.Step 2: starting from the forest (V,T) consisting of the vertices of the graph and none of its edges, the following step is repeated until (V,T) is transformed into a tree:Let (V,T) be the forest constructed so far, and let eE-T be the current edge being considered. If adding e to T does not creat
32、e a cycle, then include e in T, otherwise discard e.This process will terminate after adding exactly n-1 edges. Algorithms Design Techniques and AnalysisAn example61235412131139746(1,2)(1,3)(4,6)(5,6)(2,3)(4,5)(3,4)(2,4)(3,5)12346791113612354!Form a circle, the edge is discarded.Success!Algorithms D
33、esign Techniques and AnalysisImplementation of Kruskals algorithmData structure to represent the forest:A suitable choice of such data structure is the disjoint sets representation. In the beginning, each vertex of the graph is represented by a tree consisting of one vertex. During the execution of
34、the algorithm each connected component of the forest is represented by a tree. Algorithms Design Techniques and AnalysisAlgorithm 8.3 KRUSKALInput: A weighted connected undirected graph G=(V,E) with n vertices.Output: The set of edges T of a minimum cost spanning tree for G.1.Sort the edges in E by
35、nondecreasing weight2.for each vertex vV3.MAKESETv4.end for5.T=6.while |T|n-17.Let (x,y) be the next edge in E.8.if FIND(x) FIND(y) then9. Add(x,y) to T10 UNION(x,y)11end if12. end whileAlgorithms Design Techniques and AnalysisCorrectnessLemma 8.2: Algorithm KRUSKAL correctly finds a minimum cost sp
36、anning tree in a weighted undirected graph.Proof P241(or P153)Algorithms Design Techniques and AnalysisAlgorithm analysisSteps 1 and 3 cost O(mlogm) and (n), respectively where m = |E|. Step 7 is executed exactly n-1 times for a total of O(n) time. Step 9 costs (1), and since it is executed at most
37、m times, its total cost is O(m).The union operation is executed n-1 times, and the find operation at most 2m times. The overall cost of these two operations is O(mlog*n).Thus, the overall running time of the algorithm is dominated by the sorting step, 1.e., O(mlogm).Algorithms Design Techniques and
38、Analysis8.4 Minimum cost spanning trees (Prims Algorithm)Basic ideaLet G=(V,E), where for simplicity V is taken to be the set of integers 1,2,n. The algorithm begins by creating two sets of vertices: X=1 and Y=2,n. It then grows a spanning tree, one edge at a time.At each step, it finds an edge (x,y
39、) of minimum weight, where xX and y Y and moves y from Y toX. This step is repeated until Y becomes empty.Algorithms Design Techniques and AnalysisPrims AlgorithmThe algorithm is summarized below1.T; X1; YV-12.while Y 3. Let (x,y) be of minimum weight such that xX and yY4. XXy5. YY-y6. TT(x,y)7.end
40、while Algorithms Design Techniques and AnalysisAn example61235412131139746Success!Algorithms Design Techniques and AnalysisAlgorithm 8.4 PRIMInput: A weighted connected undirected graph G=(V,E), where V=1,2,.,n.Output: The set of edges T of a minimum cost spanning tree for G.1.T; X1; YV-12.for y2 to
41、 n3.if y adjacent to 1 then4.Ny15.Cyc1,y6.else Cy7.end if 8.end for NEXT PAGEAlgorithms Design Techniques and AnalysisAlgorithm 8.4 PRIM9. for j1 to n-1 find n-1 edges10. Let yY be such that Cy is minimum11.TTy,Ny add edge (y,Ny) to T12.XXy add vertex y to X13. YY-y delete vertex y from Y14. for eac
42、h vertex w Y that is adjacent to y15. if cy,wCw then16. Nwy17. Cwcy,w18. end if19. end for20. end for Algorithms Design Techniques and AnalysisCorrectnessLemma 8.3 Algorithm Prim correctly finds a minimum cost spanning tree in a connected undirected graph.Proof: P245Algorithms Design Techniques and
43、AnalysisAlgorithm analysisStep 1 costs (n) time. The for loop in step 2 costs (n) time. The time taken by step 3-6 is O(n). The time taken by step 10 is (n) per iteration. Since this step is executed n-1 times, so the overall time taken by step 10 is (n2) time. The for loop in step 14 is executed 2m
44、 times. Thus the time complexity of the algorithm is (m+n2) time. Algorithms Design Techniques and Analysis8.4.1 A linear time algorithm for dense graphsBasic ideaNow we improve on Algorithm PRIM in order to lower its (n2) time complexity to O(mlogn) for graphs in which m= o(n2). We will also improv
45、e it further, so that in the case of dense graphs it runs in time linear in the number of edges.As in Algorithm SHORTESTPATH, the basic idea is to use the min-heap data structure to maintain the set of bordering vertices so that vertex y in Y incident to an edge of lowest cost that is connected to a
46、 vertex in V-Y can be extracted in O(logn) time.Algorithms Design Techniques and AnalysisAlgorithm 8.5 MSTInput: A weighted connected undirected graph G=(V,E), where V=1,2,.,n.Output: The set of edges T of a minimum cost spanning tree for G. Assume that we have an empty heap H at the beginning.1.T;
47、YV-12.for y2 to n3. if y is adjacent to 1 then4.Ny15.key(y)c1,y6.INSERT(H,y)7. else key(y)8. end if9. end for NEXT PAGEAlgorithms Design Techniques and Analysis Algorithm 8.5 MST 10. for j1 to n-1 find n-1 edges11. yDELETEMIN(H)12. TT(y,N|y|) add edge (y,N|y|) to T13. YY-y delete vertex y from Y14.
48、for each vertex w Y that is adjacent to y15. if cy,w0, then it can be improved further to run in time O(m/) .Algorithms Design Techniques and Analysis8.5 File Compression Problem description: Suppose we are given a file, which is a string of characters. We wish to compress the file as much as possib
49、le in such a way that the original file can easily be reconstructed. Let the set of characters in the file be C = c1,c2,.,cn. Let also f(ci),1 i n, be the frequency of character ci in the file, i.e., the number of times ci appears in the file. Using a fixed number of bits to represent each character
50、, called the encoding of the character, the size of the file depends only on the number of characters in the file.Algorithms Design Techniques and AnalysisVariable length encodingSince the frequency of some characters may be much larger than others, it is reasonable to use variable length encodings.
51、 Intuitively, those characters with large frequencies should be assigned short encodings, whereas long encodings may be assigned to those characters with small frequencies, When the encodings vary in length, we stipulate that the encoding of one character must not be the prefix of the encoding of an
52、other character; such codes are called prefix codes. For instance, if we assign the encodings 10 and 101 to the letters “a”, and “b”, there will be an ambiguity as to whether 10 is the encoding of “a” or is the prefix of the encoding of the letter “b”.Algorithms Design Techniques and AnalysisHuffman
53、 codeOnce the prefix constraint is satisfied, the decoding becomes unambiguous; the sequence of bits is scanned until an encoding of some character is found. One way to parse a given sequence of bits is to use a full binary tree, in which each internal node has exactly two branches labeled by 0 and
54、1. The leaves in this tree correspond to the characters. Each sequence of 0s and 1s on a path from the root to a leaf corresponds to a character encoding.Huffman Code: constructed by Huffman algorithm, satisfies the prefix constraint and minimizes the size of the compressed file.Algorithms Design Te
55、chniques and AnalysisAn exampleGiven a file consists of the letters a,b,c,d and e, the frequencies is 7592138111820104eacbd4231001001Algorithms Design Techniques and AnalysisAlgorithm 8.6 HUFFMANInput: A set C=c1,c2,cn of n characters and their frequenciesf(c1),f(c2),f(cn).Output: A Huffman tree (V,
56、T) for C.1.Insert all characters into a min-heap H according to their frequencies.2. VC; T=3. for j1 to n-14.cDELETEMIN(H)5.cDELETEMIN(H)6.f(v)f(c)+f(c) v is a new node7.INSERT(H,v)8.V=V v Add v to V9.T=T (v,c),(v,c) Make c and c children of v in T 10. end forAlgorithms Design Techniques and Analysi
57、sAlgorithm analysisThe time needed to insert all characters into the heap is (n)The time required to delete two elements from the heap and add a new element is O(log n)Since this is repeated n-1 times, the overall time taken by the for loop is O(nlogn)It follows that the time complexity of the algor
58、ithm is O(nlogn).Algorithms Design Techniques and AnalysisConclusion Greedy algorithms are designed to solve optimization problems in which a quantity is to be minimized or maximized:The single-source shortest path problemMinimum cost spanning trees and Huffman codesAlgorithms Design Techniques and AnalysisExercises8.168.238.31Implement 8.34
