未知算法设计科dye-greedy

1、1Greedy algorithm叶德仕 2 Greedy algorithms paradigmAlgorithm is greedy ifit builds up a solution in small stepsit chooses a decision at each step myopically to optimize some underlying criterionAnalyzing optimal greedy algorithms by showing that:in every step it is not worse than any other algorithm,

2、or every algorithm can be gradually transformed to thegreedy one without hurting its quality3Interval schedulingInput: set of intervals on the line, represented by pairs of points (ends of intervals). In another word, the ith interval, starts at time si and finish at fi.Output: finding the largest s

3、et of intervals such that none two of them overlap. Or the maximum number of intervals that without overlap. Greedy algorithm:Select intervals one after another using some rule4Rule 1Select the interval which starts earliest (but not overlapping the already chosen intervals)Underestimated solution!A

4、lgorithm #1OPT #45Rule 2Select the interval which is shortest (but not overlapping the already chosen intervals)Underestimated solution!Algorithm #1OPT #26Rule 3Select the interval with the fewest conflicts with other remaining intervals (but still not overlapping the already chosen intervals)Undere

5、stimated solution!Algorithm #3OPT #47Rule 4Select the interval which ends first (but still not overlapping the already chosen intervals)Quite a nature idea: we ensure that our resource e free as soon as possible while still satisfying one requestHurray! Exact solution!8f1 smallestAlgorithm #39 Analy

6、sis - exact solutionAlgorithm gives non-overlapping intervals:obvious, since we always choose an interval which does not overlap the previously chosen intervalsThe solution is exact:Let A be the set of intervals obtained by the algorithm, and OPT be the largest set of pairwise non-overlapping interv

7、als. We show that A must be as large as OPT10Analysis exact solution cont.Let and be sorted. By definition of OPT we have k mFact: for every i k, Ai finishes not later than Bi.Pf. by induction.For i = 1 by definition of a step in the algorithm.Suppose that Ai-1 finishes not later than Bi-1.11Analysi

8、s con.From the definition of a step in the algorithm we get that Ai is the first interval that finishes after Ai-1 and does not verlap it.If Bi finished before Ai then it would overlap some of the previous A1 , Ai-1 andconsequently - by the inductive assumption - it would overlap Bi-1, which would b

9、e a contradiction.Bi-1Ai-1BiAi12Analysis con.Theorem: A is the exact solution.Proof: we show that k = m.Suppose to the contrary that k m. We have that Ak finishes not later than Bk Hence we could add Bk+1 to A and obtain bigger solution by the algorithm-contradictionBkAkBk-1Ak-1Bk+113Time complexity

10、Sorting intervals according to the right-most endsFor every consecutive interval:If the left-most end is after the right-most end of the last selected interval then we select this intervalOtherwise we skip it and go to the next intervalTime complexity: O(n log n + n) = O(n log n)14 Planning of schoo

11、lsA collection of towns. We want to plan schools in towns. Each school should be in a townNo one should have to travel more than 30 miles to reach one of them.Edge: towns no far than 30 miles15Set coverInput. A set of elements B, sets Output. A selection of the Si whose union is B.Cost. Number of se

12、ts picked.16Greedy Greedy: first choose a set that covers the largest number of elements. example: place a school at town a, since this covers the largest number of other towns.Greedy #4OPT #317Upper boundTheorem. Suppose B contains n elements that the optimal cover consist of k sets. Then the greed

13、y algorithm will use at most k ln n sets.Pf. Let nt be the number of elements still not covered after t iterations of the greedy algorithm (n0=n). Since these remaining elements are covered by the optimal k sets, there must be some set with at least nt /k of them. Therefore, the greedy algorithm wil

14、l ensure that 18Upper bound con.Then , since for all x, with equality if and only if x=0.ThusAt t=k ln n, therefore, nt is strictly less than ne-ln n =1, which means no elements remains to be covered.Consequently, the approximation ratio is at most ln n19MatroidsWhen will the greedy algorithm yields

15、 optimal solutions?Matroids Hassler Whitney: A matroid is an ordered pair M=(S, ) satisfying the following conditions.S is a finite nonempty set is a nonempty family of subsets of S, called the independent subsets of S, such that if We say that is hereditary if it satisfies this property. Note that

16、empty set is necessarily a member of .If , then there is some element such that . We say that M satisfies the exchage property. 20Max independentTheorem. All maximal independent subsets in a matroid have the same size.Pf. Suppose to the contrary that A is a maximal independent subset of M and there

17、exists another larger maximal independent subset B of M. Then, the exchange property implies that A is extendible to a larger independent set A x for some x B - A, contradicting the assumption that A is maximal.21Weighted MatroidWe say that a matroid M = (S,) is weighted if there is an associated we

18、ight function w that assigns a strictly positive weight w(x) to each element x S. The weight function w extends to subsets of S by summation:for any A S. 22Greedy algorithms on a weighted matroid Many problems for which a greedy approach provides optimal solutions can be formulated in terms of findi

19、ng a maximum-weight independent subset in a weighted matroid. That is, we are given a weighted matroid M = (S,), and we wish to find an independent set A such that w(A) is maximized. We call such a subset that is independent and has maximum possible weight an optimal subset of the matroid. Because t

20、he weight w(x) of any element x S is positive, an optimal subset is always a maximal independent subset-it always helps to make A as large as possible.23Greedy algorithmGREEDY(M, w) 1. A 2. sort SM into monotonically decreasing order by weight w 3. for each x SM, taken in monotonically decreasing or

21、der by weight w(x) 4. do if A x M 5. then A A x 6. return A 24LemmaLemma 1. Suppose that M = (S,) is a weighted matroid with weight function w and that S is sorted into monotonically decreasing order by weight. Let x be the first element of S such that x is independent, if any such x exists. If x ex

22、ists, then there exists an optimal subset A of S that contains x.Pf.If no such x exists, then the only independent subset is the empty set and were done. Otherwise, let B be any nonempty optimal subset. Assume that x B; otherwise, we let A = B and were done.No element of B has weight greater than w(

23、x). To see this, observe that y B implies that y is independent, since B and is hereditary. Our choice of x therefore ensures that w(x) w(y) for any y B.25LemmaConstruct the set A as follows. Begin with A = x. By the choice of x, A is independent. Using the exchange property, repeatedly find a new e

24、lement of B that can be added to A until |A| = |B| while preserving the independence of A. Then, A = B - y x for some y B, and so w(A)=w(B) - w(y) + w(x) w(B). Because B is optimal, A must also be optimal, and because x A, the lemma is proven.26LemmaLemma 2. Let M = (S,) be any matroid. If x is an e

25、lement of S that is an extension of some independent subset A of S, then x is also an extension of .Pf. Since x is an extension of A, we have that A x is independent. Since is hereditary, x must be independent. Thus, x is an extension of .It is shown that if an element is not an option initially, th

26、en it cannot be an option later. 27CorollaryCorollary Let M = (S,) be any matroid. If x is an element of S such that x is not an extension of , then x is not an extension of any independent subset A of S.Any element that cannot be used immediately can never be used. Therefore, GREEDY cannot make an

27、error by passing over any initial elements in S that are not an extension of , since they can never be used. 28Lemma 3. Let x be the first element of S chosen by GREEDY for the weighted matroid M = (S,). The remaining problem of finding a maximum-weight independent subset containing x reduces to fin

28、ding a maximum-weight independent subset of the weighted matroid M = (S,), where S =y S : x, y , =B S - x : B x , and the weight function for M is the weight function for M, restricted to S. (We call M the contraction of M by the element x.)29Proof If A is any maximum-weight independent subset of M

29、containing x, then A = A - x is an independent subset of M. Conversely, any independent subset A of M yields an independent subset A = A x of M. Since we have in both cases that w(A) = w(A) + w(x), a maximum-weight solution in M containing x yields a maximum-weight solution in M, and vice versa.30Th

30、eoremTheorem. If M = (S,) is a weighted matroid with weight function w, then GREEDY(M, w) returns an optimal subset.Pf. By Corollary, any elements that are passed over initially because they are not extensions of can be forgotten about, since they can never be useful. Once the first element x is sel

31、ected, Lemma 1 implies that GREEDY does not err by adding x to A, since there exists an optimal subset containing x. 31Theorem con.Finally, Lemma 3 implies that the remaining problem is one of finding an optimal subset in the matroid M that is the contraction of M by x. After the procedure GREEDY se

32、ts A to x, all of its remaining steps can be interpreted as acting in the matroid M = (S,), because B is independent in M if and only if B x is independent in M, for all sets B . Thus, the subsequent operation of GREEDY will find a maximum-weight independent subset for M, and the overall operation o

33、f GREEDY will find a maximum-weight independent subset for M.32 Minimum spanning treeInput: weighted graph G = (V,E) every edge in E has its positive weight Output: finding the spanning tree such that the sum of weights is not bigger than the sum of weights of any other spanning treeSpanning tree: s

34、ubgraph with no cycle, andconnected (every two nodes in V are connected by a path)11223112231122333Properties of minimum spanning trees MSTSpanning trees:n nodesn - 1 edgesat least 2 leaves (leaf - a node with only one neighbor)MST cycle property:After adding an edge we obtain exactly one cycle and

35、all the edges from MST in this cycle have no bigger weight than the weight of the added edge1122311223cycle34 Optimal substructuresMST T:(Other edges of Gare not shown.)35 Optimal substructuresMST T:(Other edges of Gare not shown.)Remove any edge (u, v) T.uv36 Optimal substructuresMST T:(Other edges

36、 of Gare not shown.)Remove any edge (u, v) T. Then, T is partitionedinto two subtrees T1 and T2.T1T237 Optimal substructuresMST T:(Other edges of Gare not shown.)Remove any edge (u, v) T. Then, T is partitionedinto two subtrees T1 and T2.T1T2Theorem. The subtree T1 is an MST of G1 = (V1, E1),the sub

37、graph of G induced by the vertices of T1:V1 = vertices of T1,E1 = (x, y) E : x, y V1 .Similarly for T2.38Proof of optimal substructureProof. Cut and paste: w(T) = w(u, v) + w(T1) + w(T2).If T1 were a lower-weight spanning tree than T1 for G1, then T = (u, v) T1 T2 would be a lower-weight spanning tr

38、ee than T for G.39Do we also have overlapping subproblems?Yes.Great, then dynamic programming may work!Yes, but MST exhibits another powerful property which leads to an even more efficient algorithm. 40Crucial observation about MSTConsider sets of nodes A and V - ALet F be the set of edges between A

39、 and V - ALet a be the smallest weight of an edge from F Theorem:Every MST must contain at least one edge of weight afrom set F 1122311223AA41Proof of the observationLet e be the edge in F with the smallest weight - for simplicity assume that there is unique such edge. Suppose to the contrary that e

40、 is not in some MST. Choose one such MST.Add e to MST - obtain the cycle, where e is (among) smallest weights. Since two ends of e are in different sets A and V - A, there is another edge f in the cycle and in F. Remove f from the tree (with added edge e) - obtain a spanning tree with the smaller we

41、ight(since f has bigger weight than e). This is a contradiction with MST.1122311223AA42Greedy algorithm finding MSTKruskals algorithm:Sort all edges according to the weightsChoose n - 1 edges one after another as follows:If a new added edge does not create a cycle with previously selected then we ke

42、ep it in (partial) MST, otherwise we remove itRemark: we always have a partial forest11223112231122343Greedy algorithm finding MSTPrims algorithm:Select a node as a root arbitrarilyChoose n - 1 edges one after another as follows:Look on all edges incident to the currently build (partial) tree and wh

43、ich do not create a cycle in it, and select one which has the smallest weightRemark: we always have a connected partial tree112231122311223root44Example of PrimAV - A6125148310791545Example of PrimAV - A6125148310791546Example of Prim70AV - A6125148310791547Example of Prim70AV - A6125148310791548Example of Prim570AV - A6125148310791549Example of Prim6570AV - A6125148310791550Example of Prim65708AV - A6125148310791551Example of Prim65708AV - A6125148310791552Example of Prim653708AV - A61251483107915