Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 66
Текст из файла (страница 66)
Shesuggests that an optimal solution to the matrix-chain multiplication problem can be found byalways choosing the matrix Ak at which to split the subproduct Ai Ai+1 Aj (by selecting k tominimize the quantity pi-1 pk pj) before solving the subproblems. Find an instance of thematrix-chain multiplication problem for which this greedy approach yields a suboptimalsolution.[1]This is not a misspelling. The word really is memoization, not memorization.
Memoizationcomes from memo, since the technique consists of recording a value so that we can look it uplater.[2]We use the term "unweighted" to distinguish this problem from that of finding shortestpaths with weighted edges, which we shall see in Chapters 24 and 25. We can use the breadthfirst search technique of Chapter 22 to solve the unweighted problem.[3]It may seem strange that dynamic programming relies on subproblems being bothindependent and overlapping. Although these requirements may sound contradictory, theydescribe two different notions, rather than two points on the same axis.
Two subproblems ofthe same problem are independent if they do not share resources. Two subproblems areoverlapping if they are really the same subproblem that occurs as a subproblem of differentproblems.[4]This approach presupposes that the set of all possible subproblem parameters is known andthat the relation between table positions and subproblems is established. Another approach isto memoize by using hashing with the subproblem parameters as keys.15.4 Longest common subsequenceIn biological applications, we often want to compare the DNA of two (or more) differentorganisms.
A strand of DNA consists of a string of molecules called bases, where the possiblebases are adenine, guanine, cytosine, and thymine. Representing each of these bases by theirinitial letters, a strand of DNA can be expressed as a string over the finite set {A, C, G, T}.(See Appendix C for a definition of a string.) For example, the DNA of one organism may beS1= ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, while the DNA of another organismmay be S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA. One goal of comparing twostrands of DNA is to determine how "similar" the two strands are, as some measure of howclosely related the two organisms are.
Similarity can be and is defined in many different ways.For example, we can say that two DNA strands are similar if one is a substring of the other.(Chapter 32 explores algorithms to solve this problem.) In our example, neither S1 nor S2 is asubstring of the other. Alternatively, we could say that two strands are similar if the numberof changes needed to turn one into the other is small. (Problem 15-3 looks at this notion.) Yetanother way to measure the similarity of strands S1 and S2 is by finding a third strand S3 inwhich the bases in S3 appear in each of S1 and S2; these bases must appear in the same order,but not necessarily consecutively.
The longer the strand S3 we can find, the more similar S1and S2 are. In our example, the longest strand S3 is GTCGTCGGAAGCCGGCCGAA.We formalize this last notion of similarity as the longest-common-subsequence problem. Asubsequence of a given sequence is just the given sequence with zero or more elements leftout. Formally, given a sequence X = x1, x2, ..., xm , another sequence Z = z1, z2, ..., zk isa subsequence of X if there exists a strictly increasing sequence i1,i2, ..., ik of indices of Xsuch that for all j = 1, 2, ..., k, we have xij = zj .
For example, Z = B, C, D, B is asubsequence of X = A, B, C, B, D, A, B with corresponding index sequence 2, 3, 5, 7 .Given two sequences X and Y , we say that a sequence Z is a common subsequence of X andY if Z is a subsequence of both X and Y . For example, if X = A, B, C, B, D, A, B and Y =B, D, C, A, B, A , the sequence B, C, A is a common subsequence of both X and Y . Thesequence B, C, A is not a longest common subsequence (LCS) of X and Y , however, sinceit has length 3 and the sequence B, C, B, A , which is also common to both X and Y , haslength 4. The sequence B, C, B, A is an LCS of X and Y , as is the sequence B, D, A, B ,since there is no common subsequence of length 5 or greater.In the longest-common-subsequence problem, we are given two sequences X = x1, x2, ...,xm and Y = y1, y2, ..., yn and wish to find a maximum-length common subsequence of Xand Y . This section shows that the LCS problem can be solved efficiently using dynamicprogramming.Step 1: Characterizing a longest common subsequenceA brute-force approach to solving the LCS problem is to enumerate all subsequences of X andcheck each subsequence to see if it is also a subsequence of Y , keeping track of the longestsubsequence found.
Each subsequence of X corresponds to a subset of the indices {1, 2, ..., m}of X. There are 2m subsequences of X, so this approach requires exponential time, making itimpractical for long sequences.The LCS problem has an optimal-substructure property, however, as the following theoremshows. As we shall see, the natural classes of subproblems correspond to pairs of "prefixes" ofthe two input sequences. To be precise, given a sequence X = x1, x2, ..., xm , we define theith prefix of X, for i = 0, 1, ..., m, as Xi = x1, x2, ..., xi .
For example, if X = A, B, C, B, D,A, B , then X4 = A, B, C, B and X0 is the empty sequence.Theorem 15.1: (Optimal substructure of an LCS)Let X = x1, x2, ..., xmany LCS of X and Y.and Y =y1, y2, ..., ynbe sequences, and let Z =z1, z2, ..., zkbe1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.2. If xm ≠ yn, then zk ≠ xm implies that Z is an LCS of Xm-1 and Y.3. If xm ≠ yn, then zk ≠ yn implies that Z is an LCS of X and Yn-1.Proof (1) If zk ≠ xm, then we could append xm = yn to Z to obtain a common subsequence of Xand Y of length k + 1, contradicting the supposition that Z is a longest common subsequenceof X and Y . Thus, we must have zk = xm = yn.
Now, the prefix Zk-1 is a length-(k - 1) commonsubsequence of Xm-1 and Yn-1. We wish to show that it is an LCS. Suppose for the purpose ofcontradiction that there is a common subsequence W of Xm-1 and Yn-1 with length greater thank - 1. Then, appending xm = yn to W produces a common subsequence of X and Y whose lengthis greater than k, which is a contradiction.(2) If zk ≠ xm, then Z is a common subsequence of Xm-1 and Y. If there were a commonsubsequence W of Xm-1 and Y with length greater than k, then W would also be a commonsubsequence of Xm and Y , contradicting the assumption that Z is an LCS of X and Y.(3) The proof is symmetric to (2).The characterization of Theorem 15.1 shows that an LCS of two sequences contains within itan LCS of prefixes of the two sequences.
Thus, the LCS problem has an optimal-substructureproperty. A recursive solution also has the overlapping-subproblems property, as we shall seein a moment.Step 2: A recursive solutionTheorem 15.1 implies that there are either one or two subproblems to examine when findingan LCS of X = x1, x2, ..., xm and Y = y1, y2, ..., yn . If xm = yn, we must find an LCS ofXm-1 and Yn-1. Appending xm = yn to this LCS yields an LCS of X and Y.
If xm ≠ yn, then wemust solve two subproblems: finding an LCS of Xm-1 and Y and finding an LCS of X and Yn-1.Whichever of these two LCS's is longer is an LCS of X and Y. Because these cases exhaust allpossibilities, we know that one of the optimal subproblem solutions must be used within anLCS of X and Y .We can readily see the overlapping-subproblems property in the LCS problem. To find anLCS of X and Y , we may need to find the LCS's of X and Yn-1 and of Xm-1 and Y . But each ofthese subproblems has the subsubproblem of finding the LCS of Xm-1 and Yn-1. Many othersubproblems share subsubproblems.As in the matrix-chain multiplication problem, our recursive solution to the LCS probleminvolves establishing a recurrence for the value of an optimal solution. Let us define c[i, j] tobe the length of an LCS of the sequences Xi and Yj .
If either i = 0 or j = 0, one of thesequences has length 0, so the LCS has length 0. The optimal substructure of the LCSproblem gives the recursive formula(15.14)Observe that in this recursive formulation, a condition in the problem restricts whichsubproblems we may consider. When xi = yj , we can and should consider the subproblem offinding the LCS of Xi-1 and Yj-1. Otherwise, we in stead consider the two subproblems offinding the LCS of Xi and Yj-1 and of Xi-1 and Yj. In the previous dynamic-programmingalgorithms we have examined—for assembly-line scheduling and matrix-chainmultiplication—no subproblems were ruled out due to conditions in the problem.
Finding theLCS is not the only dynamic-programming algorithm that rules out subproblems based onconditions in the problem. For example, the edit-distance problem (see Problem 15-3) has thischaracteristic.Step 3: Computing the length of an LCSBased on equation (15.14), we could easily write an exponential-time recursive algorithm tocompute the length of an LCS of two sequences.
Since there are only Θ(mn) distinctsubproblems, however, we can use dynamic programming to compute the solutions bottomup.Procedure LCS-LENGTH takes two sequences X = x1, x2, ..., xm and Y = y1, y2, ..., ynas inputs. It stores the c[i, j] values in a table c[0 m, 0 n] whose entries are computed inrow-major order. (That is, the first row of c is filled in from left to right, then the second row,and so on.) It also maintains the table b[1 m, 1 n] to simplify construction of an optimalsolution.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
