|
|
< Day Day Up > |
|
There is a beautiful theory about greedy algorithms, which we sketch in this section. This theory is useful in determining when the greedy method yields optimal solutions. It involves combinatorial structures known as "matroids." Although this theory does not cover all cases for which a greedy method applies (for example, it does not cover the activity-selection problem of Section 16.1 or the Huffman coding problem of Section 16.3), it does cover many cases of practical interest. Furthermore, this theory is being rapidly developed and extended to cover many more applications; see the notes at the end of this chapter for references.
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 B ∈ℓ and A ⊆ B, then A ∈ℓ. We say thatℓ is hereditary if it satisfies this property. Note that the empty set Ø is necessarily a member ofℓ.
If A ∈ℓ, B ∈ℓ, and |A| < |B|, then there is some element x ∈ B - A such that A ∪ {x} ∈ℓ. We say that M satisfies the exchange property.
The word "matroid" is due to Hassler Whitney. He was studying matric matroids, in which the elements of S are the rows of a given matrix and a set of rows is independent if they are linearly independent in the usual sense. It is easy to show that this structure defines a matroid (see Exercise 16.4-2).
As another example of matroids, consider the graphic matroid MG = (SG,ℓG) defined in terms of a given undirected graph G = (V, E) as follows.
The set SG is defined to be E, the set of edges of G.
If A is a subset of E, then A ∈ℓG if and only if A is acyclic. That is, a set of edges A is independent if and only if the subgraph GA = (V, A) forms a forest.
The graphic matroid MG is closely related to the minimum-spanning-tree problem, which is covered in detail in Chapter 23.
 |
If G = (V, E) is an undirected graph, then MG = (SG,ℓG) is a matroid.
Proof Clearly, SG = E is a finite set. Furthermore,ℓG is hereditary, since a subset of a forest is a forest. Putting it another way, removing edges from an acyclic set of edges cannot create cycles.
Thus, it remains to show that MG satisfies the exchange property. Suppose that GA = (V, A) and GB = (V, B) are forests of G and that |B| >; |A|. That is, A and B are acyclic sets of edges, and B contains more edges than A does.
It follows from Theorem B.2 that a forest having k edges contains exactly |V|-k trees. (To prove this another way, begin with |V| trees, each consisting of a single vertex, and no edges. Then, each edge that is added to the forest reduces the number of trees by one.) Thus, forest GA contains |V| - |A| trees, and forest GB contains |V| - |B| trees.
Since forest GB has fewer trees than forest GA does, forest GB must contain some tree T whose vertices are in two different trees in forest GA. Moreover, since T is connected, it must contain an edge (u, v) such that vertices u and v are in different trees in forest GA. Since the edge (u, v) connects vertices in two different trees in forest GA, the edge (u, v) can be added to forest GA without creating a cycle. Therefore, MG satisfies the exchange property, completing the proof that MG is a matroid.
|
Given a matroid M = (S,ℓ), we call an element x ∉ A an extension of A ∈ℓ if x can be added to A while preserving independence; that is, x is an extension of A if A ∪ {x} ∈ℓ. As an example, consider a graphic matroid MG. If A is an independent set of edges, then edge e is an extension of A if and only if e is not in A and the addition of e to A does not create a cycle.
If A is an independent subset in a matroid M, we say that A is maximal if it has no extensions. That is, A is maximal if it is not contained in any larger independent subset of M. The following property is often useful.
|
All maximal independent subsets in a matroid have the same size.
Proof Suppose to the contrary that A is a maximal independent subset of M and there 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.
|
As an illustration of this theorem, consider a graphic matroid MG for a connected, undirected graph G. Every maximal independent subset of MG must be a free tree with exactly |V| - 1 edges that connects all the vertices of G. Such a tree is called a spanning tree of G.
We say that a matroid M = (S,ℓ) is weighted if there is an associated weight 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. For example, if we let w(e) denote the length of an edge e in a graphic matroid MG, then w(A) is the total length of the edges in edge set A.
Many problems for which a greedy approach provides optimal solutions can be formulated in terms of finding 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 the 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.
For example, in the minimum-spanning-tree problem, we are given a connected undirected graph G = (V, E) and a length function w such that w(e) is the (positive) length of edge e. (We use the term "length" here to refer to the original edge weights for the graph, reserving the term "weight" to refer to the weights in the associated matroid.) We are asked to find a subset of the edges that connects all of the vertices together and has minimum total length. To view this as a problem of finding an optimal subset of a matroid, consider the weighted matroid MG with weight function w′, where w′(e) = w0 - w(e) and w0 is larger than the maximum length of any edge. In this weighted matroid, all weights are positive and an optimal subset is a spanning tree of minimum total length in the original graph. More specifically, each maximal independent subset A corresponds to a spanning tree, and since
w′(A) = (|V| - 1)w0 - w(A)
for any maximal independent subset A, an independent subset that maximizes the quantity w′(A) must minimize w(A). Thus, any algorithm that can find an optimal subset A in an arbitrary matroid can solve the minimum-spanning-tree problem.
Chapter 23 gives algorithms for the minimum-spanning-tree problem, but here we give a greedy algorithm that works for any weighted matroid. The algorithm takes as input a weighted matroid M = (S,ℓ) with an associated positive weight function w, and it returns an optimal subset A. In our pseudocode, we denote the components of M by S[M] andℓ[M] and the weight function by w. The algorithm is greedy because it considers each element x ∈ S in turn in order of monotonically decreasing weight and immediately adds it to the set A being accumulated if A∪{x} is independent.
GREEDY(M, w) 1 A ← Ø 2 sort S[M] into monotonically decreasing order by weight w 3 for each x S[M], taken in monotonically decreasing order by weight w(x) 4 do if A ∪ {x} ∈ℓ[M] 5 then A ← A ∪ {x} 6 return A
The elements of S are considered in turn, in order of monotonically decreasing weight. If the element x being considered can be added to A while maintaining A's independence, it is. Otherwise, x is discarded. Since the empty set is independent by the definition of a matroid, and since x is added to A only if A ∪ {x} is independent, the subset A is always independent, by induction. Therefore, GREEDY always returns an independent subset A. We shall see in a moment that A is a subset of maximum possible weight, so that A is an optimal subset.
The running time of GREEDY is easy to analyze. Let n denote |S|. The sorting phase of GREEDY takes time O(n lg n). Line 4 is executed exactly n times, once for each element of S. Each execution of line 4 requires a check on whether or not the set A ∪ {x} is independent. If each such check takes time O(f(n)), the entire algorithm runs in time O(n lg n + nf (n)).
We now prove that GREEDY returns an optimal subset.
|
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 exists, then there exists an optimal subset A of S that contains x.
Proof If no such x exists, then the only independent subset is the empty set and we're done. Otherwise, let B be any nonempty optimal subset. Assume that x ∉ B; otherwise, we let A = B and we're done.
No element of B has weight greater than w(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.
Construct 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 element 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.
|
We next show that if an element is not an option initially, then it cannot be an option later.
|
Let M = (S,ℓ) be any matroid. If x is an element of S that is an extension of some independent subset A of S, then x is also an extension of Ø.
Proof 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 Ø.
|
|
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.
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 are not an extension of Ø, since they can never be used.
|
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 finding 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.)
Proof If A is any maximum-weight independent subset of M 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.
|
|
If M = (S,ℓ) is a weighted matroid with weight function w, then GREEDY(M, w) returns an optimal subset.
Proof By Corollary 16.9, 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 selected, Lemma 16.7 implies that GREEDY does not err by adding x to A, since there exists an optimal subset containing x. Finally, Lemma 16.10 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 sets 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 of GREEDY will find a maximum-weight independent subset for M.
|
|
Show that (S,ℓk) is a matroid, where S is any finite set andℓk is the set of all subsets of S of size at most k, where k ≤ |S|.
|
|
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 linearly independent.
|
|
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 maximal independent sets of (S,ℓ).
|
|
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}. Show that (S,ℓ) is a matroid. That is, the set of all sets A that contain at most one member in each block of the partition determines the independent sets of a matroid.
|
|
|
< Day Day Up > |
|