Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 65
Текст из файла (страница 65)
Specifically, we shall showthat T (n) ≥ 2n-1 for all n ≥ 1. The basis is easy, since T (1) ≥ 1 = 20. Inductively, for n ≥ 2 wehavewhich completes the proof. Thus, the total amount of work performed by the callRECURSIVE-MATRIX-CHAIN(p, 1, n) is at least exponential in n.Compare this top-down, recursive algorithm with the bottom-up, dynamic-programmingalgorithm. The latter is more efficient because it takes advantage of the overlappingsubproblems property.
There are only Θ(n2) different subproblems, and the dynamicprogramming 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 samesubproblem repeatedly, and the total number of different subproblems is small, it is a goodidea to see if dynamic programming can be made to work.Reconstructing an optimal solutionAs a practical matter, we often store which choice we made in each subproblem in a table sothat we do not have to reconstruct this information from the costs that we stored.
In assemblyline scheduling, we stored in li [j] the station preceding Si,j in a fastest way through Si,j .Alternatively, having filled in the entire fi[j] table, we could determine which station precedesS1,j in a fastest way through Si,j with a little extra work. If f1[j] = f1[j - 1] + a1, j, then station S1, j-1 precedes S1, j in a fastest way through S1, j. Otherwise, it must be the case that f1[j] = f2[j - 1]+ t2, j -1 + a1, j, and so S2, j - 1 precedes S1, j. For assembly-line scheduling, reconstructing thepredecessor stations takes only O(1) time per station, even without the li[j] table.For matrix-chain multiplication, however, the table s[i, j] saves us a significant amount ofwork when reconstructing an optimal solution. Suppose that we did not maintain the s[i, j]table, having filled in only the table m[i, j] containing optimal subproblem costs. There are j i choices in determining which subproblems to use in an optimal solution to parenthesizing AiAi+1 Aj, and j - i is not a constant.
Therefore, it would take Θ(j - i) = ω(1) time to reconstructwhich subproblems we chose for a solution to a given problem. By storing in s[i, j] the indexof the matrix at which we split the product Ai Ai+1 Aj, we can reconstruct each choice in O(1)time.MemoizationThere is a variation of dynamic programming that often offers the efficiency of the usualdynamic-programming approach while maintaining a top-down strategy. The idea is tomemoize the natural, but inefficient, recursive algorithm. As in ordinary dynamicprogramming, we maintain a table with subproblem solutions, but the control structure forfilling in the table is more like the recursive algorithm.A memoized recursive algorithm maintains an entry in a table for the solution to eachsubproblem. Each table entry initially contains a special value to indicate that the entry hasyet to be filled in.
When the subproblem is first encountered during the execution of therecursive algorithm, its solution is computed and then stored in the table. Each subsequenttime that the subproblem is encountered, the value stored in the table is simply looked up andreturned.[4]Here is a memoized version of RECURSIVE-MATRIX-CHAIN:MEMOIZED-MATRIX-CHAIN(p)1 n ← length[p] - 12 for i ← 1 to n3do for j ← i to n4do m[i, j] ← ∞5 return LOOKUP-CHAIN(p, 1, n)LOOKUP-CHAIN(p, i, j)1 if m[i, j] < ∞2then return m[i, j]3 if i = j4then m[i, j] ← 05else for k ← i to j - 16do q ← LOOKUP-CHAIN(p, i, k)+ LOOKUP-CHAIN(p,k + 1, j) + pi-1 pk pj7if q < m[i, j]8then m[i, j] ← q9 return m[i, j]MEMOIZED-MATRIX-CHAIN, like MATRIX-CHAIN-ORDER, maintains a table m[1 n,1 n] of computed values of m[i, j], the minimum number of scalar multiplications needed tocompute the matrix Ai j.
Each table entry initially contains the value ∞ to indicate that theentry has yet to be filled in. When the call LOOKUP-CHAIN(p, i, j) is executed, if m[i, j] < ∞in line 1, the procedure simply returns the previously computed cost m[i, j] (line 2).Otherwise, the cost is computed as in RECURSIVE-MATRIX-CHAIN, stored in m[i, j], andreturned. (The value ∞ is convenient to use for an unfilled table entry since it is the value usedto initialize m[i, j] in line 3 of RECURSIVE-MATRIX-CHAIN.) Thus, LOOKUP-CHAIN(p,i, j) always returns the value of m[i, j], but it computes it only if this is the first time thatLOOKUP-CHAIN has been called with the parameters i and j.Figure 15.5 illustrates how MEMOIZED-MATRIX-CHAIN saves time compared toRECURSIVE-MATRIX-CHAIN.
Shaded subtrees represent values that are looked up ratherthan computed.Like the dynamic-programming algorithm MATRIX-CHAIN-ORDER, the procedureMEMOIZED-MATRIX-CHAIN runs in O(n3) time. Each of Θ(n2) table entries is initializedonce in line 4 of MEMOIZED-MATRIX-CHAIN. We can categorize the calls of LOOKUPCHAIN into two types:1. calls in which m[i, j] = ∞, so that lines 3–9 are executed, and2. calls in which m[i, j] < ∞, so that LOOKUP-CHAIN simply returns in line 2.There are Θ(n2) calls of the first type, one per table entry.
All calls of the second type aremade as recursive calls by calls of the first type. Whenever a given call of LOOKUP-CHAINmakes recursive calls, it makes O(n) of them. Therefore, there are O(n3) calls of the secondtype in all. Each call of the second type takes O(1) time, and each call of the first type takesO(n) time plus the time spent in its recursive calls. The total time, therefore, is O(n3).Memoization thus turns an Ω(2n)-time algorithm into an O(n3)-time algorithm.In summary, the matrix-chain multiplication problem can be solved by either a top-down,memoized algorithm or a bottom-up, dynamic-programming algorithm in O(n3) time. Bothmethods take advantage of the overlapping-subproblems property.
There are only Θ(n2)different subproblems in total, and either of these methods computes the solution to eachsubproblem once. Without memoization, the natural recursive algorithm runs in exponentialtime, since solved subproblems are repeatedly solved.In general practice, if all subproblems must be solved at least once, a bottom-up dynamicprogramming algorithm usually outperforms a top-down memoized algorithm by a constantfactor, 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 thedynamic-programming algorithm can be exploited to reduce time or space requirements evenfurther.
Alternatively, if some subproblems in the subproblem space need not be solved at all,the memoized solution has the advantage of solving only those subproblems that are definitelyrequired.Exercises 15.3-1Which is a more efficient way to determine the optimal number of multiplications in a matrixchain multiplication problem: enumerating all the ways of parenthesizing the product andcomputing the number of multiplications for each, or running RECURSIVE-MATRIXCHAIN? Justify your answer.Exercises 15.3-2Draw the recursion tree for the MERGE-SORT procedure from Section 2.3.1 on an array of16 elements.
Explain why memoization is ineffective in speeding up a good divide-andconquer algorithm such as MERGE-SORT.Exercises 15.3-3Consider a variant of the matrix-chain multiplication problem in which the goal is toparenthesize the sequence of matrices so as to maximize, rather than minimize, the number ofscalar multiplications. Does this problem exhibit optimal substructure?Exercises 15.3-4Describe how assembly-line scheduling has overlapping subproblems.Exercises 15.3-5As stated, in dynamic programming we first solve the subproblems and then choose which ofthem to use in an optimal solution to the problem. Professor Capulet claims that it is notalways necessary to solve all the subproblems in order to find an optimal solution.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
