chap17.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<img src="346_e.gif"><P>
for any <I>A </I><img src="../images/rgtubar.gif"><I> S</I>. For example, if we let <I>w</I>(<I>e</I>) denote the length of an edge <I>e</I> in a graphic matroid <I>M<SUB>G</I></SUB>, then <I>w</I>(<I>A</I>) is the total length of the edges in edge set <I>A</I>.<P>
<P>







<h2><a name="0836_15b3">17.4.2 Greedy algorithms on a weighted matroid<a name="0836_15b3"></h2><P>
<a name="0836_15ab"><a name="0836_15ac">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 <img src="347_a.gif">, and we wish to find an independent set <img src="347_b.gif"> such that <I>w</I>(<I>A</I>) is maximized. We call such a subset that is independent and has maximum possible weight an <I><B>optimal</I></B> subset of the matroid. Because the weight <I>w</I>(<I>x</I>) of any element <I>x</I> <img src="../images/memof12.gif"> <I>S</I> is positive, an optimal subset is always a maximal independent subset--it always helps to make <I>A</I> as large as possible.<P>
<a name="0836_15ad"><a name="0836_15ae">For example, in the <I><B>minimum-spanning-tree problem</I></B>, we are given a connected undirected graph <I>G</I> = (<I>V, E</I>) and a length function <I>w</I> such that <I>w </I>(<I>e</I>) is the (positive) length of edge <I>e</I>. (We use the term &quot;length&quot; here to refer to the original edge weights for the graph, reserving the term &quot;weight&quot; 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 <I>M<SUB>G</I></SUB> with weight function <I>w</I>'<I>, where </I>w<I>'</I>(<I>e</I>) = <I>w</I><SUB>0</SUB> - <I>w</I>(<I>e</I>) and <I>w</I><SUB>0</SUB> 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 <I>A</I> corresponds to a spanning tree, and since<P>
<pre><I>w'</I>(<I>A</I>)<I> = </I>(|<I>V| - 1)</I>w<I><SUB>0</SUB> - </I>w<I>(</I>A<I>)</I></sub></sup></pre><P>
for any maximal independent subset <I>A</I>, the independent subset that maximizes <I>w</I><I>'</I>(<I>A</I>)<I> </I>must minimize<I> w</I>(<I>A</I>). Thus, any algorithm that can find an optimal subset <I>A</I> in an arbitrary matroid can solve the minimum-spanning-tree problem.<P>
Chapter 24 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 <img src="347_c.gif"> with an an associated positive weight function <I>w</I>, and it returns an optimal subset <I>A</I>. In our pseudocode, we denote the components of <I>M</I> by <I>S</I>[<I>M</I>]<I> </I>and<I> </I><img src="347_d.gif"> and the weight function by <I>w</I>. The algorithm is greedy because it considers each element <I>x </I><img src="../images/memof12.gif"><I> S</I> in turn in order of nonincreasing weight and immediately adds it to the set <I>A</I> being accumulated if <I>A</I> <img src="../images/wideu.gif"> {<I>x</I>} is independent.<P>
<img src="348_a.gif"><P>
<a name="0836_15af">The elements of <I>S</I> are considered in turn, in order of nonincreasing weight. If the element <I>x</I> being considered can be added to <I>A</I> while maintaining <I>A</I>'s independence, it is. Otherwise, <I>x</I> is discarded. Since the empty set is independent by the definition of a matroid, and since <I>x</I> is only added to <I>A </I>if<I> A</I> <img src="../images/wideu.gif"> {<I>x</I>} is independent, the subset <I>A</I> is always independent, by induction. Therefore, <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> always returns an independent subset <I>A</I>. We shall see in a moment that <I>A</I> is a subset of maximum possible weight, so that <I>A</I> is an optimal subset.<P>
The running time of <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> is easy to analyze. Let <I>n</I> denote |<I>S|</I>. The sorting phase of <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> takes time <I>O</I>(<I>n </I>l<I>g n</I>). Line 4 is executed exactly <I>n</I> times, once for each element of <I>S</I>. Each execution of line 4 requires a check on whether or not the set <I>A</I> <img src="../images/wideu.gif"> {<I>x</I>} is independent. If each such check takes time <I>O</I>(<I>f(n</I>)), the entire algorithm runs in time <I>O</I>(<I>n </I>l<I>g n</I> +<I> nf</I>(<I>n</I>)).<P>
We now prove that <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> returns an optima1 subset.<P>
<a name="0836_15b4">Lemma 17.7<a name="0836_15b4"><P>
<a name="0836_15b0">Suppose that <img src="348_b.gif"> is a weighted matroid with weight function <I>w</I> and that <I>S</I> is sorted into nonincreasing order by weight. Let <I>x</I> be the first element of <I>S</I> such that {<I>x</I>} is independent, if any such <I>x</I> exists. If <I>x</I> exists, then there exists an optimal subset <I>A</I> of <I>S</I> that contains <I>x</I>.<P>
<I><B>Proof     </I></B>If no such <I>x</I> exists, then the only independent subset is the empty set and we're done. Otherwise, let <I>B</I> be any nonempty optimal subset. Assume that <I>x</I> <img src="../images/notmem.gif"> <I>B</I>; otherwise, we let <I>A</I> = <I>B</I> and we're done.<P>
No element of <I>B</I> has weight greater than <I>w</I>(<I>x</I>). To see this, observe that <I>y</I> <img src="../images/memof12.gif"> <I>B</I> implies that {<I>y</I>} is independent, since <img src="348_c.gif"> and <I>I</I> is hereditary. Our choice of <I>x</I> therefore ensures that <I>w</I>(<I>x</I>) <img src="../images/gteq.gif"> <I>w</I>(<I>y</I>) for any <I>y</I> <img src="../images/memof12.gif"> <I>B</I>.<P>
Construct the set <I>A</I> as follows. Begin with <I>A</I> = {<I>x</I>}. By the choice of <I>x, A</I> is independent. Using the exchange property, repeatedly find a new element of <I>B</I> that can be added to <I>A</I> until |<I>A| = |</I>B| while preserving the independence of <I>A</I>. Then, <I>A = B - </I>{<I>y</I>} <img src="../images/wideu.gif"> {<I>x</I>} for some <I>y</I> <img src="../images/memof12.gif"> <I>B</I>, and so<P>
<pre><I>w</I>(<I>A</I>) <I>= w</I>(<I>B</I>)<I> - w</I>(<I>y</I>) + <I>w</I>(<I>x</I>)</sub></sup></pre><P>
<pre><img src="../images/gteq.gif"> <I>w</I>(<I>B</I>) .</sub></sup></pre><P>
Because <I>B</I> is optimal, <I>A</I> must also be optimal, and because <I>x</I> <img src="../images/memof12.gif"> <I>A</I>, the lemma is proven.      <P>
We next show that if an element is not an option initially, then it cannot be an option later.<P>
<a name="0836_15b5">Lemma 17.8<a name="0836_15b5"><P>
Let <img src="349_a.gif"> be any matroid. If <I>x</I> is an element of <I>S</I> such that <I>x</I> is not an extension of <img src="349_b.gif">, then <I>x</I> is not an extension of any independent subset <I>A </I>of <I>S.</I><P>
<I><B>Proof     </I></B>The proof is by contradiction. Assume that <I>x</I> is an extension of <I>A</I> but not of <img src="349_c.gif">. Since <I>x</I> is an extension of <I>A</I>, we have that <I>A</I> <img src="../images/wideu.gif"> {<I>x</I>}<I> </I>is independent. Since <img src="349_d.gif"> is hereditary, {<I>x</I>} must be independent, which contradicts the assumption that <I>x</I> is not an extension of <img src="349_e.gif">.      <P>
Lemma 17.8 says that any element that cannot be used immediately can never be used. Therefore, <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> cannot make an error by passing over any initial elements in <I>S</I> that are not an extension of <img src="349_f.gif">, since they can never be used.<P>
<a name="0836_15b6">Lemma 17.9<a name="0836_15b6"><P>
<a name="0836_15b1"><a name="0836_15b2">Let <I>x</I> be the first element of <I>S</I> chosen by <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> for the weighted matroid <img src="349_g.gif">. The remaining problem of finding a maximum-weight independent subset containing <I>x</I> reduces to finding a maximum-weight independent subset of the weighted matroid <img src="349_h.gif">, where<P>
<img src="349_i.gif"><P>
the weight function for <I>M</I>'<I> is the weight function for </I>M<I>, restricted to </I>S<I>'</I>. (We call <I>M</I>'<I> the </I><B>contraction<I></B> of </I>M<I> by the element </I>x<I>.)</I><P>
<I><B>Proof     </I></B>If <I>A</I> is any maximum-weight independent subset of <I>M</I> containing <I>x</I>, then <I>A</I>' = A - <I>{</I>x<I>} is an independent subset of </I>M<I>'</I>. Conversely, any independent subset <I>A</I>'<I> of </I>M<I>'</I> yields an independent subset <I>A</I> = <I>A</I>'<I> <img src="../images/wideu.gif"> {</I>x<I>} of </I>M<I>. Since we have in both cases that </I>w<I>(</I>A<I>) = </I>w<I>(</I>A<I>'</I>) + <I>w</I>(<I>x</I>), a maximum-weight solution in <I>M</I> containing <I>x</I> yields a maximum-weight solution in <I>M</I>', and vice versa.<P>
<a name="0836_15b7">Theorem 17.10<a name="0836_15b7"><P>
If <img src="349_j.gif"> is a weighted matroid with weight function<I> w,</I> then the call <FONT FACE="Courier New" SIZE=2>GREEDY</FONT>(<I>M, w</I>) returns an optimal subset.<P>
<I><B>Proof     </I></B>By Lemma 17.8, any elements that are passed over initially because they are not extensions of <img src="349_k.gif"> can be forgotten about, since they can never be useful. Once the first element <I>x </I>is selected, Lemma 17.7 implies that <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> does not err by adding <I>x</I> to <I>A</I>, since there exists an optimal subset containing <I>x</I>. Finally, Lemma 17.9 implies that the remaining problem is one of finding an optimal subset in the matroid <I>M</I><I>'</I> that is the contraction of <I>M</I> by <I>x</I>. After the procedure <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> sets <I>A </I>to{<I>x</I>}, all of its remaining steps can be interpreted as acting in the matroid <img src="350_a.gif">, because <I>B</I> is independent in <I>M</I><I>'</I> if and only if <I>B</I> <img src="../images/wideu.gif"> {<I>x</I>} is independent in <I>M</I>, for all sets <img src="350_b.gif">. Thus, the subsequent operation of <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> will find a maximum-weight independent subset for <I>M</I><I>'</I>, and the overall operation of <FONT FACE="Courier New" SIZE=2>GREEDY</FONT> will find a maximum-weight independent subset for <I>M</I>.      <P>
<P>







<h2><a name="0837_0001">Exercises<a name="0837_0001"></h2><P>
<a name="0837_0002">17.4-1<a name="0837_0002"><P>
Show that <img src="350_c.gif"> is a matroid, where <I>S</I> is any finite set and <img src="350_d.gif"> is the set of all subsets of <I>S</I> of size at most <I>k</I>, where <I>k </I><img src="../images/lteq12.gif"> |S|.<P>
<a name="0837_0003">17.4-2<a name="0837_0003"><P>
Given an <I>n</I> <img src="../images/mult.gif"> <I>n</I> real-valued matrix <I>T</I>, show that <img src="350_e.gif"> is a matroid, where <I>S</I> is the set of columns of <I>T</I> and <img src="350_f.gif"><I> </I>if and only if the columns in <I>A</I> are linearly independent.<P>
<a name="0837_0004">17.4-3<a name="0837_0004"><P>
Show that if <img src="350_g.gif"> is a matroid, then <img src="350_h.gif"> is a matroid, where <img src="350_i.gif"> contains some maximal <img src="350_j.gif">. That is, the maximal independent sets of <img src="350_k.gif"> are just the complements of the maximal independent sets of <img src="350_l.gif">.<P>
<a name="0837_0005">17.4-4<a name="0837_0005"><P>
Let <I>S</I> be a finite set and let <I>S</I><SUB>1</SUB>, <I>S</I><SUB>2</SUB>, . . . , <I>S<SUB>k</I></SUB> be a partition of <I>S</I> into nonempty disjoint subsets. Define the structure <img src="350_m.gif"> by the condition that <img src="350_n.gif">. Show that <img src="350_o.gif"> is a matroid. That is, the set of all sets <I>A</I> that contain at most one member in each block of the partition determines the independent sets of a matroid.<P>
<a name="0837_0006">17.4-5<a name="0837_0006"><P>
Show how to transform the weight function of a weighted matroid problem, where the desired optimal solution is a <I>minimum-weight</I> maximal independent subset, to make it an standard weighted-matroid problem. Argue carefully that your transformation is correct.<P>
<P>


<P>







<h1><a name="0838_15b5">* 17.5 A task-scheduling problem<a name="0838_15b5"></h1><P>
<a name="0838_15b3"><a name="0838_15b4">An interesting problem that can be solved using matroids is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline and a