6.006 Lecture 19: Memoization, Subproblems, Guessing, Bottom-Up; Fibonacci, Shortest Paths

Lecture 19 Dynamic Programming I of IV 6.006 Fall 2011 Lecture 19: Dynamic Programming I: Memoization, Fibonacci, Shortest Paths, Guessing Lecture Overview • Memoization and subproblems • Examples – Fibonacci – Shortest Paths • Guessing & DAG View Dynamic Programming (DP) Big idea, hard, yet simple • Powerful algorithmic design technique • Large class of seemingly exponential problems have a polynomial solution (“only”) via DP • Particularly for optimization problems (min / max) (e.g., shortest paths) * DP ≈ “controlled brute force” * DP ≈ recursion + re-use History Richard E. Bellman (1920-1984) Richard Bellman received the IEEE Medal of Honor, 1979. “Bellman . . . explained that he invented the name ‘dynamid programming’ to hide the fact that he was doing mathe­ matical research at RAND under a Secretary of Defense who ‘had a pathological fear and hatred of the term, research’. He settled on the term ‘dynamic programming’ because it would be difficult to give a ‘pejorative meaning’ and because ‘it was something not even a Congressman could object to’ ” [John Rust 2006] Fibonacci Numbers F1 = F2 = 1; Fn = Fn−1 + Fn−2 Goal: compute Fn 1 Lecture 19 Dynamic Programming I of IV 6.006 Fall 2011 Naive Algorithm follow recursive definition fib(n): if n ≤ 2: return f = 1 else: return f = fib(n − 1) + fib(n − 2) =⇒ T (n) = T (n − 1) + T (n − 2) + O(1) ≥ Fn ≈ ϕn ≥ 2T (n − 2) + O(1) ≥ 2n/2 EXPONENTIAL — BAD! Fn Fn-2 Fn-1 Fn-2 Fn-3 Fn-3 Fn-4 Figure 1: Naive Fibonacci Algorithm. Memoized DP Algorithm Remember, remember memo = { } fib(n): if n in memo: return memo[n] else: if n ≤ 2 : f = 1 else: f = fib(n − 1) + fib(n − 2) memo[n] = f return f 2 Lecture 19 Dynamic Programming I of IV 6.006 Fall 2011 • =⇒ fib(k) only recurses first time called, ∀k • =⇒ only n nonmemoized calls: k = n, n − 1, . . . , 1 • memoized calls free (Θ(1) time) • =⇒ Θ(1) time per call (ignoring recursion) POLYNOMIAL — GOOD! * DP ≈ recursion + memoization • memoize (remember) & re-use solutions to subproblems that help solve problem – in Fibonacci, subproblems are F1 , F2 , . . . , Fn * =⇒ time = # of subproblems · time/subproblem • Fibonacci: # of subproblems is n, and time/subproblem is Θ(1) = Θ(n) (ignore recursion!). Bottom-up DP Algorithm fib = {} for k in [1, 2, . . . , n]: if k ≤ 2: f = 1 else: f = fib[k − 1] + fib[k − 2] fib[k] = f return fib[n] ⎫ ⎪ ⎬ Θ(1) ⎪ ⎭ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ Θ(n) ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ • exactly the same computation as memoized DP (recursion “unrolled”) • in general: topological sort of subproblem dependency DAG . . . Fn-2 Fn-1 Fn • practically faster: no recursion • analysis more obvious • can save space: just remember last 2 fibs =⇒ Θ(1) [Sidenote: There is also an O(lg n)-time algorithm for Fibonacci, via different techniques] 3 Lecture 19 Dynamic Programming I of IV 6.006 Fall 2011 Shortest Paths • Recursive formulation: δ(s, v) = min{w(u, v) + δ(s, u) (u, v) ∈ E} • Memoized DP algorithm: takes infinite time if cycles! in some sense necessary to handle negative cycles t s Figure 2: Shortest Paths • works for directed acyclic graphs in O(V + E) effectively DFS/topological sort + Bellman-Ford round rolled into a single recursion * Subproblem dependency should be acyclic • more subproblems remove cyclic dependence: δk (s, v) = shortest s → v path using ≤ k edges • recurrence: δk (s, v) = min{δk−1 (s, u) + w(u, v) (u, v) ∈ E} δ0 (s, v) = ∞ for s = v (base case) δk (s, s) = 0 for any k (base case, if no negative cycles) • Goal: δ(s, v) = δ|V |−1 (s, v) (if no negative cycles) • memoize • time: # subproblems · time/subproblem # - # |V |·|V | · O(v) = 0(V 3 ) • actually Θ(indegree(v)) for δk (s, v) • =⇒ time = Θ(V v∈V indegree(V )) = Θ(V E) BELLMAN-FORD! 4 Lecture 19 Dynamic Programming I of IV 6.006 Fall 2011 Guessing How to design recurrence • want shortest s → v path s . . . u v • what is the last edge in path? dunno • guess it is (u, v) • path is shortest s → u path + edge (u, v) # by optimal substructure • cost is δk−1 (s, u) + w(u, v) # another subproblem • to find best guess, try all (|V | choices) and use best • * key: small (polynomial) # possible guesses per subproblem — typically this domi­ nates time/subproblem * DP ≈ recursion + memoization + guessing DAG view 0 1 time 2 3 • like replicating graph to represent time • converting shortest paths in graph → shortest paths in DAG * DP ≈ shortest paths in some DAG 5