Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 61
Текст из файла (страница 61)
Lines 1–2 compute f1[1] and f2[1] using equations (15.2)and (15.3). Then the for loop of lines 3–13 computes fi[j] and li[j] for i = 1, 2 and j = 2, 3, ...,n. Lines 4–8 compute f1[j] and l1[j] using equation (15.4), and lines 9–13 compute f2[j] andl2[j] using equation (15.5).
Finally, lines 14–18 compute f* and l* using equation (15.1).Because lines 1–2 and 14–18 take constant time and each of the n - 1 iterations of the for loopof lines 3–13 takes constant time, the entire procedure takes Θ(n) time.One way to view the process of computing the values of fi[j] and li [j] is that we are filling intable entries. Referring to Figure 15.2(b), we fill tables containing values fi[j] and li[j] fromleft to right (and top to bottom within each column).
To fill in an entry fi[j], we need thevalues of f1[j - 1] and f2[j - 1] and, knowing that we have already computed and stored them,we determine these values simply by looking them up in the table.Step 4: Constructing the fastest way through the factoryHaving computed the values of fi[j], f*, li[j], and l*, we need to construct the sequence ofstations used in the fastest way through the factory. We discussed above how to do so in theexample of Figure 15.2.The following procedure prints out the stations used, in decreasing order of station number.Exercise 15.1-1 asks you to modify it to print them in increasing order of station number.PRINT-STATIONS(l, n)12345i ← l*print "line " i ", station " nfor j ← n downto 2do i ← li[j]print "line " i ", station " j - 1In the example of Figure 15.2, PRINT-STATIONS would produce the outputline 1, station 6line 2, station 5line 2, station 4line 1, station 3line 2, station 2line 1, station 1Exercises 15.1-1Show how to modify the PRINT-STATIONS procedure to print out the stations in increasingorder of station number.
(Hint: Use recursion.)Exercises 15.1-2Use equations (15.8) and (15.9) and the substitution method to show that ri(j), the number ofreferences made to fi[j] in a recursive algorithm, equals 2n - j.Exercises 15.1-3Using the result of Exercise 15.1-2, show that the total number of references to all fi[j] values,or, is exactly 2n+1 - 2.Exercises 15.1-4Together, the tables containing fi[j] and li[j] values contain a total of 4n - 2 entries. Show howto reduce the space requirements to a total of 2n + 2 entries, while still computing f* and stillbeing able to print all the stations on a fastest way through the factory.Exercises 15.1-5Professor Canty conjectures that there might exist some ei, ai,j, and ti,j values for whichFASTEST-WAY produces li[j] values such that l1[j] = 2 and l2[j] = 1 for some station numberj.
Assuming that all transfer costs ti,j are nonnegative, show that the professor is wrong.15.2 Matrix-chain multiplicationOur next example of dynamic programming is an algorithm that solves the problem of matrixchain multiplication. We are given a sequence (chain) A1, A2, ..., An of n matrices to bemultiplied, and we wish to compute the product(15.10)We can evaluate the expression (15.10) using the standard algorithm for multiplying pairs ofmatrices as a subroutine once we have parenthesized it to resolve all ambiguities in how thematrices are multiplied together.
A product of matrices is fully parenthesized if it is either asingle matrix or the product of two fully parenthesized matrix products, surrounded byparentheses. Matrix multiplication is associative, and so all parenthesizations yield the sameproduct. For example, if the chain of matrices is A1, A2, A3, A4 , the product A1 A2 A3 A4 canbe fully parenthesized in five distinct ways:(A1 (A2 (A3 A4))) ,(A1 ((A2 A3) A4)) ,((A1 A2) (A3 A4)) ,((A1 (A2 A3)) A4) ,(((A1 A2) A3) A4).The way we parenthesize a chain of matrices can have a dramatic impact on the cost ofevaluating the product.
Consider first the cost of multiplying two matrices. The standardalgorithm is given by the following pseudocode. The attributes rows and columns are thenumbers of rows and columns in a matrix.MATRIX-MULTIPLY(A, B)1 if columns[A] ≠ rows[B]2then error "incompatible dimensions"3else for i ← 1 to rows[A]4do for j ← 1 to columns[B]5do C[i, j] ← 06for k ← 1 to columns[A]7do C[i, j] ← C[i, j] + A[i, k] · B[k, j]8return CWe can multiply two matrices A and B only if they are compatible: the number of columns ofA must equal the number of rows of B. If A is a p × q matrix and B is a q × r matrix, theresulting matrix C is a p × r matrix. The time to compute C is dominated by the number ofscalar multiplications in line 7, which is pqr.
In what follows, we shall express costs in termsof the number of scalar multiplications.To illustrate the different costs incurred by different parenthesizations of a matrix product,consider the problem of a chain A1, A2, A3 of three matrices.
Suppose that the dimensionsof the matrices are 10 × 100, 100 × 5, and 5 × 50, respectively. If we multiply according to theparenthesization ((A1 A2) A3), we perform 10 · 100 · 5 = 5000 scalar multiplications tocompute the 10 × 5 matrix product A1 A2, plus another 10 · 5 · 50 = 2500 scalarmultiplications to multiply this matrix by A3, for a total of 7500 scalar multiplications. Ifinstead we multiply according to the parenthesization (A1 (A2 A3)), we perform 100 · 5 · 50 =25,000 scalar multiplications to compute the 100 × 50 matrix product A2 A3, plus another 10 ·100 · 50 = 50,000 scalar multiplications to multiply A1 by this matrix, for a total of 75,000scalar multiplications.
Thus, computing the product according to the first parenthesization is10 times faster.The matrix-chain multiplication problem can be stated as follows: given a chain A1, A2, ...,An of n matrices, where for i = 1, 2, ..., n, matrix Ai has dimension pi-1 × pi, fullyparenthesize the product A1 A2 An in a way that minimizes the number of scalarmultiplications.Note that in the matrix-chain multiplication problem, we are not actually multiplyingmatrices. Our goal is only to determine an order for multiplying matrices that has the lowestcost. Typically, the time invested in determining this optimal order is more than paid for bythe time saved later on when actually performing the matrix multiplications (such asperforming only 7500 scalar multiplications instead of 75,000).Counting the number of parenthesizationsBefore solving the matrix-chain multiplication problem by dynamic programming, let usconvince ourselves that exhaustively checking all possible parenthesizations does not yield anefficient algorithm.
Denote the number of alternative parenthesizations of a sequence of nmatrices by P(n). When n = 1, there is just one matrix and therefore only one way to fullyparenthesize the matrix product. When n ≥ 2, a fully parenthesized matrix product is theproduct of two fully parenthesized matrix subproducts, and the split between the twosubproducts may occur between the kth and (k + 1)st matrices for any k = 1, 2, ..., n - 1. Thus,we obtain the recurrence(15.11)Problem 12-4 asked you to show that the solution to a similar recurrence is the sequence ofCatalan numbers, which grows as Ω(4n/n3/2). A simpler exercise (see Exercise 15.2-3) is toshow that the solution to the recurrence (15.11) is Ω(2n).
The number of solutions is thusexponential in n, and the brute-force method of exhaustive search is therefore a poor strategyfor determining the optimal parenthesization of a matrix chain.Step 1: The structure of an optimal parenthesizationOur first step in the dynamic-programming paradigm is to find the optimal substructure andthen use it to construct an optimal solution to the problem from optimal solutions tosubproblems.
For the matrix-chain multiplication problem, we can perform this step asfollows. For convenience, let us adopt the notation Ai j, where i ≤ j, for the matrix that resultsfrom evaluating the product Ai Ai+1 Aj. Observe that if the problem is nontrivial, i.e., i < j, thenany parenthesization of the product Ai Ai+1 Aj must split the product between Ak and Ak+1 forsome integer k in the range i ≤ k < j. That is, for some value of k, we first compute thematrices Ai k and Ak+1 j and then multiply them together to produce the final product Ai j. Thecost of this parenthesization is thus the cost of computing the matrix Ai k, plus the cost ofcomputing Ak+1 j, plus the cost of multiplying them together.The optimal substructure of this problem is as follows.
Suppose that an optimalparenthesization of Ai Ai+1 Aj splits the product between Ak and Ak+1. Then the parenthesizationof the "prefix" subchain Ai Ai+1 Ak within this optimal parenthesization of Ai Ai+1 Aj must be anoptimal parenthesization of Ai Ai+1 Ak. Why? If there were a less costly way to parenthesize AiAi+1 Ak, substituting that parenthesization in the optimal parenthesization of Ai Ai+1 Aj wouldproduce another parenthesization of Ai Ai+1 Aj whose cost was lower than the optimum: acontradiction. A similar observation holds for the parenthesization of the subchain Ak+1 Ak+2 Ajin the optimal parenthesization of Ai Ai+1 Aj: it must be an optimal parenthesization of Ak+1Ak+2 Aj.Now we use our optimal substructure to show that we can construct an optimal solution to theproblem from optimal solutions to subproblems.
We have seen that any solution to anontrivial instance of the matrix-chain multiplication problem requires us to split the product,and that any optimal solution contains within it optimal solutions to subproblem instances.Thus, we can build an optimal solution to an instance of the matrix-chain multiplicationproblem by splitting the problem into two subproblems (optimally parenthesizing Ai Ai+1 Akand Ak+1 Ak+2 Aj), finding optimal solutions to subproblem instances, and then combining theseoptimal subproblem solutions. We must ensure that when we search for the correct place tosplit the product, we have considered all possible places so that we are sure of havingexamined the optimal one.Step 2: A recursive solutionNext, we define the cost of an optimal solution recursively in terms of the optimal solutions tosubproblems.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
