复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 08 Dynamic programming

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

ynamic programming a Dynamic programming is typically applied to optimization problems a There can be many possible solutions in optimization pI robes a Each solution has a value. and we wish to find a solution with the optimal(minimum or maximum) value

Dynamic programming ‡ Dynamic programming is typically applied to optimization problems. ‡ There can be many possible solutions in optimization problems. ‡ Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value

Manufacturing problem Station Station Station Station Station Station S Assembly line179-348-(4 (2 3 Chassis Completed enters auto exits Assemblyline2(8(5(6 5 Station Station Station Station Station Station

Manufacturing problem 7 9 3 4 3 2 2 4 8 4 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6

Brute-force Check every way through a factory and choose the fastest way Analysis Checking =O(n) time per way 2n possible ways to choose stations o Worst-case running time =O(n2n) exponential time It is infeasible!

Brute-force Check every way through a factory and choose the fastest way. Analysis y Checking = O(n) time per way. y 2n possible ways to choose stations. y Worst-case running time = O(n2n) = exponential time. It is infeasible!

Structure of manufacturing problem a An optimal solution to a problem(finding the fastest way though station Si i)contains within it an optimal solution to subproblems(finding the fastest way through either Si-or a Suppose that the fastest way through station S is either the fastest way througl h station y Chen directly through station Si, or the fastest way through station Si-I,a transfer from line 1 to line 1, and then through station S1/ a Suppose that the fastest way through station S is througl station Si-I. The key observation is that the chassis must have taken a fastest way from the starting point through station Si-1

Structure of manufacturing problem ‡ An optimal solution to a problem (finding the fastest way though station Si,j) contains within it an optimal solution to subproblems (finding the fastest way through either S1,j −1 or S2,j −1) ‡ Suppose that the fastest way through station S1,j is either y the fastest way through station S1,j −1 and then directly through station S1,j, or y the fastest way through station S2,j −1, a transfer from line 1 to line 1, and then through station S1,j . ‡ Suppose that the fastest way through station S1,j is through station S1,j −1. The key observation is that the chassis must have taken a fastest way from the starting point through station S1,j −1

Recursive solution fig] denote the fastest possible time to get a chassis from the starting point through station ei denote an entry time for the chassis to enter assembly line denote an exit time for the completed auto to exit assembly line i iy denote the assembly time required at station S denote the time to transfer a chassis away from assembly line i after through station S Our ultimate goal is f=mingi[n]+x,f2[n]+x2)

Recursive solution denote the fastest possible time to get a chassis from the starting point through station Sij. Our ultimate goal is: f * = min(f1 [ n] + x 1, f2 [ n] + x 2 ). denote an entry time for the chassis to enter assembly line i. denote an exit time for the completed auto to exit assembly line i. denote the assembly time required at station Sij. denote the time to transfer a chassis away from assembly line i after through station Sij. fi [j ] ei xi ai,j ti,j

Recursive solution(cont We obtain the recursive equations e,t a f min(1-11+a1/27-1+t21+a1,)ifj22 if j=I falL min(-1]+a2yV-1]+11+a2)ifj22 Lili denote the line number i, whose station j-1 is used in a fastest way through station s

Recursive solution (cont.) We obtain the recursive equations f1 [j] = e 1 + a1,1 if j = 1, min(f1 [j − 1] + a1,j, f2 [j − 1] + t2,j − 1+ a1,j) if j ≥ 2. f2 [j] = e 2 + a2,1 if j = 1, min(f2 [j − 1] + a2,j, f1 [j − 1] + t1,j − 1+ a2,j) if j ≥ 2. denote the line number i, whose station j − 1 is used in a fastest way through station Sij. li [j ]

Computing the fastest times Station Station Station StationStation Station S Assembly line 1 4 p Chassis Completed enters auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123 23456 f lUI

Computing the fastest times 7 9 3 4 3 2 2 4 8 4 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 12345 6 2345 6 f1[j] j f2[j] l1[j] j l2[j]

Computing the fastest times Station Station Station StationStation Station S Assembly line 1 4 Chassis Completed enters auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123 23456 fun lUI

Computing the fastest times 7 9 3 4 3 2 2 4 8 4 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 12345 6 2345 6 f1[j] j f2[j] l1[j] j l2[j]

Computing the fastest times Station Station Station StationStation Station S Assembly line 1 4 p Chassis Completed enters auto exits Assembly line 2(8(5(64 Station Station Station Station Station Station j123 23456 lUI

Computing the fastest times 7 9 3 4 3 2 2 4 8 4 8 5 6 4 5 7 2 2 3 1 1 2 3 2 4 1 Chassis enters Assembly line 1 Completed auto exits Assembly line 2 Station S1,1 Station S1,2 Station S1,3 Station S1,4 Station S1,5 Station S1,6 Station S2,1 Station S2,2 Station S2,3 Station S2,4 Station S2,5 Station S2,6 9 12345 6 12 2345 6 f1[j] j f2[j] l1[j] j l2[j]