Question? Leave a message!




Dynamic programming applications

Dynamic programming applications
6. DYNAMIC PROGRAMMING I weighted interval scheduling ‣ segmented least squares ‣ knapsack problem ‣ RNA secondary structure ‣ Lecture slides by Kevin Wayne
 Copyright © 2005 PearsonAddison Wesley
 http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on 2/10/16 9:26 AMAlgorithmic paradigms Greedy. Build up a solution incrementally, myopically optimizing
 some local criterion.
 Divideandconquer. Break up a problem into independent subproblems,
 solve each subproblem, and combine solution to subproblems to form solution to original problem. 
 Dynamic programming. Break up a problem into a series of overlapping subproblems, and build up solutions to larger and larger subproblems. fancy name for caching away intermediate results in a table for later reuse 2Dynamic programming history Bellman. Pioneered the systematic study of dynamic programming in 1950s. 
 Etymology. Dynamic programming = planning over time. Secretary of Defense was hostile to mathematical research. Bellman sought an impressive name to avoid confrontation. THE THEORY OF DYNAMIC PROGRAMMING RICHARD BELLMAN 1. Introduction. Before turning to a discussion of some representa tive problems which will permit us to exhibit various mathematical features of the theory, let us present a brief survey of the funda mental concepts, hopes, and aspirations of dynamic programming. To begin with, the theory was created to treat the mathematical problems arising from the study of various multistage decision processes, which may roughly be described in the following way: We have a physical system whose state at any time / is determined by a set of quantities which we call state parameters, or state variables. At certain times, which may be prescribed in advance, or which may be determined by the process itself, we are called upon to make de cisions which will affect the state of the system. These decisions are equivalent to transformations of the state variables, the choice of a decision being identical with the choice of a transformation. The out come of the preceding decisions is to be used to guide the choice of future ones, with the purpose of the whole process that of maximizing some function of the parameters describing the final state. Examples of processes fitting this loose description are furnished by virtually every phase of modern life, from the planning of indus trial production lines to the scheduling of patients at a medical clinic ; from the determination of longterm investment programs for universities to the determination of a replacement policy for ma chinery in factories; from the programming of training policies for skilled and unskilled labor to the choice of optimal purchasing and in ventory policies for department stores and military establishments. It is abundantly clear from the very brief description of possible applications that the problems arising from the study of these 3 processes are problems of the future as well as of the immediate present. Turning to a more precise discussion, let us introduce a small amount of terminology. A sequence of decisions will be called a policy, and a policy which is most advantageous according to some preassigned criterion will be called an optimal policy. The classical approach to the mathematical problems arising from the processes described above is to consider the set of all possible An address delivered before the Summer Meeting of the Society in Laramie on September 3, 1953 by invitation of the Committee to Select Hour Speakers for An nual and Summer meetings; received by the editors August 27,1954. 503 Dynamic programming applications Areas. Bioinformatics. Control theory. Information theory. Operations research. Computer science: theory, graphics, AI, compilers, systems, …. ... 
 Some famous dynamic programming algorithms. Unix diff for comparing two files. Viterbi for hidden Markov models. De Boor for evaluating spline curves. SmithWaterman for genetic sequence alignment. BellmanFord for shortest path routing in networks. CockeKasamiYounger for parsing contextfree grammars. ... 46. DYNAMIC PROGRAMMING I weighted interval scheduling ‣ segmented least squares ‣ knapsack problem ‣ RNA secondary structure ‣Weighted interval scheduling Weighted interval scheduling problem. Job j starts at s , finishes at f , and has weight or value v . j j j Two jobs compatible if they don't overlap. Goal: find maximum weight subset of mutually compatible jobs. a b c d e f g h time 0 1 2 3 4 5 6 7 8 9 10 11 6Earliestfinishtime first algorithm Earliest finishtime first. Consider jobs in ascending order of finish time. Add job to subset if it is compatible with previously chosen jobs. Recall. Greedy algorithm is correct if all weights are 1. 
 
 Observation. Greedy algorithm fails spectacularly for weighted version. b weight = 999 weight = 1 a h time 0 1 2 3 4 5 6 7 8 9 10 11 7Weighted interval scheduling Notation. Label jobs by finishing time: f ≤ f ≤ . . . ≤ f . 1 2 n 
 Def. p ( j ) = largest index i j such that job i is compatible with j.
 Ex. p(8) = 5, p(7) = 3, p(2) = 0. 1 2 3 4 5 6 7 8 time 0 1 2 3 4 5 6 7 8 9 10 11 8Dynamic programming: binary choice Notation. OPT(j) = value of optimal solution to the problem consisting of
 job requests 1, 2, ..., j. 
 Case 1. OPT selects job j. Collect profit v . j Can't use incompatible jobs p(j) + 1, p(j) + 2, ..., j – 1 . Must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., p(j). optimal substructure property 
 (proof via exchange argument) Case 2. OPT does not select job j. Must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., j – 1. 0 if j = 0 OPT( j) = max v + OPT( p( j)), OPT( j−1) otherwise j 9 € Weighted interval scheduling: brute force Input: n, s1..n, f1..n, v1..n Sort jobs by finish time so that f1 ≤ f2 ≤ … ≤ fn. Compute p1, p2, …, pn. ComputeOpt(j) if j = 0 return 0. else return max(vj + ComputeOpt(pj), ComputeOpt(j–1)). 10Weighted interval scheduling: brute force Observation. Recursive algorithm fails spectacularly because of redundant subproblems ⇒ exponential algorithms. 
 Ex. Number of recursive calls for family of "layered" instances grows like Fibonacci sequence. 5 4 3 1 2 3 2 2 1 3 4 2 1 1 0 1 0 5 1 0 p(1) = 0, p(j) = j2 recursion tree 11Weighted interval scheduling: memoization Memoization. Cache results of each subproblem; lookup as needed. Input: n, s1..n, f1..n, v1..n Sort jobs by finish time so that f1 ≤ f2 ≤ … ≤ fn. Compute p1, p2, …, pn. for j = 1 to n Mj ← empty. global array M0 ← 0. MComputeOpt(j) if Mj is empty Mj ← max(vj + MComputeOpt(pj), MComputeOpt(j – 1)). return Mj. 12Weighted interval scheduling: running time Claim. Memoized version of algorithm takes O(n log n) time. Sort by finish time: O(n log n). Computing p(⋅) : O(n log n) via sorting by start time.
 MCOMPUTEOPT(j): each invocation takes O(1) time and either (i) returns an existing value Mj (ii) fills in one new entry Mj and makes two recursive calls
 Progress measure Φ = nonempty entries of M. initially Φ = 0, throughout Φ ≤ n. (ii) increases Φ by 1 ⇒ at most 2n recursive calls.
 Overall running time of MCOMPUTEOPT(n) is O(n). ▪ 
 Remark. O(n) if jobs are presorted by start and finish times. 13Weighted interval scheduling: finding a solution Q. DP algorithm computes optimal value. How to find solution itself A. Make a second pass. 
 
 
 FindSolution(j) 
 if j = 0 
 return ∅. 
 else if (vj + Mpj Mj–1) 
 return j ∪ FindSolution(pj). else 
 return FindSolution(j–1). 
 
 
 
 
 Analysis. of recursive calls ≤ n ⇒ O(n). 14Weighted interval scheduling: bottomup Bottomup dynamic programming. Unwind recursion. BOTTOMUP (n, s , …, s , f , …, f , v , …, v ) 1 n 1 n 1 n Sort jobs by finish time so that f ≤ f ≤ … ≤ f . 1 2 n Compute p(1), p(2), …, p(n). M 0 ← 0. FOR j = 1 TO n M j ← max v + M p(j) , M j – 1 . j 156. DYNAMIC PROGRAMMING I weighted interval scheduling ‣ segmented least squares ‣ knapsack problem ‣ RNA secondary structure ‣Least squares Least squares. Foundational problem in statistics. Given n points in the plane: (x , y ), (x , y ) , …, (x , y ). 1 1 2 2 n n Find a line y = ax + b that minimizes the sum of the squared error: 
 n 2 SSE = ( y − ax − b) ∑ 
 i i y i=1 
 
 
 € 
 
 x 
 
 Solution. Calculus ⇒ min error is achieved when y − a x n x y − ( x ) ( y ) ∑ ∑ ∑ ∑ ∑ i i i i i i i i i i i a = , b = 2 2 n n x − ( x ) ∑ ∑ i i i i 17 € Segmented least squares Segmented least squares. Points lie roughly on a sequence of several line segments. Given n points in the plane: (x , y ), (x , y ) , …, (x , y ) with
 1 1 2 2 n n x x ... x , find a sequence of lines that minimizes f (x). 1 2 n 
 Q. What is a reasonable choice for f (x) to balance accuracy and parsimony goodness of fit number of lines y x 18Segmented least squares Given n points in the plane: (x , y ), (x , y ) , …, (x , y ) with x x ... x and a 1 1 2 2 n n 1 2 n constant c 0, find a sequence of lines that minimizes f (x) = E + c L: E = the sum of the sums of the squared errors in each segment. L = the number of lines. y x 19Dynamic programming: multiway choice Notation. OPT(j) = minimum cost for points p , p , …, p . 1 2 j e(i, j) = minimum sum of squares for points p , p , …, p . i i+1 j 
 To compute OPT(j): Last segment uses points p , p , …, p for some i. i i+1 j Cost = e(i, j) + c + OPT(i – 1). optimal substructure property (proof via exchange argument) 0 if j = 0 OPT( j) = min e(i, j) + c + OPT(i−1) otherwise '1 ≤ i≤ j € 20Segmented least squares algorithm SEGMENTEDLEASTSQUARES (n, p , …, p , c) 1 n FOR j = 1 TO n FOR i = 1 TO j Compute the least squares e(i, j) for the segment p , p , …, p . i i+1 j M 0 ← 0. FOR j = 1 TO n M j ← min e + c + M i – 1 . 1 ≤ i ≤ j ij RETURN Mn. 21Segmented least squares analysis Theorem. Bellman 1961 The dynamic programming algorithm solves the 3 2 segmented least squares problem in O(n ) time and O(n ) space. 
 Pf. 2 Bottleneck = computing e(i, j) for O(n ) pairs. O(n) per pair using formula. ▪ 
 y − a x n x y − ( x ) ( y ) ∑ ∑ ∑ ∑ ∑ i i i i i i i i 
 i i i a = , b = 2 2 n n x − ( x ) 
 ∑ ∑ i i i i 
 
 € 
 2 Remark. Can be improved to O(n ) time and O(n) space by precomputing various statistics. How 226. DYNAMIC PROGRAMMING I weighted interval scheduling ‣ segmented least squares ‣ knapsack problem ‣ RNA secondary structure ‣Knapsack problem Given n objects and a "knapsack." Item i weighs w 0 and has value v 0. i i Knapsack has capacity of W. Goal: fill knapsack so as to maximize total value. v w i i i 1 1 1 Ex. 1, 2, 5 has value 35. 2 6 2 Ex. 3, 4 has value 40. 3 18 5 Ex. 3, 5 has value 46 (but exceeds weight limit). 4 22 6 
 5 28 7 
 knapsack instance (weight limit W = 11) 
 
 Greedy by value. Repeatedly add item with maximum v . i Greedy by weight. Repeatedly add item with minimum w . i Greedy by ratio. Repeatedly add item with maximum ratio v / w .
 i i 
 Observation. None of greedy algorithms is optimal. 24Dynamic programming: false start Def. OPT(i) = max profit subset of items 1, …, i. 
 Case 1. OPT does not select item i. OPT selects best of 1, 2, …, i – 1 . 
 optimal substructure property (proof via exchange argument) Case 2. OPT selects item i. Selecting item i does not immediately imply that we will have to reject other items. Without knowing what other items were selected before i,
 we don't even know if we have enough room for i. 
 
 Conclusion. Need more subproblems 25Dynamic programming: adding a new variable Def. OPT(i, w) = max profit subset of items 1, …, i with weight limit w. 
 Case 1. OPT does not select item i. OPT selects best of 1, 2, …, i – 1 using weight limit w. 
 optimal substructure property Case 2. OPT selects item i. (proof via exchange argument) New weight limit = w – w . i OPT selects best of 1, 2, …, i – 1 using this new weight limit. 0 if i = 0 OPT(i, w) = OPT(i−1, w) if w w i max OPT(i−1, w), v + OPT(i−1, w− w ) otherwise i i € 26Knapsack problem: bottomup KNAPSACK (n, W, w , …, w , v , …, v ) 1 n 1 n FOR w = 0 TO W M 0, w ← 0. FOR i = 1 TO n FOR w = 0 TO W IF (w w) M i, w ← M i – 1, w. i ELSE M i, w ← max M i – 1, w, v + M i – 1, w – w . i i RETURN Mn, W. 27Knapsack problem: bottomup demo v w i i i 1 1 1 0 if i = 0 2 6 2 OPT(i, w) = OPT(i−1, w) if w w i 3 18 5 max OPT(i−1, w), v + OPT(i−1, w− w ) otherwise i i 4 22 6 5 28 7 € weight limit w 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1, 2 0 1 6 7 7 7 7 7 7 7 7 7 subset
 of items 1, 2, 3 1, …, i 0 1 6 7 7 18 19 24 25 25 25 25 1, 2, 3, 4 0 1 6 7 7 18 22 24 28 29 29 40 1, 2, 3, 4, 5 0 1 6 7 7 18 22 28 29 34 35 40 OPT(i, w) = max profit subset of items 1, …, i with weight limit w. 28Knapsack problem: running time Theorem. There exists an algorithm to solve the knapsack problem with n items and maximum weight W in Θ(n W) time and Θ(n W) space. Pf. weights are integers between 1 and W Takes O(1) time per table entry. There are Θ(n W) table entries. After computing optimal values, can trace back to find solution:
 take item i in OPT(i, w) iff M i, w M i – 1, w. ▪ 
 
 
 Remarks. "pseudopolynomial" Not polynomial in input size Decision version of knapsack problem is NPCOMPLETE. CHAPTER 8 There exists a polytime algorithm that produces a feasible solution that has value within 1 of optimum. SECTION 11.8 296. DYNAMIC PROGRAMMING I weighted interval scheduling ‣ segmented least squares ‣ knapsack problem ‣ RNA secondary structure ‣RNA secondary structure RNA. String B = b b …b over alphabet A, C, G, U . 1 2 n Secondary structure. RNA is singlestranded so it tends to loop back and form base pairs with itself. This structure is essential for understanding behavior of molecule. C A A A A U G C C G U A A G G U A U U A G A C G C U G C G C G A G C G A U G RNA secondary structure for GUCGAUUGAGCGAAUGUAACAACGUGGCUACGGCGAGA 31RNA secondary structure Secondary structure. A set of pairs S = (b , b ) that satisfy: i j WatsonCrick S is a matching and each pair in S is a WatsonCrick complement: A–U, U–A, C–G, or G–C. No sharp turns The ends of each pair are separated by at least 4 intervening bases. If (b , b ) ∈ S, then i j – 4. i j Noncrossing If (b , b ) and (b , b ) are two pairs in S, then we cannot i j k have i k j . 
 
 Free energy. Usual hypothesis is that an RNA molecule will form the secondary structure with the minimum total free energy. 
 approximate by number of base pairs 
 
 Goal. Given an RNA molecule B = b b …b , find a secondary structure S
 1 2 n that maximizes the number of base pairs. 32RNA secondary structure Examples. G G G G G G G C U C U G C G C U C A U A U A G U A U A U A base pair U G U G G C C A U U G G G G C A U G U U G G C C A U A A A ok sharp turn
 crossing (≤4 intervening bases) 33RNA secondary structure: subproblems First attempt. OPT(j) = maximum number of base pairs in a secondary structure of the substring b b … b . 1 2 j 
 
 
 match b and b t n Choice. Match b and b . t n 
 
 
 t n 1 
 
 
 Difficulty. Results in two subproblems but one of wrong form. OPT(t–1) Find secondary structure in b b … b . 1 2 t–1 Find secondary structure in b b … b . need more subproblems t+1 t+2 n–1 34Dynamic programming over intervals Notation. OPT( i, j ) = maximum number of base pairs in a secondary structure of the substring b b … b . i i+1 j 
 Case 1. If i ≥ j – 4. OPT(i, j) = 0 by nosharp turns condition. 
 Case 2. Base b is not involved in a pair. j OPT(i, j) = OPT(i, j – 1). 
 Case 3. Base b pairs with b for some i ≤ t j – 4. j t Noncrossing constraint decouples resulting subproblems. OPT(i, j) = 1 + max OPT(i, t – 1) + OPT(t + 1, j – 1) . t take max over t such that i ≤ t j – 4 and
 b and b are WatsonCrick complements t j 35Bottomup dynamic programming over intervals Q. In which order to solve the subproblems A. Do shortest intervals first. 
 
 j RNA (n, b , …, b ) 
 1 n 6 7 8 9 10 
 FOR k = 5 TO n – 1 4 0 0 0 
 FOR i = 1 TO n – k 3 0 0 
 i j ← i + k. 2 0 
 Compute Mi, j using formula. 1 
 RETURN M1, n. 
 order in which to solve subproblems 
 
 Theorem. The dynamic programming algorithm solves the RNA secondary 3 2 substructure problem in O(n ) time and O(n ) space. 36Dynamic programming summary Outline. Polynomial number of subproblems. Solution to original problem can be computed from subproblems. Natural ordering of subproblems from smallest to largest, with an easy tocompute recurrence that allows one to determine the solution to a subproblem from the solution to smaller subproblems. 
 Techniques. Binary choice: weighted interval scheduling. Multiway choice: segmented least squares. Adding a new variable: knapsack problem. Dynamic programming over intervals: RNA secondary structure. 
 
 
 Topdown vs. bottomup. Different people have different intuitions. 37
Website URL
Comment