国外算法设计与分析课件13

1、Dynamic ProgrammingCopyright Li Zimao 2007-2008-1 SCUECExpected OutcomesStudents should be able toSolve the all pairs shortest paths problem by dynamic programming, that is the Floyds algorithmSolve the transitive closure problem by dynamic programming, that is the Warshalls algorithmSolve the knaps

2、ack problem by dynamic programmingSolve the matrix chain multiplication problem by dynamic programmingCopyright Li Zimao 2007-2008-1 SCUECTransitive ClosureThe transitive closure of a directed graph with n vertices can be defined as the nxn matrix T = tij, in which the element in the ith row (1 i n)

3、 and the jth column (1 j n) is 1 if there exists a nontrivial directed path (i.e., a directed path of a positive length) from the ith vertex to the jth vertex; otherwise, tij is 0. Graph traversal-based algorithm and Warshalls algorithm34210 0 1 01 0 0 10 0 0 00 1 0 00 0 1 01 1 1 10 0 0 01 1 1 13421

4、Adjacency matrixTransitive closureCopyright Li Zimao 2007-2008-1 SCUECWarshalls Algorithm Main idea: Use a bottom-up method to construct the transitive closure of a given digraph with n vertices through a series of nxn boolean matrices:T(0), T(k-1), T(k) , , T(n)The question is: how to obtain T(k) f

5、rom T(k-1) ?3421342134213421 T(0)0 0 1 01 0 0 10 0 0 00 1 0 0T(1)0 0 1 01 0 1 10 0 0 00 1 0 0T(2)0 0 1 01 0 1 10 0 0 01 1 1 1T(3)0 0 1 01 0 1 10 0 0 01 1 1 1T(4)0 0 1 01 1 1 10 0 0 01 1 1 13421 T(k) : tij(k) = 1 in T(k) , iff there is an edge from i to j; or there is a path from i to j going through

6、 vertex 1; or there is a path from i to j going through vertex 1 and/or 2; or. there is a path from i to j going through 1, 2, and/or kAllow 1 to be an intermediate nodeAllow 1,2 to be an intermediate nodeAllow 1,2,3 to be an intermediate nodeAllow 1,2,3,4 to be an intermediate nodeDoes not allow an

7、 intermediate nodeCopyright Li Zimao 2007-2008-1 SCUECWarshalls AlgorithmIn the kth stage: to determine T(k) is to determine if a path exists between two vertices i, j using just vertices among 1,k tij(k-1) = 1 (path using just 1 ,k-1)tij(k) = 1: or (tik(k-1) = 1 and tkj(k-1) = 1) (path from i to k

8、and from k to i using just 1 ,k-1)ijkkth stageRule to determine whether tij (k) should be 1 in T(k) : If an element tij is 1 in T(k-1) , it remains 1 in T(k) . If an element tij is 0 in T(k-1) ,it has to be changed to 1 in T(k) iff the element in its row i and column k and the element in its column

9、j and row k are both 1s in T(k-1). Copyright Li Zimao 2007-2008-1 SCUECCompute Transitive ClosureTime ComplexitySpace Complexity less space?Copyright Li Zimao 2007-2008-1 SCUECFloyds Algorithm: All pairs shortest paths All pairs shortest paths problem: In a weighted graph, find shortest paths betwee

10、n every pair of vertices.Applicable to: undirected and directed weighted graphs; no negative weight.Same idea as the Warshalls algorithm : construct solution through series of matrices D(0) , D(1), , D(n) Example:34214161530 4 1 0 6 3 0 5 1 00 4 1 0 4 3 0 6 5 1 0weight matrixdistance matrixdij(k) =

11、length of the shortest path from i to j with each vertex numbered no higher than k.Copyright Li Zimao 2007-2008-1 SCUECFloyds AlgorithmD(k) : allow 1, 2, , k to be intermediate vertices.In the kth stage, determine whether the introduction of k as a new eligible intermediate vertex will bring about a

12、 shorter path from i to j. dij(k) = mindij(k-1) , dik(k-1) + dkj(k-1) for k 1, dij(0) = wijijkkth stagedij(k-1)dik(k-1)dkj(k-1)Copyright Li Zimao 2007-2008-1 SCUECFloyd AlgorithmTime Complexity: O(n3), Space ?Copyright Li Zimao 2007-2008-1 SCUECFloyd algorithm (less space)Copyright Li Zimao 2007-200

13、8-1 SCUECConstructing a shortest pathFor k=0For k=1Copyright Li Zimao 2007-2008-1 SCUECPrint all-pairs shortest pathsCopyright Li Zimao 2007-2008-1 SCUECExample:15432347-481-526Copyright Li Zimao 2007-2008-1 SCUECD(0)= (0)=D(1)= (1)=Copyright Li Zimao 2007-2008-1 SCUECD(2)= (2)=D(3)= (3)=Copyright L

14、i Zimao 2007-2008-1 SCUECD(4)= (4)=D(5)= (5)=Copyright Li Zimao 2007-2008-1 SCUEC15432347-481-526Shortest path from 1 to 2 in Copyright Li Zimao 2007-2008-1 SCUECThe Knapsack ProblemThe problemFind the most valuable subset of the given n items that fit into a knapsack of capacity W.Consider the foll

15、owing subproblem P(i, j)Find the most valuable subset of the first i items that fit into a knapsack of capacity j, where 1 i n, and 1 j WLet Vi, j be the value of an optimal solution to the above subproblem P(i, j). Goal: Vn, W The question: What is the recurrence relation that expresses a solution

16、to this instance in terms of solutions to smaller subinstances?Copyright Li Zimao 2007-2008-1 SCUECThe Knapsack ProblemThe RecurrenceTwo possibilities for the most valuable subset for the subproblem P(i, j)It does not include the ith item: Vi, j = Vi-1, jIt includes the ith item: Vi, j = vi+ Vi-1, j

17、 wi Vi, j = maxVi-1, j, vi+ Vi-1, j wi , if j wi 0 Vi-1, jif j wi 0V0, j = 0 for j 0 and Vi, 0 = 0 for i 0 Copyright Li Zimao 2007-2008-1 SCUECDynamic Matrix MultiplicationIf we have a series of matrices of different sizes that we need to multiply, the order we do it can have a big impact on the num

18、ber of operationsFor example, if we need to multiply four matrices M1, M2, M3, and M4 of sizes 205, 5 35, 35 4, and 4 25, depending on the order this can take between 3100 and 24,500 multiplicationsCopyright Li Zimao 2007-2008-1 SCUECCopyright Li Zimao 2007-2008-1 SCUECDynamic Matrix Multiplication

19、ProblemInput: a series of matrices M1, M2, , MN with different sizes s1s2, s2s3, , sNsN+1Output: the order of multiplication of these matrices such that the total number of multiplications is minimizedCan you give a solution to this problem?Try all possibilities to find the order, butIt is time cons

20、uming because the number of all possibilities is a Catalan number C(N-1) where Copyright Li Zimao 2007-2008-1 SCUECDynamic Matrix Multiplication: IdeaWe look at the waysto pair the matrices and then combine these into groups of three, and then fourkeep track of the efficiency of these partial result

21、sCopyright Li Zimao 2007-2008-1 SCUECCharacterize the optimal solutionDenote Mi:j (ij)as MiMi+1Mj, our problem is to find the optimal multiplication order of M1: N.Consider Mi:j (ij) and i kj:The optimal value for Mi:j must be the minimum one of the optimal values for Mi:k plus for Mk+1:j plus sisk+1sj+1 for i kj.A key property:If Mi: j is divide into Mi:k and Mk+1:j, then the optimal order for Mi: j contains the optimal order for Mi:k and Mk+1:j.Copyright Li Zim