算法导论Let9-Dynamic Programming 1.ppt

1 Simple Review Order Statistics Expected linear time selection Main idea: PARTITION Worst-case Θ(n2) Worst-case linear time selection Generate a good pivot recursively. Design and Analysis of Algorithms Dynamic Programming(Ch15)Part 1 Manufacturing Problem Assembly-Line Scheduling Two parallel assembly lines in a factory, lines 1 and 2 Each line has n stations Si,1…Si,n , i =1, 2 For each j, S1, j does the same thing as S2, j , but it may take a different amount of assembly time ai, j Transferring away from line i after stage j costs ti, j , i=1, 2 and j =1, 2, … , n-1 Also entry time ei and exit time xi at beginning and end Assembly Lines n stations on each line: S1,1…S1,n and S2,1…S2,n . ai, j : time required on line i at station j. Transferring times: ti, j . Entry and exit time: e1 , e2 , x1 , x2. Goal: Find the fastest path through the factory. (Trying all possibilities is not tractable.) Assembly Lines Properties of the optimal solution: consider the fastest way of exiting station S1,j. if j = 1, then there’s only one way, if j ≥ 2, then in order to exit station j, we must have 1. either gone through station S1,j-1, or 2. gone through station S2,j-1 and transferred to S1,j. In the first case, we must have used the fastest way of exiting S1,j-1. In the second case, we must have used the fastest way of exiting S2,j-1. Assembly Lines Key observation. An optimal solution to the problem (fastest way through S1,j) contains within it an optimal solution to subproblems (fastest way through S1,j-1 or S2,j-1). [Optimal substructure] It’s easy to write a recursive solution to the problem now. Homework 15.1-1, 15.2-1 *Software School of XiDian University *Software School of XiDian University ALS Design and Analysis of Algorithms Dynamic Programming Topics: Dynamic Programming (DP) paradigm Assembly-Line Scheduling Matrix-Chain Multiplication Optimization Problems A design technique, like divide-and-conquer. Works bottom-up rather than top-down. Useful for