Recursive formula Function Ii] f=mn(f(-1)+a1 a For help tracking the work route, it needs to 21+2+a1) save the information of line switching f=mn(2(-1)+a2, f{1+t1+a2y 到工作台S1的最快路径的上一个工作台所在 的装配线号码 Computing the fastest times Computing the optimal solution ■ Do it in the class ■ Do it in the class 小结 Matrix-chain multiplication ■ Difference with Divide an ■AA2A3-An Repeatedly solving the sub-problems a The nature way to get the multiplication of a ■ Applied fields ■ The four steps ■C=A C=CA m Recursively define the value of an optimal solution m Compute the value of an optimal solution in a bottom up fashion a Construct an optimal solution from computed5 清华大学 宋斌恒 25 Recursive formula nf1 [j] = min(f1 (j-1) +a1,j , f2 [j-1]+t2,j-1+a1,j) nf2 [j] = min(f2 (j-1) +a2,j , f1 [j-1]+t1,j-1+a2,j) 清华大学 宋斌恒 26 Function l i [j] n For help tracking the work route, it needs to save the information of line switching: n l i [j] means the line number whose station j-1 is used in a fastest way through station Si,j . 到工作台Si,j的最快路径的上一个工作台所在 的装配线号码 清华大学 宋斌恒 27 Computing the fastest times nDo it in the class 清华大学 宋斌恒 28 Computing the optimal solution n Do it in the class 清华大学 宋斌恒 29 小结 n Difference with Divide and conquer n Repeatedly solving the sub-problems n Applied fields n Optimization problems (Many solution but ) n The four steps n Characterize the structure of an optimal solution n Recursively define the value of an optimal solution n Compute the value of an optimal solution in a bottom - up fashion n Construct an optimal solution from computed information 清华大学 宋斌恒 30 Matrix-chain multiplication n A1A2A3… An n The nature way to get the multiplication of a series of matrices: n C=A1 n C=CA2 n …