chap16.htm

介绍算法的书籍

<pre>5     <B>else return</B> <I>A<SUB>i</I></sub></sup></pre><P>
In the example of Figure 16.1, the call <FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>-<FONT FACE="Courier New" SIZE=2>MULTIPLY<I>(A, s, </I></FONT>1, 6) computes the matrix-chain product according to the parenthesization<P>
<pre>((<I>A</I><SUB>1</SUB>(<I>A</I><SUB>2</SUB><I>A</I><SUB>3</SUB>))((<I>A</I><SUB>4</SUB><I>A</I><SUB>5</SUB>)<I>A</I><SUB>6</SUB>)) .</sub></sup></pre><P>
<h4><a name="0810_153c">(16.3)<a name="0810_153c"></sub></sup></h4><P>
<P>







<h2><a name="0811_153d">Exercises<a name="0811_153d"></h2><P>
<a name="0811_153e">16.1-1<a name="0811_153e"><P>
Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <img src="../images/lftwdchv.gif">5, 10, 3, 12, 5, 50, 6<img src="../images/wdrtchv.gif">.<P>
<a name="0811_153f">16.1-2<a name="0811_153f"><P>
<a name="0811_153c">Give an efficient algorithm <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-<FONT FACE="Courier New" SIZE=2>OPTIMAL</FONT>-<FONT FACE="Courier New" SIZE=2>PARENS</FONT> to print the optimal parenthesization of a matrix chain given the table <I>s</I> computed by <FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>-<FONT FACE="Courier New" SIZE=2>ORDER</FONT>. Analyze your algorithm.<P>
<a name="0811_1540">16.1-3<a name="0811_1540"><P>
Let <I>R</I>(<I>i, j</I>) be the number of times that table entry <I>m</I>[<I>i, j</I>] is referenced by <FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>-<FONT FACE="Courier New" SIZE=2>ORDER</FONT> in computing other table entries. Show that the total number of references for the entire table is<P>
<img src="309_a.gif"><P>
(<I>Hint</I>: You may find the identity <img src="309_b.gif"><P>
<a name="0811_1541">16.1-4<a name="0811_1541"><P>
Show that a full parenthesization of an <I>n</I>-element expression has exactly <I>n</I> - 1 pairs of parentheses.<P>
<P>


<P>







<h1><a name="0812_153e">16.2 Elements of dynamic programming<a name="0812_153e"></h1><P>
<a name="0812_153d">Although we have just worked through an example of the dynamic-programming method, you might still be wondering just when the method applies. From an engineering perspective, when should we look for a dynamic-programming solution to a problem? In this section, we examine the two key ingredients that an optimization problem must have for dynamic programming to be applicable: optimal substructure and overlapping subproblems. We also look at a variant method, called memoization, for taking advantage of the overlapping-subproblems property.<P>





<h2>Optimal substructure</h2><P>
<a name="0813_153e"><a name="0813_153f">The first step in solving an optimization problem by dynamic programming is to characterize the structure of an optimal solution. We say that a problem exhibits <I><B>optimal substructure</I></B><I> </I>if an optimal solution to the problem contains within it optimal solutions to subproblems. Whenever a problem exhibits optimal substructure, it is a good clue that dynamic programming might apply. (It also might mean that a greedy strategy applies, however. See Chapter 17.)<P>
In Section 16.1, we discovered that the problem of matrix-chain multiplication exhibits optimal substructure. We observed that an optimal parenthesization of <I>A</I><SUB>1<I> </SUB>A</I><SUB>2 </SUB><img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"><SUB> </SUB><I>A<SUB>n</SUB> </I>that splits the product between <I>A<SUB>k</SUB> </I>and <I>A<SUB>k </I>+ 1 </SUB>contains within it optimal solutions to the problems of parenthesizing <I>A</I><SUB>1</SUB><I>A</I><SUB>2</SUB> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <I>A <SUB>k</SUB> and A<SUB>k + </I>1</SUB><I>A<SUB>k +</I> 2</SUB><I>. . . A<SUB>n</I>. </SUB>The technique that we used to show that subproblems have optimal solutions is typical. We assume that there is a better solution to the subproblem and show how this assumption contradicts the optimality of the solution to the original problem.<P>
The optimal substructure of a problem often suggests a suitable space of subproblems to which dynamic programming can be applied. Typically, there are several classes of subproblems that might be considered "natural" for a problem. For example, the space of subproblems that we considered for matrix-chain multiplication contained all subchains of the input chain. We could equally well have chosen as our space of subproblems arbitrary sequences of matrices from the input chain, but this space of subproblems is unnecessarily large. A dynamic-programming algorithm based on this space of subproblems solves many more problems than it has to.<P>
Investigating the optimal substructure of a problem by iterating on subproblem instances is a good way to infer a suitable space of subproblems for dynamic programming. For example, after looking at the structure of an optimal solution to a matrix-chain problem, we might iterate and look at the structure of optimal solutions to subproblems, subsubproblems, and so forth. We discover that all subproblems consist of subchains of <img src="../images/lftwdchv.gif"><I>A</I><SUB>l</SUB>, <I>A</I><SUB>2</SUB>, . . . , <I>A<SUB>n</I></SUB><img src="../images/wdrtchv.gif">. Thus, the set of chains of the form <img src="../images/lftwdchv.gif"><I>A<SUB>i</I></SUB>, <I>A<SUB>j</I>+l</SUB>, . . . , <I>A<SUB>j</I></SUB><img src="../images/wdrtchv.gif"> for 1 <img src="../images/lteq12.gif"> <I>i</I> <img src="../images/lteq12.gif"> <I>j</I> <img src="../images/lteq12.gif"> <I>n</I> makes a natural and reasonable space of subproblems to use.<P>
<P>







<h2>Overlapping subproblems</h2><P>
<a name="0814_1540"><a name="0814_1541">The second ingredient that an optimization problem must have for dynamic programming to be applicable is that the space of subproblems must be &quot;small&quot; in the sense that a recursive algorithm for the problem solves the same subproblems over and over, rather than always generating new subproblems. Typically, the total number of distinct subproblems is a polynomial in the input size. When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has <I><B>overlapping subproblems</I></B>. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion. Dynamic-programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing the solution in a table where it can be looked up when needed, using constant time per lookup.<P>
To illustrate the overlapping-subproblems property, let us reexamine the matrix-chain multiplication problem. Referring back to Figure 16.1, observe that <FONT FACE="Courier New" SIZE=2>MATRIX</FONT>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT>-<FONT FACE="Courier New" SIZE=2>ORDER</FONT> repeatedly looks up the solution to subproblems in lower rows when solving subproblems in higher rows. For example, entry <I>m</I>[3, 4] is referenced 4 times: during the computations of <I>m</I>[2, 4], <I>m</I>[1, 4], <I>m</I>[3, 5], and <I>m</I>[3, 6]. If <I>m</I>[3, 4] were recomputed each time, rather than just being looked up, the increase in running time would be dramatic. To see this, consider the following (inefficient) recursive procedure that determines <I>m</I>[<I>i, j</I>], the minimum number of scalar multiplications needed to compute the matrix-chain product <I>A<SUB>i..j</I></SUB> = <I>A<SUB>i</SUB>A<SUB>i </I>+ 1</SUB>, . . . <I>A<SUB>j</I></SUB>. The procedure is based directly on the recurrence (16.2).<P>
<img src="311_a.gif"><P>
<h4><a name="0814_1543">Figure 16.2 The recursion tree for the computation of <FONT FACE="Courier New" SIZE=2>RECURSIVE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>MATRIX<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT></FONT></FONT></FONT></FONT>(p, 1, 4). Each node contains the parameters i and j. The computations performed in a shaded subtree are replaced by a single table lookup in <FONT FACE="Courier New" SIZE=2>MEMOIZED<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>MATRIX<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>CHAIN</FONT></FONT></FONT></FONT></FONT>(p, 1, 4).<a name="0814_1543"></sub></sup></h4><P>
<pre><a name="0814_1542">RECURSIVE-MATRIX-CHAIN(<I>p, i, j</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>i</I> =<I> j</I></sub></sup></pre><P>
<pre>2     <B>then return</B> 0</sub></sup></pre><P>
<pre>3 <I>m</I>[<I>i, j</I>] <img src="../images/arrlt12.gif"> <img src="../images/infin.gif"></sub></sup></pre><P>
<pre>4 <B>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>5      <B>do</B> <I>q</I> <img src="../images/arrlt12.gif"> RECURSIVE-MATRIX-CHAIN(<I>p, i, k</I>)</sub></sup></pre><P>
<pre>+ RECURSIVE-MATRIX-CHAIN(<I>p, k + </I>1<I>, j</I>) + <I>p<SUB>i-</I>1</SUB><I>p<SUB>k</SUB>p<SUB>j</I></sub></sup></pre><P>
<pre>6         <B>if</B> <I>q</I> &lt; <I>m</I>[<I>i, j</I>]</sub></sup></pre><P>
<pre>7            <B>then</B> <I>m</I>[<I>i, j</I>] <img src="../images/arrlt12.gif"> <I>q</I></sub></sup></pre><P>
<pre>8 <B>return</B> <I>m</I>[<I>i, j</I>]</sub></sup></pre><P>
Figure 16.2 shows the recursion tree produced 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, 4). Each node is labeled by the values of the parameters <I>i</I> and <I>j</I>. Observe that some pairs of values occur many times.<P>
In fact, we can show that the running time <I>T</I>(<I>n</I>) to compute <I>m</I>[1<I>, n</I>] by this recursive procedure is at least exponential in <I>n</I>. Let us assume that the execution of lines 1-2 and of lines 6-7 each take at least unit time. Inspection of the procedure yields the recurrence<P>
<img src="311_b.gif"><P>
Noting that for <I>i</I> = 1, 2, . . . , <I>n</I> - 1, each term <I>T</I>(<I>i</I>) appears once as <I>T</I>(<I>k</I>) and once as <I>T</I>(<I>n - k</I>), and collecting the <I>n</I> - 1 1's in the summation together with the 1 out front, we can rewrite the recurrence as<P>
<img src="311_c.gif"><P>