📄 chap16.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 16: DYNAMIC PROGRAMMING</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap17.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="partiv.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0809_1533">CHAPTER 16: DYNAMIC PROGRAMMING<a name="0809_1533"></h1><P>
<a name="0809_152f"><a name="0809_1530">Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. ("Programming" in this context refers to a tabular method, not to writing computer code.) As we saw in Chapter 1, divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subsubproblem is encountered.<P>
<a name="0809_1531"><a name="0809_1532">Dynamic programming is typically applied to <I><B>optimization problems</I></B><I>. </I>In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution <I>an</I> optimal solution to the problem, as opposed to <I>the</I> optimal solution, since there may be several solutions that achieve the optimal value.<P>
The development of a dynamic-programming algorithm can be broken into a sequence of four steps.<P>
1. Characterize the structure of an optimal solution.<P>
2. Recursively define the value of an optimal solution.<P>
3. Compute the value of an optimal solution in a bottom-up fashion.<P>
4. Construct an optimal solution from computed information.<P>
Steps 1-3 form the basis of a dynamic-programming solution to a problem. Step 4 can be omitted if only the value of an optimal solution is required. When we do perform step 4, we sometimes maintain additional information during the computation in step 3 to ease the construction of an optimal solution.<P>
The sections that follow use the dynamic-programming method to solve some optimization problems. Section 16.1 asks how we can multiply a chain of matrices so that the fewest total scalar multiplications are performed. Given this example of dynamic programming, Section 16.2 discusses two key characteristics that a problem must have for dynamic programming to be a viable solution technique. Section 16.3 then shows how to find the longest common subsequence of two sequences. Finally, Section 16.4 uses dynamic programming to find an optimal triangulation of a convex polygon, a problem that is surprisingly similar to matrix-chain multiplication.<P>
<h1><a name="080b_1538">16.1 Matrix-chain multiplication<a name="080b_1538"></h1><P>
<a name="080b_1533"><a name="080b_1534">Our first example of dynamic programming is an algorithm that solves the problem of matrix-chain multiplication. We are given a sequence (chain) <img src="../images/lftwdchv.gif"><I>A<SUB>1</SUB>, A<SUB>2</SUB>, . . ., A<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> of <I>n</I> matrices to be multiplied, and we wish to compute the product<P>
<pre><I>A</I><SUB>1</SUB><I>A</I><SUB>2</SUB><SUP> </SUP><img src="../images/dot10.gif"> <SUP><img src="../images/dot10.gif"> </SUP><img src="../images/dot10.gif"><SUP><I>A<SUB>n </SUB>.</I></sub></sup></pre><P>
<h4><a name="080b_1539">(16.1)<a name="080b_1539"></sub></sup></h4><P>
<a name="080b_1535"><a name="080b_1536">We can evaluate the expression (16.1) using the standard algorithm for multiplying pairs of matrices as a subroutine once we have parenthesized it to resolve all ambiguities in how the matrices are multiplied together. A product of matrices is <I><B>fully parenthesized </I></B>if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses. Matrix multiplication is associative, and so all parenthesizations yield the same product. For example, if the chain of matrices is <img src="../images/lftwdchv.gif"><I>A</I><SUB>1</SUB>, <I>A</I><SUB>2</SUB>, <I>A</I><SUB>3</SUB>, <I>A</I><SUB>4</SUB><img src="../images/wdrtchv.gif">, the product <I>A</I><SUB>1</SUB><I>A</I><SUB>2</SUB><I>A</I><SUB>3</SUB><I>A</I><SUB>4</SUB> can be fully parenthesized in five distinct ways:<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>))) ,</sub></sup></pre><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>)) ,</sub></sup></pre><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>)) ,</sub></sup></pre><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>) ,</sub></sup></pre><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>) .</sub></sup></pre><P>
The way we parenthesize a chain of matrices can have a dramatic impact on the cost of evaluating the product. Consider first the cost of multiplying two matrices. The standard algorithm is given by the following pseudocode. The attributes <I>rows</I> and <I>columns</I> are the numbers of rows and columns in a matrix.<P>
<pre><a name="080b_1537">MATRIX-MULTIPLY(<I>A</I>,<I>B</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>columns </I>[<I>A</I>] <img src="../images/noteq.gif"> rows <I>[</I>B<I>]</I></sub></sup></pre><P>
<pre>2 <B>then error</B> "incompatible dimensions"</sub></sup></pre><P>
<pre>3 <B>else for </B><I>i </I><img src="../images/arrlt12.gif">1 <I><B>to</B></I> rows <I>[</I>A<I>]</I></sub></sup></pre><P>
<pre>4 <B>do for</B> <I>j</I> <img src="../images/arrlt12.gif">1 <B>to</B> <I>columns</I>[<I>B</I>]</sub></sup></pre><P>
<pre>5 <B>do</B> <I>C</I>[<I>i, j</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>6 <B>for</B><I> k </I><img src="../images/arrlt12.gif"> <I>1</I> <I><B>to</B></I> columns <I>[</I>A<I>]</I></sub></sup></pre><P>
<pre><I>7 </I><B>do</B><I> C</I>[<I>i ,j</I>] <img src="../images/arrlt12.gif"> C<I>[</I>i ,j<I>]</I> + A <I>[</I>i, k<I>] </I>B<I>[</I>k, j<I>]</I></sub></sup></pre><P>
<pre>8 <B>return</B><I> C</I></sub></sup></pre><P>
We can multiply two matrices <I>A</I> and <I>B</I> only if the number of columns of <I>A </I>is equal to the number of rows of <I>B</I>. If <I>A</I> is a <I>p</I> X <I>q</I> matrix and <I>B</I> is a <I>q</I> X <I>r</I> matrix, the resulting matrix <I>C</I> is a <I>p</I> X <I>r</I> matrix. The time to compute <I>C</I> is dominated by the number of scalar multiplications in line 7, which is <I>pqr</I>. In what follows, we shall express running times in terms of the number of scalar multiplications.<P>
To illustrate the different costs incurred by different parenthesizations of a matrix product, consider the problem of a chain <img src="../images/lftwdchv.gif"><I>A</I><SUB>1</SUB>, <I>A</I><SUB>2</SUB>, <I>A</I><SUB>3</SUB><img src="../images/wdrtchv.gif"> of three matrices. Suppose that the dimensions of the matrices are 10 X 100,100 <img src="../images/mult.gif"> 5, and 5 <img src="../images/mult.gif"> 50, respectively. If we multiply according to the parenthesization ((<I>A</I><SUB>1</SUB><I>A</I><SUB>2</SUB>)<I>A</I><SUB>3</SUB>), we perform 10 <img src="../images/dot10.gif"> 100 <img src="../images/dot10.gif"> 5 = 5000 scalar multiplications to compute the 10 X 5 matrix product <I>A</I><SUB>1</SUB><I>A</I><SUB>2</SUB>, plus another 10 <img src="../images/dot10.gif"> 5 <img src="../images/dot10.gif"> 50 = 2500 scalar multiplications to multiply this matrix by <I>A</I><SUB>3</SUB>, for a total of 7500 scalar multiplications. If instead we multiply according to the parenthesization (<I>A</I><SUB>1</SUB>(<I>A</I><SUB>2</SUB><I>A</I><SUB>3</SUB>)), we perform 100 <img src="../images/dot10.gif"> 5 <img src="../images/dot10.gif"> 50 = 25,000 scalar multiplications to compute the 100 X 50 matrix product <I>A</I><SUB>2</SUB><I>A</I><SUB>3</SUB>, plus another 10 <img src="../images/dot10.gif"> 100 <img src="../images/dot10.gif"> 50 = 50,000 scalar multiplications to multiply <I>A</I><SUB>1</SUB> by this matrix, for a total of 75,000 scalar multiplications. Thus, computing the product according to the first parenthesization is 10 times faster.<P>
The <I><B>matrix-chain multiplication problem</I></B> can be stated as follows: given a chain <img src="../images/lftwdchv.gif"><I>A</I><SUB>1</SUB>, <I>A</I><SUB>2</SUB>, . . . , <I>A</I><SUB>n</SUB><img src="../images/wdrtchv.gif"> of <I>n</I> matrices, where for <I>i</I> = 1, 2, . . . , <I>n</I> , matrix <I>A<SUB>i </I></SUB>has dimension <I>p<SUB>i </I></SUB>- <SUB>1</SUB> X <I>p<SUB>i</I></SUB>, fully parenthesize the product <I>A</I><SUB>1</SUB> <I>A</I><SUB>2</SUB>...<I>A<SUB>n</I></SUB> in a way that minimizes the number of scalar multiplications.<P>
<h2>Counting the number of parenthesizations</h2><P>
Before solving the matrix-chain multiplication problem by dynamic programming, we should convince ourselves that exhaustively checking all possible parenthesizations does not yield an efficient algorithm. Denote the number of alternative parenthesizations of a sequence of <I>n</I> matrices by <I>P</I>(<I>n</I>). Since we can split a sequence of <I>n</I> matrices between the <I>k</I>th and (<I>k</I> + 1)st matrices for any <I>k</I> = 1, 2, . . . , <I>n</I> -1 and then parenthesize the two resulting subsequences independently, we obtain the recurrence<P>
<img src="304_a.gif"><P>
<a name="080c_1538">Problem 13-4 asked you to show that the solution to this recurrence is the sequence of <I><B>Catalan numbers</I></B>:<P>
<pre><I>P</I>(<I>n</I>) = <I>C</I> (<I>n</I> - 1),</sub></sup></pre><P>
where<P>
<img src="304_b.gif"><P>
The number of solutions is thus exponential in <I>n</I>, and the brute-force method of exhaustive search is therefore a poor strategy for determining the optimal parenthesization of a matrix chain.<P>
<P>
<h2>The structure of an optimal parenthesization </h2><P>
<a name="080d_1539">The first step of the dynamic-programming paradigm is to characterize the structure of an optimal solution. For the matrix-chain multiplication problem, we can perform this step as follows. For convenience, let us adopt the notation <I>A<SUB>i</I>..<I>j</I></SUB> for the matrix that results from evaluating the product <I>A<SUB>i</SUB>A<SUB>i </I>+ 1</SUB> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <I>A<SUB>j</I></SUB>. An optimal parenthesization of the product <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>n </I></SUB>splits the product between <I>A<SUB>k</I></SUB> and <I>A<SUB>k </I>+ 1</SUB> for some integer <I>k</I> in the range 1 <img src="../images/lteq12.gif"> <I>k</I> < <I>n</I> . That is, for some value of <I>k</I>, we first compute the matrices <I>A</I><SUB>1..<I>k</I></SUB> and <I>A<SUB>k </I>+ 1..<I>n</I></SUB> and then multiply them together to produce the final product <I>A</I><SUB>1..<I>n</I></SUB>. The cost of this optimal parenthesization is thus the cost of computing the matrix <I>A</I><SUB>1..<I>k</I></SUB>, plus the cost of computing <I>A<SUB>k </I>+ 1..<I>n</I></SUB>, plus the cost of multiplying them together.<P>
The key observation is that the parenthesization of the "prefix" subchain <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</I></SUB> within this optimal parenthesization of <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>n</I></SUB> must be an <I>optimal</I> parenthesization of <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</I></SUB>. Why? If there were a less costly way to parenthesize <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</I></SUB>, substituting that parenthesization in the optimal parenthesization of <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>n</I></SUB> would produce another parenthesization of <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"> A<I><SUB>n</I></SUB> whose cost was lower than the optimum: a contradiction. A similar observation holds for the the parenthesization of the subchain <I>A<SUB>k</I>+1</SUB><I>A<SUB>k</I>+2</SUB> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <I>A<SUB>n</I></SUB> in the optimal parenthesization of <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>n</I></SUB>: it must be an optimal parenthesization of <I>A<SUB>k</I>+1</SUB><I>A<SUB>k</I>+2</SUB> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <I>A<SUB>n</I></SUB>.<P>
Thus, an optimal solution to an instance of the matrix-chain multiplication problem contains within it optimal solutions to subproblem instances. Optimal substructure within an optimal solution is one of the hallmarks of the applicability of dynamic programming, as we shall see in Section 16.2.<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -