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