算法设计与分析双语课Chapter 5 -1Gready algorithm

1、 算法设计与分析North China Electric Power University Algorithms Design & Analysis华北电力大学计算机科学与技术学院School of Computer Science&Technology of North China Electric Power UniversityNorth China Electric Power UniversityChapter 5 Greedy Algorithm 1. Introduction 2. Fractional knapsack problem 3. The shortest path

2、problem 4. Minimum spanning trees problem 5. 找钱问题 6. 汽车加油问题 7. An activity-selection problemNorth China Electric Power University1 Introduction Typically, in optimization problems the algorithm needs to make a series of choices whose overall effect is to minimize the total cost, or maximize the tota

3、l benefit, of some system. The greedy method consists of making the choices in sequence such that each individual choice is best according to some limited “short-term” criterion that is not too expensive to evaluate. Once a choice is made, it cant be undown , even if it becomes evident later that it

4、 was a poor choice. For this reason, greedy algorithm dont necessarily find the exact optimum solution for many problems. Unlike dynamic programming algorithms, greedy algorithms typically consist of an iterative procedure that tries to find a local optimal solution. A greedy algorithm makes a corre

5、ct guess on the basis of little calculation without worrying about the future. Thus 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 feasibil

6、ity. North China Electric Power University Since each step consists of little work based on a small amount of information, the resulting algorithms are typically efficient. The hard part in the design of a greedy algorithm is proving that the algorithm does indeed solve the problem it is designed fo

7、r. This is contrasted with recursive algorithms that have simple inductive proofs. How can one tell if a greedy algorithm will solve aparticular optimization problem? There is no way in general. If we can demonstrate the following properties, then itis probable to use greedy algorithm:When greedy al

8、gorithm works?North China Electric Power University1. Greedy-choice Property2. Optimal Substructure (the same with that of dynamic programming) propertyGreedy choice property A global optimal solution can be arrived at by making a locally optimal greedy choice. That is, when we are considering which

9、 choice to make, we make the choice that looks best in the current problem, we make the choice that looks best in the current problem, without considering result from subproblems.Note: Greedy algorithm is a special dynamic programming.North China Electric Power UniversitySteps of Greedy Algorithm1.

10、Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.North China Electric Power University2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.3. Demonstrat

11、e that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem.2 Fractional knapsack problem Given n items of sizes s1 ,s2 ,sn

12、, 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 sumNorth China Electric Power Universitysubject to the constraint North China Electric Power UniversityThe optimal substructure property: If we remove a size s of

13、 one item j from the optimal load, then the remaining load must be the most valuable load sizing with most C-s that the knapsack has from the n-1 original items plus sj - s pounds of item j. This problem can easily be solved using the following greedy strategy. For each item compute yi=vi/si, the ra

14、tio of its value to its size. Sort the items by decreasing ratio, and fill the knapsack with as much as possible from the first item, then second, and so forth. North China Electric Power UniversityThe algorithm：procedure greedy_knapsack(s,v,x:array of real,n:integer;C:real);s1.n and v1.n has been s

15、orted such that si/vi=si+1/vi+1 Begin for i:=1 to n do xi:=0; cu:=C; i:=1; while (i=n) and (si=cu) do xi:=1; cu:=cu-si; i:=i+1; if (i0,wi0,pi0; 1in xi 0,1 ni=1ni=1Knapsack problem model：Object function ：max pixiConstraint : wixiC； C0,wi0,pi0; 1in 0 xi1ni=1ni=1North China Electric Power UniversityBot

16、h knapsack problems exhibit the optimal substructure property:1. For 0-1 knapsack problem, if we remove item j from this load, the remaining load must be at most valuable items weighing at most C-wj from n - 1 items.2. For fractional one, if we remove a weight w of one item j from the optimal load,

17、then the remaining load must be the most valuable load weighing at most C-w that the thief can take from the n-1 original items plus wj - w pounds of item j.North China Electric Power UniversityNorth China Electric Power University例： Knapsack problem，n=3,C=40, (w1,w2,w3)=(28,15,24), (p1,p2,p3)= (35,

18、25,24) . There are 5 feasible solutions as follow:(x1,x2,x3) wixi pixini=1ni=1 (1,4/5,0) 40 55 (1/2,1,1/3) 37 50.5 (1/28,1,1) 40 50.254) (5/7,1,5/24) 40 555) (25/28,1,0) 40 56.253 greedy methods:1）choose the most valuable item every time: (x1,x2,x3)=(1,4/5,0) total value：552）choose the lowest weight

19、 item every time: (x1,x2,x3 )=(1/28,1,1) total value ：50.25 3）choose the most valuable item in a unit weight every time: （x1,x2,x3)=(25/28,1,0) total value：56.25North China Electric Power University3 The shortest path problem Let G=(V,E) be a directed graph in which each edge has a nonnegative lengt

20、h, 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 form vertex s to vertex x is defined as the length of a shortest path from s to x. For s

21、implicity, we will assume that V=1,2,n and s=1. This problem can be solved using a greedy technique known as Dijkstras algorithm. Initially, the set of vertices is partitioned into two sets X=1 and Y=2,3,n. The intention is that X contains the set of vertices whose distance from the source has been

22、de determined.North China Electric Power University At each step, we select a vertex whose distance form the source vertex has been found and move it to X. Associated with each vertex y in Y is a label , which is the length of a shortest path that passes only through vertices in X. Once a vertex is

23、moved to , the label of each vertex that is adjacent to y is updated indicating that a shorter path to w via y has been discovered. Throughout this section, for any vertex , will denote the distance form the source vertex to v . As will be shown later, at the end of the algorithm, for each vertex .

24、A sketch of the algorithm is given below.North China Electric Power UniversityX1; YV-1;for y 2 to n if y is adjacent to 1 then else end for for j 1 to n-1 let be such that is minimum for each edge (y,w) if and then end for end for ExampleNorth China Electric Power University12345611293544151301 12 (

25、a)12345611293544151301 10 (b)123456112935441513014 12 (c)123456112935441513014 17 13 8 (e)123456112935441513014 17 13 8 (f)123456112935441513014 19 13 8 (d)111241219138North China Electric Power UniversityCorrectnessLemma: In algorithm Dijkstra, when a vertex y is chosen in step 8, if its label is f

26、inite then X1xwyProof By induction on the orders in which vertices leave the set Y and enter X. The first vertex to leave is 1 and we have .Assume that the statement is true for all vertices which left Y before y. Since is finite, there must exists a path from 1 to y whose length is . Now, we show t

27、hat .Let be a shortest path from 1 to y , where x is the rightmost vertex to leave Y before y. We haveTheorem Given a directed graph with nonnegative weights on its edges and a source vertex s, Algorithm Dijkstra finds the length of the distance from s to every other vertex in (n2) time.North China

28、Electric Power University4 Minimum cost spanning trees problemDefinition: Let G=(V,E) be a connected undirected graph with weights on its edges. A spanning tree (V,T) of G is a tree which contains all the vertices of G. If the sum of the weights of the edges in T is minimum, then (V,T) is called a m

29、inimum cost spanning tree or simply a minimum spanning tree. There are many situations in which minimum spanning tress must be found. Whenever one wants to find the cheapest way to connect a set of terminals, be the cities, electrical terminals computers or factories by using , say, roads, wires, or

30、 telephone lines , a solution is a minimum spanning tree for the graph with an edge for each possible connection weighted by the cost of that connection.North China Electric Power UniversityKruskals Algorithm The algorithm starts by sorting the edges in nondecreasing order by weight. Next, starting

31、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 be the current edge being considered. If adding e to T does not create a cycle, then include

32、 e in T; otherwise discard e. This process will terminate after adding exactly n-1 edges .North China Electric Power UniversityNorth China Electric Power UniversityExample1234561 269437(f)1234561(b)1234561(c) 21234561 243(e)1234561 2(d)31234561 2611139437(a)North China Electric Power UniversityAlgor

33、ithmsorting the edges in nondecreasing order by weight. for each edge V Makeset ( ) end forT=while Tn-1 let (x, y) be the next edge of E if find(x)find(y) then adding (x, y) to T UNION(x, y) end ifend whileCorrectness We prove by induction on the size of T that T is a subset of the set of edges in a

34、 minimum cost spanning tree. Initially, T= and the statement is trivially true. For the induction step, assume before adding the edge e=(x,y) that , where T* is the set of edges in a minimum cost spanning tree G*=(V, T*) . Let X be the set of vertices in the subtree containing x. Let , We will show

35、that T is also a subset of the set of edges in a minimum cost tree. By the induction hypothesis, . If T* contains e, then there is nothing to prove. Otherwise, contains exactly one circle with e being one of its edges. Since e=(x,y) connects one vertex in X to another vertex in V-X, T* must also con

36、tain another edge e=(w,z) such that and . North China Electric Power University We observe that cost(e) cost(e); for otherwise e would have been added before since it does not create a cycle with the edges of T* which contains the edges of T. If we now construct , we notice that . Moreover, T* is th

37、e set of edges in a minimum cost spanning tree since e is of minimum cost among all edges connecting the vertices X with those in V-X.North China Electric Power UniversityPrims Algorithm The algorithm grows the spanning tree starting from an arbitrary vertex. Let G=(V,E) , where for simplicity V is

38、taken to be the set of integers 1,2,n. The algorithm begins by creating two set of vertices: X=1 and Y=2,3,n. Then, it grows a spanning tree, one edge at a time. At each step, it finds an edge (x,y) of minimum weight, where and and moves y from Y to X . This edge is added to the current minimum span

39、ning tree edges in T. This step is repeated until Y becomes empty. The algorithm is outlined below. It finds the set of edges T of a minimum cost spanning tree.North China Electric Power UniversityExampleNorth China Electric Power University1234561 2611139437(a)1234561 2611139437(b)1234561 261113943

40、7(c)1234561 2611139437(d)111234561 26139437(e)1234561 2943(f) The cost of an edge (x,y) denoted by cx,y, is stored at the node for y in the adjacency list corresponding of x. Two sets X and Y will be implemented as boolean vectors X1.n and Y1.n. Initially, X1 =1 and Y1=0, and for all i, 2i n Xi=0 ,

41、Yi=1. Thus, operation is implemented by setting Xy to 1, and the operation is implemented by setting Yy to 0. If (x,y) is an edge such that and , we will call y a bordering vertex. Bordering vertices are candidates for being moved from Y to X. Let y be a bordering vertex. Then there is at least one

42、vertex that is adjacent to y. We define the neighbor of y, denoted by Ny, to be that vertex x in X with the property that cx,y is minimum among all vertices adjacent to y in X. We also define Cy=cy,Ny. Thus, Ny is the nearest neighbor to y in x and Cy is the cost of the edge connecting y and Ny.Nort

43、h China Electric Power UniversityT ; X 1; YV-1for y 2 to n if y is adjacent to 1 then else end for for j 1 to n-1 Let be such that Cy is minimum for each vertex that is adjacent to y if cy,w0，取ti=si 1i4,ij,tj=sj-1。ti,i=14是子问题 min ti 4i=1s.t. tici=n-cj4i=1的最优解。North China Electric Power University2) 贪心选择性质 对于所述问题的任一最优解si,i=14,s44,s31,s22。 事实上，若s45,则可用1枚面值为c3的硬币去替代5枚面值为c4的硬币; 当s3 2时，可用1枚面值为c2的硬币去替换2枚面值为c3的硬币; 当s23时，可用1枚面值为c1的硬币和1枚面值为c3的硬币去替换3枚面值为c2的硬币。 这些替换都导致si,i=14不是最优解。