算法课件全121301ADA14动态规划二项式系数与全源最短路径

1、Dynamic Programming (1),Chapter 8,Basic Idea and Framework of DP Application to Non-optimization Problem Binomial Coefficient Calculation Application to optimization Problem,2019/6/21,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of This Lecture,At the end of this lecture, you should Master the basic idea of dynamic programming and know the difference between DP and DAC Master the binomial coefficient calculation algorithm Master the basic idea of Floyds algorithm for all-pairs shor

2、test paths problem and analyze the time complexity of Floyds algorithm Master how to get the transitive closure of a digraph,2019/6/21,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Dynamic Programming,Dynamic Programming is a general algorithm design technique for solving problems defined by recurrences with overlapping subproblems. Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems. “Programming” here means “planning”,2019/6/21,5,2012-2013-01 D

3、esign and Analysis of Algorithm SCUN,Binomial Coefficient,This can also be expressed as:,Binomial coefficients are coefficients of the binomial formula:(a + b)n = C(n,0)anb0 + . . . + C(n,k)an-kbk + . . . + C(n,n)a0bn,The equation for the binomial coefficient is:,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Binomial Coefficient,It also shows us how we could use an array to calculate these values,This second form shows us we could set up a recursive algorithm to calculate the bi

4、nomial coefficient,2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Binomial Coefficient Algorithm,BinomialCoefficient(N,k) /Imput: A pair of nonnegative integers nk0 /Output: The value of C(n,k) for i 0 to n do for j 0 to min (i, k) do if j = 0 or j = i Ci, j 1 else C i, j = C i-1, j-1 + Ci-1, j return Cn,k,Space efficiency: (Nk),Time efficiency: (Nk),Key ingredients of an optimization problem be suitable solved by DP Basic idea of DP for solving optimization problem Application t

5、o Graph problem All-pairs shortest-path problem Transitive closure problem Application to Numerical Problem Matrix Chain Multiplication Problem Application to Combinatorial Problem Knapsack Problem,Application of DP to optimization problem,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Two key ingredients,An optimization problem be suitable solved by DP must have two key ingredients:,2019/6/21,10,2012-2013-01 Design and Analysis of Algorithm SCUN,Four steps and Three components,B

6、asic idea of DP for solving optimization problem can be divided into 4 steps Characterize the structure of an optimal solution Recursively define the value of an optimal solution Compute the value of an optimal solution in a bottom-up fashion Construct an optimal solution from computed information The development of a dynamic programming algorithm has three basic components A recurrence relation (for defining the value/cost of an optimal solution); A tabular computation (for computing the value

7、of an optimal solution); A backtracing procedure (for delivering an optimal solution).,2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SCUN,All Pairs Shortest-Paths Problem,Input: A directed graph G = (V, E), and a weight function w: E R. Output: A shortest path for each pair of vertices u and v in V, if it exists. We output: a V V matrix D = (dij), where, dij contains the weight of a shortest path from vertex i to vertex j; and V V matrix = (ij), where ij means the predecessor of j i

8、n a shortest path from vertex i to vertex j.,2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Characterize the structure of the optimal solution,If i, v1, v2 , vk-1, vk, vk+1, , j is the shortest path from i to j, then i, v1, v2, , vk-1, vk and vk, vk+1, , j must be the shortest paths from i to vk and vk to j respectively.,2019/6/21,13,2012-2013-01 Design and Analysis of Algorithm SCUN,Define the Recurrence Relation,. :,. :,k-1,i,j,1,2,k,k+1,n,2019/6/21,14,2012-2013-01 Design and

9、Analysis of Algorithm SCUN,Solve the problem stage by stage (dynamic programming): D(0), D(1), D(2), , D(n) where D(k) contains the shortest path weight with all the intermediate vertices from set 1,2,k. dij(k): shortest path weight from i to j with intermediate vertices (excluding i, j) in the set 1, 2, , k dij(0) = wij (no intermediate vertices at all) Result: D(n) = (dij(n) = (i, j) (because all intermediate vertices are in the set 1, 2, , n),Define the Recurrence Relation,2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,dij(0) = wij if k=0 dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1) if k 1,Define the Recurrence Relation,2019/6/21,16,2012-2013-01 Design and Analysis of Algorithm SCUN,Constructing a shortest path,For k=1,For k=0,2019/6/21,17,2012-2013-01 Design and Analysis of Algorithm SCUN,Floyd algorithm (Example),k=0: d41(0)=2; d42(0)=; d43(0)

《算法课件全121301ADA14动态规划二项式系数与全源最短路径》由会员E****分享，可在线阅读，更多相关《算法课件全121301ADA14动态规划二项式系数与全源最短路径》请在金锄头文库上搜索。