chap16.htm

介绍算法的书籍

<h4><a name="0814_1544">(16.4)<a name="0814_1544"></sub></sup></h4><P>
We shall prove that <I>T</I>(<I>n</I>) =<I> </I><img src="../images/omega12.gif">(2<I><SUP>n</I></SUP>) using the substitution method. Specifically, we shall show that <I>T</I>(<I>n</I>) <img src="../images/gteq.gif"> 2<I><SUP>n</I>-1</SUP> for all <I>n</I> &gt; 1. The basis is easy, since <I>T</I>(1) &gt; 1 = 2<img src="../images/degree.gif">. Inductively, for <I>n</I> <img src="../images/gteq.gif"> 2 we have<P>
<img src="312_a.gif"><P>
which completes the proof. Thus, the total amount of work performed by the call <FONT FACE="Courier New" SIZE=2>RECURSIVE</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>(<I>p, </I>1, <I>n</I>) is at least exponential in <I>n</I>.<P>
Compare this top-down, recursive algorithm with the bottom-up, dynamic-programming algorithm. The latter is more efficient because it takes advantage of the overlapping-subproblems property. There are only <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>)<I> </I>different subproblems, and the dynamic-programming algorithm solves each exactly once. The recursive algorithm, on the other hand, must repeatedly resolve each subproblem each time it reappears in the recursion tree. Whenever a recursion tree for the natural recursive solution to a problem contains the same subproblem repeatedly, and the total number of different subproblems is small, it is a good idea to see if dynamic programming can be made to work.<P>
<P>







<h2>Memoization</h2><P>
<a name="0815_1543"><a name="0815_1544">There is a variation of dynamic programming that often offers the efficiency of the usual dynamic-programming approach while maintaining a top-down strategy. The idea is to <I><B>memoize</I></B> the natural, but inefficient, recursive algorithm. As in ordinary dynamic programming, we maintain a table with subproblem solutions, but the control structure for filling in the table is more like the recursive algorithm.<P>
A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered during the execution of the recursive algorithm, its solution is computed and then stored in the table. Each subsequent time that the subproblem is encountered, the value stored in the table is simply looked up and returned.<SUP>1<P>
<SUP>1</SUP>This approach presupposes that the set of all possible subproblem parameters is known and that the relation between table positions and subproblems is established. Another approach is to memoize by using hashing with the subproblem parameters as keys.<P>
The following procedure is a memoized version of <FONT FACE="Courier New" SIZE=2>RECURSIVE</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>.<P>
<pre><a name="0815_1545">MEMOIZED-MATRIX-CHAIN(<I>p</I>)</sub></sup></pre><P>
<pre>1 <I>n</I> <img src="../images/arrlt12.gif"> <I>length</I>[<I>p</I>] - 1</sub></sup></pre><P>
<pre>2 <B>for</B> <I>i </I><img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>3      <B>do for</B> <I>j</I> <img src="../images/arrlt12.gif"> <I>i</I> <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>4             <B>do</B> <I>m</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>5 <B>return</B> LOOKUP-CHAIN(<I>p</I>, 1, <I>n</I>)</sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="0815_1546">LOOKUP-CHAIN(<I>p, i, j</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>m</I>[<I>i,j</I>] &lt; <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>2    <B>then return</B> <I>m</I>[<I>i, j</I>]</sub></sup></pre><P>
<pre>3 <B>if</B> <I>i = j</I></sub></sup></pre><P>
<pre>4    <B>then</B> <I>m</I>[<I>i, j</I>]<I> </I><img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>5    <B>else for </B><I>k</I> <img src="../images/arrlt12.gif"> <I>i</I> <B>to</B> <I>j</I> - 1</sub></sup></pre><P>
<pre>6             <B>do</B> <I>q</I> <img src="../images/arrlt12.gif"> LOOKUP-CHAIN(<I>p, i, k</I>)</sub></sup></pre><P>
<pre>+ LOOKUP-CHAIN(<I>p, k</I> + 1, <I>j</I>) + <I>p<SUB>i</I> </SUB>- 1<I>pkpj</I></sub></sup></pre><P>
<pre>7                <B>if</B> <I>q </I>&lt; <I>m</I>[<I>i, j</I>]</sub></sup></pre><P>
<pre>8                   <B>then </B><I>m</I>[<I>i, j</I>] <img src="../images/arrlt12.gif"> <I>q</I></sub></sup></pre><P>
<pre>9 <B>return</B> <I>m</I>[<I>i, j</I>]</sub></sup></pre><P>
<FONT FACE="Courier New" SIZE=2>MEMOIZED</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN,</FONT> like <FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>-<FONT FACE="Courier New" SIZE=2>ORDER</FONT>, maintains a table <I>m</I>[1 . . <I>n</I>, 1 . . <I>n</I>] of computed values of <I>m</I>[<I>i, j</I>], the minimum number of scalar multiplications needed to compute the matrix <I>A<SUB>i</I>..<I>j</I></SUB>. Each table entry initially contains the value <img src="../images/infin.gif"> to indicate that the entry has yet to be filled in. When the call <FONT FACE="Courier New" SIZE=2>LOOKUP</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>(<I>p, i, j</I>) is executed, if <I>m</I>[<I>i, j</I>] &lt; <img src="../images/infin.gif"> in line 1, the procedure simply returns the previously computed cost <I>m[i, j</I>] (line 2). Otherwise, the cost is computed as in <FONT FACE="Courier New" SIZE=2>RECURSIVE</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>, stored in <I>m</I>[<I>i, j</I>], and returned. (The value <img src="../images/infin.gif"> is convenient to use for an unfilled table entry since it is the value used to initialize <I>m</I>[<I>i, j</I>] in line 3 of <FONT FACE="Courier New" SIZE=2>RECURSIVE</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>.) Thus, <FONT FACE="Courier New" SIZE=2>LOOKUP</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>(<I>p, i, j</I>) always returns the value of <I>m</I>[<I>i, j</I>], but it only computes it if this is the first time that <FONT FACE="Courier New" SIZE=2>LOOKUP</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT> has been called with the parameters <I>i</I> and <I>j</I>.<P>
Figure 16.2 illustrates how <FONT FACE="Courier New" SIZE=2>MEMOIZED</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT> saves time over <FONT FACE="Courier New" SIZE=2>RECURSIVE</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>. Shaded subtrees represent values that are looked up rather than computed.<P>
Like the dynamic-programming algorithm <FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>-<FONT FACE="Courier New" SIZE=2>ORDER,</FONT> the procedure <FONT FACE="Courier New" SIZE=2>MEMOIZED</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT> runs in <I>O</I>(<I>n</I><SUP>3</SUP> time. Each of <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) table entries is initialized once in line 4 of <FONT FACE="Courier New" SIZE=2>MEMOIZED</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT> and filled in for good by just one call of <FONT FACE="Courier New" SIZE=2>LOOKUP</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>. Each of these <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) calls to <FONT FACE="Times New Roman" SIZE=2>LOOKUP</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT> takes <I>O</I>(<I>n</I>) time, excluding the time spent in computing other table entries, so a total of <I>O</I>(<I>n</I><SUP>3</SUP>) is spent altogether. Memoization thus turns an <img src="../images/omega12.gif">(2<I><SUP>n</I></SUP>) algorithm into an <I>O</I>(<I>n</I><SUP>3</SUP>) algorithm.<P>
In summary, the matrix-chain multiplication problem can be solved in <I>O(n</I><SUP>3</SUP>) time by either a top-down, memoized algorithm or a bottom-up, dynamic-programming algorithm. Both methods take advantage of the overlapping-subproblems property. There are only <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) different subproblems in total, and either of these methods computes the solution to each subproblem once. Without memoization, the natural recursive algorithm runs in exponential time, since solved subproblems are repeatedly solved.<P>
In general practice, if all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor, because there is no overhead for recursion and less overhead for maintaining the table. Moreover, there are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce time or space requirements even further. Alternatively, if some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of only solving those subproblems that are definitely required.<P>
<P>







<h2><a name="0816_1549">Exercises<a name="0816_1549"></h2><P>
<a name="0816_154a">16.2-1<a name="0816_154a"><P>
Compare the recurrence (16.4) with the recurrence (8.4) that arose in the analysis of the average-case running time of quicksort. Explain intuitively why the solutions to the two recurrences should be so dramatically different.<P>
<a name="0816_154b">16.2-2<a name="0816_154b"><P>
Which is a more efficient way to determine the optimal number of multiplications in a chain-matrix multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running <FONT FACE="Courier New" SIZE=2>RECURSIVE</FONT>-<FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>? Justify your answer.<P>
<a name="0816_154c">16.2-3<a name="0816_154c"><P>
<a name="0816_1547"><a name="0816_1548">Draw the recursion tree for the <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure from Section 1.3.1 on an array of 16 elements. Explain why memoization is ineffective in speeding up a good divide-and-conquer algorithm such as <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>.<P>
<P>


<P>







<h1><a name="0817_154f">16.3 Longest common subsequence<a name="0817_154f"></h1><P>
<a name="0817_1549"><a name="0817_154a"><a name="0817_154b"><a name="0817_154c"><a name="0817_154d">The next problem we shall consider is the longest-common-subsequence problem. A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>,<I> x</I><SUB>2</SUB>, . . . , <I>x<SUB>m</I></SUB><img src="../images/wdrtchv.gif">, another sequence <I>Z</I> = <img src="../images/lftwdchv.gif"><I>z</I><SUB>1</SUB>, <I>z</I><SUB>2</SUB>, . . . , <I>z<SUB>k</I></SUB><img src="../images/wdrtchv.gif"> is a <I><B>subsequence</I></B> of <I>X</I> if there exists a strictly increasing sequence <img src="../images/lftwdchv.gif"><I>i</I><SUB>1</SUB>, <I>i</I><SUB>2</SUB>, . . . , <I>i<SUB>k</I></SUB><img src="../images/wdrtchv.gif"> of indices of <I>X</I> such that for all <I>j</I> = 1, 2, . . . , <I>k</I>, we have <I>x<SUB>ij</I></SUB> = <I>z<SUB>j</I></SUB>. For example, <I>Z = </I><img src="../images/lftwdchv.gif"><I>B, C, D, B</I><img src="../images/wdrtchv.gif"><I> </I>is a subsequence of<I> X = </I><img src="../images/lftwdchv.gif"><I>A, B, C, B, D, A, B</I><img src="../images/wdrtchv.gif"> with corresponding index sequence <img src="../images/lftwdchv.gif">2, 3, 5, 7<img src="../images/wdrtchv.gif">.<P>
<a name="0817_154e">Given two sequences <I>X</I> and <I>Y</I>, we say that a sequence <I>Z</I> is a <I><B>common subsequence</I></B> of <I>X</I> and <I>Y</I> if <I>Z</I> is a subsequence of both <I>X</I> and <I>Y</I>. For example, if <I>X = </I><img src="../images/lftwdchv.gif"><I>A, B, C, B, D, A, B</I><img src="../images/wdrtchv.gif"> and <I>Y = </I><img src="../images/lftwdchv.gif"><I>B, D, C, A, B, A</I><img src="../images/wdrtchv.gif">, the sequence <img src="../images/lftwdchv.gif"><I>B, C, A</I><img src="../images/wdrtchv.gif"> is a common subsequence of both <I>X</I> and <I>Y</I>. The sequence <img src="../images/lftwdchv.gif"><I>B, C, A</I><img src="../images/wdrtchv.gif"> is not a <I>longest</I> common subsequence <img src="../images/lftwdchv.gif">LCS<img src="../images/wdrtchv.gif"> of <I>X</I> and <I>Y</I>, however, since it has length 3 and the sequence <img src="../images/lftwdchv.gif"><I>B, C, B, A</I><img src="../images/wdrtchv.gif">, which is also common to both <I>X</I> and <I>Y</I>, has length 4. The sequence <img src="../images/lftwdchv.gif"><I>B, C, B, A</I><img src="../images/wdrtchv.gif"> is an LCS of <I>X</I> and <I>Y,</I> as is the sequence <img src="../images/lftwdchv.gif"><I>B, D, A, B</I><img src="../images/wdrtchv.gif">, since there is no common subsequence of length 5 or greater.<P>
In the <I><B>longest-common-subsequence problem</I></B>, we are given two sequences <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>m</I></SUB><img src="../images/wdrtchv.gif"> and <I>Y</I> = <img src="../images/lftwdchv.gif"><I>y</I><SUB>1,</SUB> <I>y</I><SUB>2</SUB>, . . . , <I>y</I><SUB>n</SUB><img src="../images/wdrtchv.gif"> and wish to find a maximum-length common subsequence of <I>X</I> and <I>Y</I>. This section shows that the LCS problem can be solved efficiently using dynamic programming.<P>