6.006- Introduction to Algorithms Lecture 19 Prof. Patrick JailletLecture overview Dynamic Programming II – review • key aspects of Dynamic Programming (DP) • all-pairs shortest paths as a DP – another DP for all-pairs shortest paths – longest common subsequence CLRS 15.3, 15.4, 25.1, 25.2Dynamic Programming • DP ≈ recursion + memoization • Typically (not always) applied to optimization problems – ex Fibonaci, Crazy eight, SPPs Optimal substructure optimal solution to a problem can be obtained from optimal solutions to subproblems. Overlapping subproblems A recursive solution contains a “small” number of distinct subproblems (repeated many times)Dynamic Programming • DP ≈ recursion + memoization • DP works when: – the solution can be produced by combining solutions of subproblems; – the solution of each subproblem can be produced by combining solutions of sub-subproblems, etc; moreover …. is efficient if – the total number of subproblems arising recursively is polynomial.All-pairs shortest paths • Input: Directed graph G = (V, E), where |V | = n, with edge-weight function w : E → R • Output: n × n matrix of shortest-path lengths δ(i, j) for all i, j ∈ V.Dynamic Programming Approach • Consider the n × n matrix A = (aij) where aij=w(i,j) if (i,j) ∈ E. • Define dij(m) = weight of a shortest path from i to j that uses at most m edges • We have – dij(0) = 0, if i = j, – and dij(0) = ∞ otherwise; CLAIM: for m = 1, 2, …, n–1, dij(m) = mink{dik(m–1) + akj}Proof of Claim … ≤ m-1 edges ≤ m-1 edges i j k’s dij(m) = mink{dik(m–1) + akj } for k ← 1 to n if dij > dik + akj dij ← dik + akj RelaxationDP Approach, running time • Consider the n × n matrix A = (aij), where aij=w(i,j) if (i,j) ∈ E. • Define dij(m) = weight of a shortest path from i to j that uses at most m edges We have – dij(0) = 0, if i = j, – and dij(0) = ∞ otherwise; CLAIM: for m = 1, 2, …, n–1, dij(m) = mink{dik(m–1) + akj} O(n4) - similar to n runs of Bellman-FordDynamic Programming • DP ≈ recursion + memoization • Typically (not always) applied to optimization problems Optimal substructure ? optimal solution to a problem can be obtained from optimal solutions to subproblems. Overlapping subproblems ? A recursive solution contains a “small” number of distinct subproblems (repeated many times)Another DP Approach • Consider again the n × n matrix A = (aij) where aij=w(i,j) if (i,j) ∈ E. • Define dij(k) = weight of a shortest path from i to j for which all intermediate vertices are chosen among {1,2, ..., k} • CLAIM: – dij(k) = aij if k=0, – dij(k) = min{dij(k-1),dik(k–1) +dkj(k–1)} if k≥1; O(n3) running time (Floyd-Warshall)Dynamic Programming • DP ≈ recursion + memoization • Typically (not always) applied to optimization problems Optimal substructure ? optimal solution to a problem can be obtained from optimal solutions to subproblems. Overlapping subproblems ? A recursive solution contains a “small” number of distinct subproblems (repeated many times)Longest Common Subsequence • given two sequences x[1..m] and y[1..n], find a longest subsequence LCS(x,y) common to both: x: A B C B D A B y: B D C A B A • denote the length of a sequence s by |s| • let us first try to get |LCS(x,y)|Brute force solution • For every subsequence of x[1..m] , check if it is a subsequence of y[1..n] • Analysis – 2m subsequences of x – each check takes Ο(n) time ... – worst case running time is Ο(n2m) • Pretty bad (brute!)Using prefixes • consider prefixes of x and y – x[1..i] ith prefix of x[1..m] – y[1..j] jth prefix of y[1..n] • define c[i,j] = |LCS(x[1..i],y[1..j])| • so c[m,n] = |LCS(x,y)| • recurrence?1) x[1..i] and y[1..j] end with xi=yj x1 x2 … xi-1 xi y1 y2 … yj-1 yj=xi z1 z2…zk-1 zk =yj=xi Zk is Zk -1 followed by zk = yj = xi where Zk-1 is an LCS of x[1..i-1] and y[1..j-1] c(i, j) = c(i-1, j-1)+1Example - use of property 1 x: B A N A N A y: A T A N A by inspection LCS of B A N and A T is A so LCS(x,y) is A A N A2) x[1..i] and y[1..j] end with xi ≠ yj x1 x2 … xi-1 xi y1 y2 … yj-1 yj Zk z1 z2…zk-1 zk ≠yj LCS of x[1..i] and y[1..j-1] x1 x2 … xi-1 x i yj y1 y2 …yj-1 yj Zk z1 z2…zk-1 zk ≠ xi c(i, j)=max{c(i, j-1), c(i-1, j)} LCS of x[1..i-1] and y[1..j]Example: use of property 2 The last character of the LCS(x,y) either: – ends with a G => can’t end with a K • => can remove K from y – doesn’t end with a G • => can remove G from x x: A B C D E F G y: B C D G KA recurrence, summary • consider prefixes of x and y – x[1..i] ith prefix of x[1..m] – y[1..j] jth prefix of y[1..n] • define c[i,j] = |LCS(x[1..i],y[1..j])| – so c[m,n] = |LCS(x,y)| • recurrence: € c[i, j] =c[i −1, j −1] +1 if xi= yjmax{c[i −1, j],c[i, j −1]} otherwise⎧ ⎨ ⎩Solving LCS with DP • running time is .... – O(n×m) € c[i, j] =c[i −1, j −1] +1 if xi= yjmax{c[i −1, j],c[i, j −1]} otherwise⎧ ⎨ ⎩Dynamic Programming • DP ≈ recursion + memoization • Typically (not always) applied to optimization problems Optimal substructure ? optimal solution to a problem can be obtained from optimal solutions to subproblems. Overlapping subproblems ? A recursive solution contains a “small” number of distinct subproblems (repeated many
View Full Document
Unlocking...