Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 63
Текст из файла (страница 63)
(The initial callwould be MATRIX-CHAIN-MULTIPLY(A, s, 1, n).)Exercises 15.2-3Use the substitution method to show that the solution to the recurrence (15.11) is Ω(2n).Exercises 15.2-4Let R(i, j) be the number of times that table entry m[i, j] is referenced while computing othertable entries in a call of MATRIX-CHAIN-ORDER.
Show that the total number of referencesfor the entire table is(Hint: You may find equation (A.3) useful.)Exercises 15.2-5Show that a full parenthesization of an n-element expression has exactly n - 1 pairs ofparentheses.15.3 Elements of dynamic programmingAlthough we have just worked through two examples 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, weexamine the two key ingredients that an optimization problem must have in order for dynamicprogramming to be applicable: optimal substructure and overlapping subproblems.
We alsolook at a variant method, called memoization,[1] for taking advantage of the overlappingsubproblems property.Optimal substructureThe first step in solving an optimization problem by dynamic programming is to characterizethe structure of an optimal solution. Recall that a problem exhibits optimal substructure if anoptimal solution to the problem contains within it optimal solutions to subproblems.Whenever a problem exhibits optimal substructure, it is a good clue that dynamicprogramming might apply.
(It also might mean that a greedy strategy applies, however. SeeChapter 16.) In dynamic programming, we build an optimal solution to the problem fromoptimal solutions to subproblems. Consequently, we must take care to ensure that the range ofsubproblems we consider includes those used in an optimal solution.We discovered optimal substructure in both of the problems we have examined in this chapterso far. In Section 15.1, we observed that the fastest way through station j of either linecontained within it the fastest way through station j - 1 on one line.
In Section 15.2, weobserved that an optimal parenthesization of Ai Ai+1 Aj that splits the product between Ak andAk+1 contains within it optimal solutions to the problems of parenthesizing Ai Ai+1 Ak and Ak+1Ak+2 Aj.You will find yourself following a common pattern in discovering optimal substructure:1. You show that a solution to the problem consists of making a choice, such as choosinga preceding assembly-line station or choosing an index at which to split the matrixchain. Making this choice leaves one or more subproblems to be solved.2.
You suppose that for a given problem, you are given the choice that leads to anoptimal solution. You do not concern yourself yet with how to determine this choice.You just assume that it has been given to you.3. Given this choice, you determine which subproblems ensue and how to bestcharacterize the resulting space of subproblems.4. You show that the solutions to the subproblems used within the optimal solution to theproblem must themselves be optimal by using a "cut-and-paste" technique.
You do soby supposing that each of the subproblem solutions is not optimal and then deriving acontradiction. In particular, by "cutting out" the nonoptimal subproblem solution and"pasting in" the optimal one, you show that you can get a better solution to the originalproblem, thus contradicting your supposition that you already had an optimal solution.If there is more than one subproblem, they are typically so similar that the cut-andpaste argument for one can be modified for the others with little effort.To characterize the space of subproblems, a good rule of thumb is to try to keep the space assimple as possible, and then to expand it as necessary.
For example, the space of subproblemsthat we considered for assembly-line scheduling was the fastest way from entry into thefactory through stations S1, j and S2, j. This subproblem space worked well, and there was noneed to try a more general space of subproblems.Conversely, suppose that we had tried to constrain our subproblem space for matrix-chainmultiplication to matrix products of the form A1 A2 Aj. As before, an optimal parenthesizationmust split this product between Ak and Ak+1 for some 1 ≤ k ≤ j.
Unless we could guarantee thatk always equals j - 1, we would find that we had subproblems of the form A1 A2 Ak and Ak+1Ak+2 Aj, and that the latter subproblem is not of the form A1 A2 Aj. For this problem, it wasnecessary to allow our subproblems to vary at "both ends," that is, to allow both i and j to varyin the subproblem Ai Ai+1 Aj.Optimal substructure varies across problem domains in two ways:1. how many subproblems are used in an optimal solution to the original problem, and2. how many choices we have in determining which subproblem(s) to use in an optimalsolution.In assembly-line scheduling, an optimal solution uses just one subproblem, but we mustconsider two choices in order to determine an optimal solution. To find the fastest waythrough station Si,j , we use either the fastest way through S1, j -1 or the fastest way through S2, j-1; whichever we use represents the one subproblem that we must optimally solve.
Matrixchain multiplication for the subchain Ai Ai+1 Aj serves as an example with two subproblemsand j - i choices. For a given matrix Ak at which we split the product, we have twosubproblems—parenthesizing Ai Ai+1 Ak and parenthesizing Ak+1 Ak+2 Aj—and we must solveboth of them optimally. Once we determine the optimal solutions to subproblems, we choosefrom among j - i candidates for the index k.Informally, the running time of a dynamic-programming algorithm depends on the product oftwo factors: the number of subproblems overall and how many choices we look at for eachsubproblem. In assembly-line scheduling, we had Θ(n) subproblems overall, and only twochoices to examine for each, yielding a Θ(n) running time. For matrix-chain multiplication,there were Θ(n2) subproblems overall, and in each we had at most n - 1 choices, giving anO(n3) running time.Dynamic programming uses optimal substructure in a bottom-up fashion.
That is, we first findoptimal solutions to subproblems and, having solved the subproblems, we find an optimalsolution to the problem. Finding an optimal solution to the problem entails making a choiceamong subproblems as to which we will use in solving the problem. The cost of the problemsolution is usually the subproblem costs plus a cost that is directly attributable to the choiceitself. In assembly-line scheduling, for example, first we solved the subproblems of findingthe fastest way through stations S1, j -1 and S2, j -1, and then we chose one of these stations as theone preceding station Si, j. The cost attributable to the choice itself depends on whether weswitch lines between stations j - 1 and j; this cost is ai, j if we stay on the same line, and it is ti′,j-1 + ai,j , where i′ ≠ i, if we switch.
In matrix-chain multiplication, we determined optimalparenthesizations of subchains of Ai Ai+1 Aj , and then we chose the matrix Ak at which to splitthe product. The cost attributable to the choice itself is the term pi-1 pk pj.In Chapter 16, we shall examine "greedy algorithms," which have many similarities todynamic programming. In particular, problems to which greedy algorithms apply haveoptimal substructure. One salient difference between greedy algorithms and dynamicprogramming is that in greedy algorithms, we use optimal substructure in a top-down fashion.Instead of first finding optimal solutions to subproblems and then making a choice, greedyalgorithms first make a choice—the choice that looks best at the time—and then solve aresulting subproblem.SubtletiesOne should be careful not to assume that optimal substructure applies when it does not.Consider the following two problems in which we are given a directed graph G = (V, E) andvertices u, v V.••Unweighted shortest path: [2] Find a path from u to v consisting of the fewest edges.Such a path must be simple, since removing a cycle from a path produces a path withfewer edges.Unweighted longest simple path: Find a simple path from u to v consisting of themost edges.
We need to include the requirement of simplicity because otherwise wecan traverse a cycle as many times as we like to create paths with an arbitrarily largenumber of edges.The unweighted shortest-path problem exhibits optimal substructure, as follows. Suppose thatu ≠ v, so that the problem is nontrivial. Then any path p from u to v must contain anintermediate vertex, say w. (Note that w may be u or v.) Thus we can decompose the pathinto subpaths. Clearly, the number of edges in p is equal to the sum of thenumber of edges in p1 and the number of edges in p2. We claim that if p is an optimal (i.e.,shortest) path from u to v, then p1 must be a shortest path from u to w.
Why? We use a "cutand-paste" argument: if there were another path, say , from u to w with fewer edges than p1,then we could cut out p1 and paste in to produce a pathwith fewer edges than p,thus contradicting p's optimality. Symmetrically, p2 must be a shortest path from w to v. Thus,we can find a shortest path from u to v by considering all intermediate vertices w, finding ashortest path from u to w and a shortest path from w to v, and choosing an intermediate vertexw that yields the overall shortest path. In Section 25.2, we use a variant of this observation ofoptimal substructure to find a shortest path between every pair of vertices on a weighted,directed graph.It is tempting to assume that the problem of finding an unweighted longest simple pathexhibits optimal substructure as well.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
