Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 64
Текст из файла (страница 64)
After all, if we decompose a longest simple pathinto subpaths, then mustn't p1 be a longest simple path from u to w, and mustn't p2 bea longest simple path from w to v? The answer is no! Figure 15.4 gives an example. Considerthe path q → r → t, which is a longest simple path from q to t.
Is q → r a longest simple pathfrom q to r? No, for the path q → s → t → r is a simple path that is longer. Is r → t a longestsimple path from r to t? No again, for the path r → q → s → t is a simple path that is longer.Figure 15.4: A directed graph showing that the problem of finding a longest simple path in anunweighted directed graph does not have optimal substructure. The path q → r → t is alongest simple path from q to t, but the subpath q → r is not a longest simple path from q to r,nor is the subpath r → t a longest simple path from r to t.This example shows that for longest simple paths, not only is optimal substructure lacking,but we cannot necessarily assemble a "legal" solution to the problem from solutions tosubproblems.
If we combine the longest simple paths q → s → t → r and r → q → s → t, weget the path q → s → t → r → q → s → t, which is not simple. Indeed, the problem of findingan unweighted longest simple path does not appear to have any sort of optimal substructure.No efficient dynamic-programming algorithm for this problem has ever been found. In fact,this problem is NP-complete, which—as we shall see in Chapter 34—means that it is unlikelythat it can be solved in polynomial time.What is it about the substructure of a longest simple path that is so different from that of ashortest path? Although two subproblems are used in a solution to a problem for both longestand shortest paths, the subproblems in finding the longest simple path are not independent,whereas for shortest paths they are.
What do we mean by subproblems being independent?We mean that the solution to one subproblem does not affect the solution to anothersubproblem of the same problem. For the example of Figure 15.4, we have the problem offinding a longest simple path from q to t with two subproblems: finding longest simple pathsfrom q to r and from r to t. For the first of these subproblems, we choose the path q → s → t→ r, and so we have also used the vertices s and t.
We can no longer use these vertices in thesecond subproblem, since the combination of the two solutions to subproblems would yield apath that is not simple. If we cannot use vertex t in the second problem, then we cannot solveit all, since t is required to be on the path that we find, and it is not the vertex at which we are"splicing" together the subproblem solutions (that vertex being r). Our use of vertices s and tin one subproblem solution prevents them from being used in the other subproblem solution.We must use at least one of them to solve the other subproblem, however, and we must useboth of them to solve it optimally.
Thus we say that these subproblems are not independent.Looked at another way, our use of resources in solving one subproblem (those resources beingvertices) has rendered them unavailable for the other subproblem.Why, then, are the subproblems independent for finding a shortest path? The answer is that bynature, the subproblems do not share resources. We claim that if a vertex w is on a shortestpath p from u to v, then we can splice together any shortest pathand any shortest pathto produce a shortest path from u to v. We are assured that, other than w, no vertex canappear in both paths p1 and p2.
Why? Suppose that some vertex x ≠ w appears in both p1 andp2, so that we can decompose p1 asand p2 as. By the optimal substructureof this problem, path p has as many edges as p1 and p2 together; let's say that p has e edges.Now let us construct a pathfrom u to v. This path has at most e - 2 edges, whichcontradicts the assumption that p is a shortest path.
Thus, we are assured that the subproblemsfor the shortest-path problem are independent.Both problems examined in Sections 15.1 and 15.2 have independent subproblems. In matrixchain multiplication, the subproblems are multiplying subchains AiAi+1 Ak and Ak+1Ak+2 Aj.These subchains are disjoint, so that no matrix could possibly be included in both of them. Inassembly-line scheduling, to determine the fastest way through station Si,j, we look at thefastest ways through stations S1,j-1 and S2,j-1. Because our solution to the fastest way throughstation Si, j will include just one of these subproblem solutions, that subproblem isautomatically independent of all others used in the solution.Overlapping subproblemsThe second ingredient that an optimization problem must have for dynamic programming tobe applicable is that the space of subproblems must be "small" in the sense that a recursivealgorithm for the problem solves the same subproblems over and over, rather than alwaysgenerating new subproblems.
Typically, the total number of distinct subproblems is apolynomial in the input size. When a recursive algorithm revisits the same problem over andover again, we say that the optimization problem has overlapping subproblems.[3] In contrast,a problem for which a divide-and-conquer approach is suitable usually generates brand-newproblems at each step of the recursion. Dynamic-programming algorithms typically takeadvantage of overlapping subproblems by solving each subproblem once and then storing thesolution in a table where it can be looked up when needed, using constant time per lookup.In Section 15.1, we briefly examined how a recursive solution to assembly-line schedulingmakes 2n-j references to fi[j] for j = 1, 2, ..., n.
Our tabular solution takes an exponential-timerecursive algorithm down to linear time.To illustrate the overlapping-subproblems property in greater detail, let us reexamine thematrix-chain multiplication problem. Referring back to Figure 15.3, observe that MATRIXCHAIN-ORDER repeatedly looks up the solution to subproblems in lower rows when solvingsubproblems in higher rows. For example, entry m[3, 4] is referenced 4 times: during thecomputations of m[2, 4], m[1, 4], m[3, 5], and m[3, 6].
If m[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 m[i, j], the minimumnumber of scalar multiplications needed to compute the matrix-chain product Ai j = AiAi+1 ···Aj. The procedure is based directly on the recurrence (15.12).RECURSIVE-MATRIX-CHAIN(p, i, j)1 if i = j2then return 03 m[i, j] ← ∞4 for k ← i to j - 15do q ← RECURSIVE-MATRIX-CHAIN(p, i, k)+ RECURSIVE-MATRIX-CHAIN(p,k + 1, j)+ pi-1 pk pj6if q < m[i, j]7then m[i, j] ← q8 return m[i, j]Figure 15.5 shows the recursion tree produced by the call RECURSIVE-MATRIX-CHAIN(p,1, 4).
Each node is labeled by the values of the parameters i and j. Observe that some pairs ofvalues occur many times.Figure 15.5: The recursion tree for the computation of RECURSIVE-MATRIX-CHAIN(p, 1,4). Each node contains the parameters i and j. The computations performed in a shadedsubtree are replaced by a single table lookup in MEMOIZED-MATRIX-CHAIN(p, 1, 4).In fact, we can show that the time to compute m[1, n] by this recursive procedure is at leastexponential in n. Let T (n) denote the time taken by RECURSIVE-MATRIX-CHAIN tocompute an optimal parenthesization of a chain of n matrices.
If we assume that the executionof lines 1–2 and of lines 6–7 each take at least unit time, then inspection of the procedureyields the recurrenceNoting that for i = 1, 2, ..., n - 1, each term T (i) appears once as T (k) and once as T (n - k),and collecting the n - 1 1's in the summation together with the 1 out front, we can rewrite therecurrence as(15.13)We shall prove that T (n) = Ω(2n) using the substitution method.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
