Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 77
Текст из файла (страница 77)
Thus, x is an extension of Ø.Corollary 16.9Let M = (S,ℓ) be any matroid. If x is an element of S such that x is not an extension of Ø, thenx is not an extension of any independent subset A of S.Proof This corollary is simply the contrapositive of Lemma 16.8.Corollary 16.9 says that any element that cannot be used immediately can never be used.Therefore, GREEDY cannot make an error by passing over any initial elements in S that arenot an extension of Ø, since they can never be used.Lemma 16.10: Matroids exhibit the optimal-substructure propertyLet x be the first element of S chosen by GREEDY for the weighted matroid M = (S,ℓ).
Theremaining problem of finding a maximum-weight independent subset containing x reduces tofinding a maximum-weight independent subset of the weighted matroid M′ = (S′,ℓ), whereS′ = {yℓ′ = {BS : {x, y} ℓ},S - {x} : B {x}ℓ}, andthe weight function for M′ is the weight function for M, restricted to S′.
(We call M′ thecontraction of M by the element x.)Proof If A is any maximum-weight independent subset of M containing x, then A′ = A - {x} isan independent subset of M′. Conversely, any independent subset A′ of M′ yields anindependent 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′, andvice versa.Theorem 16.11: (Correctness of the greedy algorithm on matroidsIf M = (S,ℓ) is a weighted matroid with weight function w, then GREEDY(M, w) returns anoptimal subset.Proof By Corollary 16.9, any elements that are passed over initially because they are notextensions of Ø can be forgotten about, since they can never be useful. Once the first elementx is selected, Lemma 16.7 implies that GREEDY does not err by adding x to A, since thereexists an optimal subset containing x. Finally, Lemma 16.10 implies that the remainingproblem is one of finding an optimal subset in the matroid M′ that is the contraction of M byx.
After the procedure GREEDY sets A to {x}, all of its remaining steps can be interpreted asacting in the matroid M′ = (S′,ℓ′), because B is independent in M′ if and only if B {x} isindependent in M, for all sets B ℓ′. Thus, the subsequent operation of GREEDY will find amaximum-weight independent subset for M′, and the overall operation of GREEDY will finda maximum-weight independent subset for M.Exercises 16.4-1Show that (S,ℓk) is a matroid, where S is any finite set andℓk is the set of all subsets of S ofsize at most k, where k ≤ |S|.Exercises 16.4-2:Given an m × n matrix T over some field (such as the reals), show that (S,ℓ) is a matroid,where S is the set of columns of T and A ℓ if and only if the columns in A are linearlyindependent.Exercises 16.4-3:Show that if (S,ℓ) is a matroid, then (S,ℓ′) is a matroid, whereℓ′ = {A′ : S - A′ contains some maximal Aℓ}.That is, the maximal independent sets of (S,ℓ′) are just the complements of the maximalindependent sets of (S,ℓ).Exercises 16.4-4:Let S be a finite set and let S1, S2, ..., Sk be a partition of S into nonempty disjoint subsets.Define the structure (S,ℓ) by the condition thatℓ = {A : |A ∩ Si| ≤ 1 for i = 1, 2, ..., k}.
Showthat (S,ℓ) is a matroid. That is, the set of all sets A that contain at most one member in eachblock of the partition determines the independent sets of a matroid.Exercises 16.4-5Show how to transform the weight function of a weighted matroid problem, where the desiredoptimal solution is a minimum-weight maximal independent subset, to make it an standardweighted-matroid problem.
Argue carefully that your transformation is correct.16.5A task-scheduling problemAn interesting problem that can be solved using matroids is the problem of optimallyscheduling unit-time tasks on a single processor, where each task has a deadline,along with a penalty that must be paid if the deadline is missed. The problem lookscomplicated, but it can be solved in a surprisingly simple manner using a greedyalgorithm.A unit-time task is a job, such as a program to be run on a computer, that requiresexactly one unit of time to complete. Given a finite set S of unit-time tasks, a schedulefor S is a permutation of S specifying the order in which these tasks are to beperformed. The first task in the schedule begins at time 0 and finishes at time 1, thesecond task begins at time 1 and finishes at time 2, and so on.The problem of scheduling unit-time tasks with deadlines and penalties for asingle processor has the following inputs: a set S = {a1, a2, ..., an} of n unit-time tasks; a set of n integer deadlines d1, d2, ..., dn, such that each di satisfies 1 ≤ di ≤ nand task ai is supposed to finish by time di; and a set of n nonnegative weights or penalties w1, w2, ..., wn, such that we incur apenalty of wi if task ai is not finished by time di and we incur no penalty if a taskfinishes by its deadline.We are asked to find a schedule for S that minimizes the total penalty incurred formissed deadlines.Consider a given schedule.
We say that a task is late in this schedule if it finishes afterits deadline. Otherwise, the task is early in the schedule. An arbitrary schedule canalways be put into early-first form, in which the early tasks precede the late tasks. Tosee this, note that if some early task ai follows some late task aj, then we can switch thepositions of ai and aj, and ai will still be early and aj will still be late.We similarly claim that an arbitrary schedule can always be put into canonical form, inwhich the early tasks precede the late tasks and the early tasks are scheduled in orderof monotonically increasing deadlines. To do so, we put the schedule into early-firstform.
Then, as long as there are two early tasks ai and aj finishing at respective times kand k + 1 in the schedule such that dj < di, we swap the positions of ai and aj. Since ajis early before the swap, k + 1 ≤ dj. Therefore, k + 1 < di, and so ai is still early afterthe swap. Task aj is moved earlier in the schedule, so it also still early after the swap.The search for an optimal schedule thus reduces to finding a set A of tasks that are tobe early in the optimal schedule.
Once A is determined, we can create the actualschedule by listing the elements of A in order of monotonically increasing deadline, thenlisting the late tasks (i.e., S - A) in any order, producing a canonical ordering of theoptimal schedule.We say that a set A of tasks is independent if there exists a schedule for these taskssuch that no tasks are late. Clearly, the set of early tasks for a schedule forms anindependent set of tasks.
Letℓ denote the set of all independent sets of tasks.Consider the problem of determining whether a given set A of tasks is independent. Fort = 0, 1, 2, ..., n, let Nt (A) denote the number of tasks in A whose deadline is t or earlier.Note that N0(A) = 0 for any set A.Lemma 16.12For any set of tasks A, the following statements are equivalent.1. The set A is independent.2. For t = 0, 1, 2, ..., n, we have Nt (A) ≤ t.3. If the tasks in A are scheduled in order of monotonically increasingdeadlines, then no task is late.Proof Clearly, if Nt (A) >; t for some t, then there is no way to make a schedule with nolate tasks for set A, because there are more than t tasks to finish before time t.
Therefore,(1) implies (2). If (2) holds, then (3) must follow: there is no way to "get stuck" whenscheduling the tasks in order of monotonically increasing deadlines, since (2) implies thatthe ith largest deadline is at most i. Finally, (3) trivially implies (1).Using property 2 of Lemma 16.12, we can easily compute whether or not a given set oftasks is independent (see Exercise 16.5-2).The problem of minimizing the sum of the penalties of the late tasks is the same as theproblem of maximizing the sum of the penalties of the early tasks.
The followingtheorem thus ensures that we can use the greedy algorithm to find an independent setA of tasks with the maximum total penalty.Theorem 16.13If S is a set of unit-time tasks with deadlines, andℓ is the set of all independent sets oftasks, then the corresponding system (S,ℓ) is a matroid.Proof Every subset of an independent set of tasks is certainly independent.
To prove theexchange property, suppose that B and A are independent sets of tasks and that |B| >;|A|. Let k be the largest t such that Nt (B) ≤ Nt (A). (Such a value of t exists, since N0(A) =N0(B) = 0.) Since Nn(B) = |B| and Nn(A) = |A|, but |B| >; |A|, we must have that k < n andthat Nj(B) >; Nj(A) for all j in the range k + 1 ≤ j ≤ n. Therefore, B contains more taskswith deadline k + 1 than A does.
Let ai be a task in B - A with deadline k + 1. Let A′ = A ∪{ai}.We now show that A′ must be independent by using property 2 of Lemma 16.12. For 0 ≤t ≤ k, we have Nt (A′) = Nt (A) ≤ t, since A is independent. For k < t = n, we have Nt(A′) ≤ Nt (B) ≤ t, since B is independent.
Therefore, A′ is independent, completing ourproof that (S,ℓ) is a matroid.By Theorem 16.11, we can use a greedy algorithm to find a maximum-weightindependent set of tasks A. We can then create an optimal schedule having the tasks inA as its early tasks. This method is an efficient algorithm for scheduling unit-time taskswith deadlines and penalties for a single processor. The running time is O(n2) usingGREEDY, since each of the O(n) independence checks made by that algorithm takestime O(n) (see Exercise 16.5-2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
