算法设计英文版课件：Chapter 3 The GREEDY METHOD

1、Chapter 3 The GREEDY METHODThe design and Analysis of Computer AlgorithmsOutlineThe greedy method is a strategy to solve some optimization problems. It employs the following approach: In each stage, our decision is a locally-optimal one. Only a few optimization problems can be solved by this greedy

2、method.To solve some problems using this greedy method. The greedy method Suppose that a problem can be solved by a sequence of decisions. The greedy method has that each decision is locally optimal. These locally optimal solutions will finally add up to a globally optimal solution.Only a few optimi

3、zation problems can be solved by the greedy method. An simple exampleProblem: Pick k numbers out of n numbers such that the sum of these k numbers is the largest.Algorithm:FOR i = 1 to kpick out the largest number and delete this number from the input.ENDFORShortest paths on a special graphProblem:

4、Find a shortest path from v0 to v3.The greedy method can solve this problem.The shortest path: 1 + 2 + 4 = 7.Shortest paths on a multi-stage graphProblem: Find a shortest path from v0 to v3 in the multi-stage graph.Greedy method: v0v1,2v2,1v3 = 23Optimal: v0v1,1v2,2v3 = 7The greedy method does not w

5、ork.Solution of the above problem dmin(i,j): minimum distance between i and j. This problem can be solved by the dynamic programming method. Minimum spanning trees (MST) It may be defined on Euclidean space points or on a graph.G = (V, E): weighted connected undirected graph Spanning tree : S = (V,

6、T), T E, undirected treeMinimum spanning tree(MST) : a spanning tree with the smallest total weight. The vertices set of spanning tree is the same as the vertices set of Graph G!An example of MSTA graph and one of its minimum costs spanning treeKruskals algorithm for finding MSTStep 1: Sort all edge

7、s into nondecreasing order. Step 2: Add the next smallest weight edge to the forest if it will not cause a cycle.Step 3: Stop if n-1 edges. Otherwise, go to Step2.An example of Kruskals algorithm(1,2) - 10 (3,5) - 35(3,6) - 15 (2,5) - 40(4,6) - 20 (1,5) - 45(2,6) - 25 (2,3) - 50(1,4) - 30 (5,6) - 55

8、The details for constructing MSTHow do we check if a cycle is formed when a new edge is added?By the SET and UNION method.A tree in the forest is used to represent a SET.If (u, v) E and u, v are in the same set, then the addition of (u, v) will form a cycle.If (u, v) E and uS1 , vS2 , then perform U

9、NION of S1 and S2 .Time complexityTime complexity: O(|E| log|E|)Step 1: O(|E| log|E|)Step 2 & Step 3: Where is the inverse of Ackermanns function.Ackermanns function A(p, q+1) A(p, q), A(p+1, q) A(p, q)65536 twosInverse of Ackermanns function (m, n) = minZ1|A(Z,4m/n) log2n Practically, A(3,4) log2n

10、(m, n) 3 (m, n) is almost a constant.Prims algorithm for finding MSTStep 1: x V, Let A = x, B = V - x.Step 2: Select (u, v) E, u A, v B such that (u, v) has the smallest weight between A and B.Step 3: Put (u, v) in the tree. A = A v, B = B - vStep 4: If B = , stop; otherwise, go to Step 2. Time comp

11、lexity : O(n2), n = |V|. (see the example on the next page)An example for Prims algorithm(1,2) - 10 (3,5) - 35(3,6) - 15 (2,5) - 40(4,6) - 20 (1,5) - 45(2,6) - 25 (2,3) - 50(1,4) - 30 (5,6) - 55 The set A 1, 2 1, 2, 6 1, 2, 6, 3 1, 2, 6, 3, 4 1, 2, 6, 3, 4, 5An example for Prims algorithmThe set B=V

12、-A 3, 4, 5, 6 3, 4, 5 4, 5 5 The set V (Include all vertices): 1, 2, 3, 4, 5, 6Step 1Step 2Step 3Step 4Step 5V(V)Comparison of Kruskals and Prims algorithmsTo get the Minimum spanning trees (MST) using Kruskals algorithmsTo get the Minimum spanning trees (MST) using Prims algorithmsThe single-source

13、 shortest path problem shortest paths from v0 to all destinationsDirected graphTo get the shortest paths from source V0 to all destinationsDirected graphDr. Yan Dijkstras algorithmCost adjacency matrix. All entries not shown are +. Time complexity : O(n2)Can we use Dijkstras algorithm to find the lo

14、ngest path from a starting vertex to an ending vertex in an acyclic directed graph?There are 3 possible ways to apply Dijkstras algorithm:Directly use “max” operations instead of “min” operations.Convert all positive weights to be negative. Then find the shortest path.Give a very large positive numb

15、er M. If the weight of an edge is w, now M-w is used to replace w. Then find the shortest path. All these 3 possible ways would not work!The longest path problemActivity On Edge (AOE) NetworksTasks (activities) : a0, a1,Events : v0,v1,Some definition:PredecessorSuccessorImmediate predecessorImmediat

16、e successorcritical pathA critical path is a path that has the longest length. (v0, v1, v4, v7, v8)6 + 1 + 7 + 4 = 18 (Max)The earliest timeThe earliest time of an activity, ai, can occur is the length of the longest path from the start vertex v0 to ais start vertex.（Ex: the earliest time of activit

17、y a7 can occur is 7.）We denote this time as early(i) for activity ai. early(6) = early(7) = 7.The latest timeThe latest time, late(i), of activity, ai, is defined to be the latest time the activity may start without increasing the project duration.Ex: early(5) = 5 & late(5) = 8; early(7) = 7 & late(

18、7) = 7late(5) = 18 4 4 - 2 = 8late(7) = 18 4 7 = 7Critical activityA critical activity is an activity for which early(i) = late(i).The difference between late(i) and early(i) is a measure of how critical an activity is.Calculation of Earliest TimesLet activity ai is represented by edge (u, v).early

19、(i) = earliest ulate (i) = latest v duration of activity aiWe compute the times in two stages:a forward stage and a backward stage.The forward stage:Step 1: earliest 0 = 0Step 2: earliest j = max earliest i + duration of (i, j)i is in P(j)P(j) is the set of immediate predecessors of j.The backward s

20、tage:Step 1: latestn-1 = earliestn-1Step 2: latest j = min latest i - duration of (j, i) i is in S(j)S(j) is the set of vertices adjacent from vertex j.latest8 = earliest8 = 18latest6 = minearliest8 - 2 = 16latest7 = minearliest8 - 4 = 14latest4 = minearliest6 9; earliest7 7 = 7latest1 = minearliest

21、4 - 1 = 6latest2 = minearliest4 - 1 = 6latest5 = minearliest7 - 4 = 10latest3 = minearliest5 - 2 = 8latest0 = minearliest1 6; earliest2 4; earliest3 5 = 0Calculation of Latest TimesGraph with non-critical activities deletedActivityEarlyLateL - ECriticala0000Yesa1022Noa2033Noa3660Yesa4462Noa5583Noa67

22、70Yesa7770Yesa87103Noa916160Yesa1014140YesThe longest path(critical path) problem can be solved by the critical path method(CPM) :Step 1:Find a topological ordering.Step 2: Find the critical path. (see Horiwitz 1998.)CPM for the longest path problemThe 2-way merging problem # of comparisons required

23、 for the linear 2-way merge algorithm is m1+ m2 -1 where m1 and m2 are the lengths of the two sorted lists respectively.The problem: There are n sorted lists, each of length mi. What is the optimal sequence of merging process to merge these n lists into one sorted list ?Extended Binary Tree Represen

24、ting a 2-way MergeExtended binary treesAn example of 2-way merging Example: 6 sorted lists with lengths 2, 3, 5, 7, 11 and 13.Time complexity for generating an optimal extended binary tree:O(n log n)Huffman codes In telecommunication, how do we represent a set of messages, each with an access freque

25、ncy, by a sequence of 0s and 1s?To minimize the transmission and decoding costs, we may use short strings to represent more frequently used messages.This problem can be solved by using an extended binary tree which is used in the 2-way merging problem.5. Huffman codesIn principle Huffman codes can b

26、e used for a widevariety of compression tasks, but as progress has been made in the theory and practice of compression technology, newer approaches to compression have supplanted their use. However, the mathematical ideas behind Huffman codes remain as fresh and exciting as when they were first deve

27、loped. Huffman developed his ideas at MIT where he was working under the supervision of Robert Fano. Imagine that we have a text or image. For a text assume we know in advance exactly how many times each character (i.e. lower case or upper case letter, space, punctuation symbol) appears. In the case

28、 of an image, we would assume that the gray levels of the pixels in the image are all known in advance. In either case we know the relative frequencies (probabilities) of the items that we must develop a compression code for. The algorithm for constructing a Huffman code to represent items with give

29、n relative frequencies (probabilities) of occurrence proceeds in two phases. First, one constructs a Huffman tree based on the relative frequencies. Second, using the Huffman tree, one constructs the code words that go with the given relative frequencies. A simple example will illustrate the lovely

30、ideas involved.An example of Huffman algorithmSymbols: A, B, C, D, E, F, G freq. : 2, 3, 5, 8, 13, 15, 18Huffman codes:A: 10100B: 10101 C: 1011 D: 100 E: 00 F: 01G: 11Huffman codesGreedy methodInput(A1n)Solution for i 1 to n doX SELECT(A)If FEASIBLE( solution, x) then solution UNION( select, x)endif

31、repeatOutput (solution)(1)To make a group of decision(2)Every decision is only responsible for its own optimization(3) Local optimal must be global optimal(4)This process implicit some actions such as: sorting, etc. Knapsack problemGiven positive integers P1, P2, , Pn,W1, W2, , Wn and M.Find X1, X2,

32、 ,Xn, 0Xi1 such that is maximized.Subject to Knapsack Problem ExampleM = 20, (P1, P2, P3)=(25,24,15) (W1, W2, W3) = (18, 15, 10)Four feasible solutions, 4 is optimal(X1, X2, X3)WiXiPiX1.(1/2,1/3,1/4)16.524.252.(1,2/15,0)2028.23.(0, 2/3, 1)20314.(0, 1, 1/2)2031.5How to select them according to optimal value?We should calculate the profit per weight P/W!Sort them into decreasing order. P1/W11.5 P3/W3=1.5 P2/W2 P3/W3 P1/W1Job Sequencing with DeadlinesGive