What are the requirements for dynamic programming

Dynamic programming

Transcript

1 Dynamic Programming Hannes Schwarz - WS-06/07 Getting Ready for the ACM Programming Contest

2 Overview Overview What is dynamic programming? Development of an algorithm Example: Fibonacci sequence Implementation memoization & sub-problems

3 Overview backpack problem implementation top-down vs. bottom-up binomial coefficients Conclusion sources

4 What is dynamic programming? Definition: Dynamic programming algorithms are used for optimization problems in which the end result can be calculated from an unknown combination of many, not necessarily independent partial results. Source: http: //dynamische_programmierung.know-library.net

5 What is dynamic programming? Area of ​​application: optimization problems end result is a combination of partial results partial results are not necessarily independent combination unknown

6 Where does dynamic programming come from? Divide & rule is the basis Cleverly implemented recursion Store intermediate results in a table Typical use: Search for minimum or maximum combination

7 Where does dynamic programming come from? Term coined in the 1940s by Richard Bellman Mathematical Procedure Programming refers to filling out the table

8 Development of an algorithm with dynamic programming Prerequisite: The optimal solution consists of optimal partial solutions. 1. Characterization of the structure 2. Recursive definition of the value of an optimal solution 3. Calculation of the value of an optimal solution (recursive) 4. Construction of the optimal solution from calculated information

9 Fibonacci sequence definition: f (1) = f (2) = 1 f (n) = f (n 2) + f (n 1) n> 2 recursively defined recursive implementation?

10 Fibonacci sequence - recursive implementation static int knownf [] = new int [1000]; int fib (int n) {if (knownf [n]! = 0) {return knownf [n];} if (n == 1 n == 2) {return 1; } int newfib = fib (n-2) + fib (n-1); return newfib; }

11 Fibonacci sequence - recursive implementation recursion tree for f (7) exponential effort O (2 n)

12 Fibonacci sequence - recursive implementation with brains static int knownf [] = new int [1000]; int fib (int n) {if (knownf [n]! = 0) {return knownf [n];} if (n == 1 n == 2) {return 1; } int newfib = fib (n-2) + fib (n-1); return newfib; }

13 Fibonacci sequence - recursive implementation with brains static int knownf [] = new int [1000]; int fib (int n) {if (knownf [n]! = 0) {return knownf [n];} if (n <2) {return 1; } int newfib = fib (n-2) + fib (n-1); return newfib; }

14 Fibonacci sequence - recursive implementation with brains static int knownf [] = new int [1000]; int fib (int n) {if (knownf [n]! = 0) {return knownf [n];} if (n <2) {return 1; } int newfib = fib (n-2) + fib (n-1); return knownf [n] = newfib; }

15 Fibonacci sequence - recursive implementation with brains Further recursion Recursion tree for f (7) results are saved First lookup in table linear effort O (n)

16 Fibonacci sequence running times for fib (50) = algorithm time recursive 13 min. 12 sec. iterative sec. rec. + Head sec.

17 Optimal sub-problems decomposition as in Divide & Rule BUT: sub-problems do not have to be independent decomposition provides recursion equation for the problem sub-problems are optimally set up base cases (n = 1)

18 Overlapping sub-problems Recursion always solves the same sub-problems Overlapping sub-problems Divide & rule: different sub-problems Use of memoization Dynamic programming is nothing more than the solving of sub-problems, whereby the multiple computation of sub-problems due to overlapping is overwhelmed by memoization.

19 Memoization Idea: Inefficient recursion becomes efficient by filling the table. Table one- or multi-dimensional array program looks like this: Value already calculated? return Value not yet calculated? calculate, save, return

20 backpack problem? 17 kg

21 Backpack problem Backpack of size c N types of objects Each type n has a value vn as well as a space requirement of sn Now we pack the backpack: The capacity c is not exceeded The total value is maximum

22 Backpack problem - design of the optimal solution List of k object types n: L c = (n 1, n 2, ..., n k) The maximum value of the backpack is the sum of all values ​​of its objects w c = k i = 1 v i

23 Backpack problem - setting up the recursion equation Lc is an optimal solution for the capacity c If we remove an element from Lc the remaining list is an optimal solution for the capacity c - snk At each step a selection has to be made: add another element so that The capacity is still below the total capacity. The increased total value is a maximum

24 Backpack problem - recursive solution Cont .: static class Item {int size; int val;} Item items []; static int knap (int cap) {int i, space, max, t; for (i = 0, max = 0; i = 0) if ((t = knap (space) + items [i] .val)> max) max = t; return max; }

25 Backpack problem - recursive solution Op .: static class Item {int size; int val;} Item items []; HANDS OFF!!!! static int knap (int cap) {int i, space, max, t; for (i = 0, max = 0; i = 0) if ((t = knap (space) + items [i] .val)> max) max = t; return max; }

26 Backpack problem - recursive solution with memoization static int knap (int cap) {int i, space, max, t; if (maxknown [cap]! = unknown) return maxknown [cap]; for (i = 0, max = 0; i = 0) if ((t = knap (space) + items [i] .cal)> max) max = t; return max; }

27 Backpack problem - recursive solution with memoization static int knap (int cap) {int i, space, max, t; if (maxknown [cap]! = unknown) return manknown [cap]; for (i = 0, max = 0; i = 0) if ((t = knap (space) + items [i] .val)> max) max = t; maxknown [cap] = max; return max; }

28 Backpack problem - recursive solution with memoization Runtime without memociation c time sec sec 135 4min 28sec min 48sec runtime with memociation c time ms ms ms ms from exponential to linear runtime

29 Backpack problem - reconstruction of the solution. Result so far: Value of our maximum packed backpack. Which items are actually in the backpack?

30 Backpack problem - Reconstruction of the solution. Note the object in each step - further array A unique object for each capacity value. This object is optimal for its size and therefore solid

31 Backpack problem - reconstruction of the solution method Reconstruction begins with the total capacity c The index of the first item is in itemknown [c] If the item was added c = c -itemknown [c] .size Next index also itemknown [c -itemknown [c]. size] etc.

32 Backpack problem - the final solution static int knap (int cap) {int i, space, max, maxi, t; if (maxknown [cap]! = unknown) return manknown [cap]; for (i = 0, max = 0; i = 0) if ((t = knap (space) + items [i] .val )> max) max = t; maxi = i; maxknown [cap] = max; itemknown [cap] = items [maxi]; return max; }

33 Top-down recursive calculation is a top-down approach Up to now, efficiency gains through memoization Problems through: High recursion depths (stack overflow) Overhead through function calls

34 Bottom-up First fill the table with partial solutions and then read the solution from the table. Higher performers than the top-down approach Bottom-up approach is harder to find

35 Bottom-up vs. top-down Bottom-up approach First an optimal solution of sub-problems is determined. Then selection of the optimal sub-solutions for the construction of a solution to the original problem. Top-down approach First selection of a promising alternative. Then solution of the resulting sub-problems

36 Binomial Coefficients Problem: Number of possibilities to choose k (numbered) students from a seminar room with n people and send them to the World Final Solution: () n k = n! (n k)! k!

37 binomial coefficients recursion equation () n k = () n 1 k 1 + () n 1 k Pascal's triangle n = 0 1 n = n = n = n = n = n =

38 Binomial Coefficients - The Bottom-Up Solution To the solution Pascal's triangle Array [n] [n + 1] The borders [0] [0] to [0] [n] and [0] [0] to [n] [n ] are filled with ones. Previous results are used for the calculation. Position [n] [m] contains the value you are looking for

39 Binomial Coefficients - The Bottom-Up Solution static void bin () {int triangle [] [] = new int [7] []; for (int i = 0; i

40 Binomial Coefficients - The Bottom-Up Solution No overhead from function calls But: too many values ​​calculated For the value xi, j, xi-1, j-1 and xi-1, j values ​​are relevant. For the calculation of () nm, therefore, none are required xi, j with j> m Filling out the table in every row for the m-th value is sufficient

41 Fibonacci sequence - recursive implementation with memoization static int knownf [] = new int [1000]; int fib (int n) {if (knownf [n]! = 0) {return knownf [n];} if (n <2) {return 1; } int newfib = fib (n-2) + fib (n-1); return knownf [n] = newfib; }

42 Fibonacci sequence - iterative implementation (bottom-up) static int iterative (int n) {int [] ita = new int [n + 1]; ita [1] = 1; ita [2] = 1; for (int i = 3; i

43 Conclusion Search for the optimum The optimum result can be broken down into optimum partial results. Every step towards the goal requires a selection. Overlaps can occur

44 Conclusion It is not always possible to combine the solution of smaller problems in such a way that the big problem is solved

45 Other areas of application of dynamic programming Bioinformatics Sequencing of genes and proteins Similar problems as with string comparisons Linguistics CYK algorithm

46 Recommended reading R. Sedgewick; Algorithms in Java; Pearson, 2003 S. Skiena; The Algorithm Design Manual; Springer, 1998 V. Heun; Basic alhorithms; Vieweg, 2003

47 Internet sources dynamic_programming.pdf? Language = en dyn_programming.beamer.pdf? Language = de

48 Thank you for your attention!