6 006 Introduction to Algorithms Lecture 19 Prof Patrick Jaillet Lecture 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 2 Dynamic 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 dij m mink dik m 1 akj i k s s e g d e m 1 m 1 edges j for k 1 to n if dij dik akj dij dik akj Relaxation DP 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 Ford 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 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 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 B 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 1 Example use of property 1 x B A N A N y A T A N A A by inspection LCS of B A N and A T is A so LCS x y is A A N A 2 x 1 i and y 1 j end with xi yj x1 x2 xi 1 xi x1 x2 xi 1 x i y1 y2 yj y1 y2 yj 1 yj yj 1 yj Zk z1 z2 zk 1 zk yj LCS of x 1 i and y 1 j 1 Zk z1 z2 zk 1 zk xi LCS of x 1 i 1 and y 1 j c i j max c i j 1 c i 1 j Example use of property 2 x A B C D E y B C D G K F 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 G A 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 1 j 1 1 if x i y j c i j max c i 1 j c i j 1 otherwise Solving LCS with DP c i 1 j 1 1 if x i y j c i j max c i 1 j c i j 1 otherwise running time is O n m 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
View Full Document
Unlocking...