算法设计-LEC8(2)

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

2.递归解(A Recursive Solution) Define the value of an optimal solution in terms of the optimal solution to subproblems(利用子问题的最优解，通过递归的方式求解原问题的最优解) Assembly line subproblems(装配线排程子问题)– Finding the fastest way through station j on both lines

, j= 1, 2,…, n (即是经过两条第j个工作台的最快线路问题， j= 1, 2,…, n )

2.递归解(A Recursive Solution) f*= the fastest time to get through the entire factory(问题最优解，完成所有装配过程的最短时间) fi[j]= the fastest time to get from the starting point through station Si,j(表示从起点经过Si,j工序的最短时间)f*= min (f1[n]+ x1, f2[n]+ x2)

13

14

2.递归解(A Recursive Solution) Compute fi[j] for j= 2, 3,…,n, and i= 1, 2(对于i= 1, 2和j= 2, 3,…,n,计算fi[j] ) Fastest way through S1, j is either:(经过S1, j的两种情况)– the way through S1, j - 1 then directly through S1, j, or(经过S1, j 1 ) f1[j - 1]+ a1,j

2.递归解(A Recursive Solution) fi[j]= the fastest time to get from the starting point through station Si,j (从起点经过Si,j工序的最短时间) j= 1 (getting through station 1)(经过工作台1的最短时间) f1[1]= e1+ a1,1 f2[1]= e2+ a2,1

– the way through S2, j - 1, transfer from line 2 to line 1, then S1,j-1 through S1, j (经过S2, j - 1 ) f2[j -1]+ t2,j-1+ a1,ja1,j-1 t2,j-1 f1[j]= min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j) a2,j-1 S2,j-1

S1,j a1,j

15

16

2.递归解(A Recursive Solution)e1+ a1,1 min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j) e2+ a2,1 if j= 1 if j≥ 2 if j= 1

3.计算最优解(Computing the Optimal Solution)f*= min (f1[n]+ x1, f2[n]+ x2)(自顶向下求最优解) f1[j]= min(f2[j - 1]+ a2,j,f1[j -1]+ t1,j-1+ a2,j)1 2 f1(2) f2(2) 3 f1(3) f2(3) 4 times 4 f1(4) f2(4) 2 times 5 f1(5) f2(5)

f1[j]=

f1[j] f2[j]

f1(1) f2(1)

f2[j]=

min(f2[j - 1]+ a2,j,f1[j -1]+ t1,j-1+ a2,j) if j≥ 2

Solving top-down would result in exponential running time (自顶向下导致指数增长的计算时间)17 18

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

3.计算最优解(Computing the Optimal Solution) For j≥ 2, each value fi[j] depends only on the values of f1[j– 1] and f2[j - 1](对于j≥ 2,计算fi[j]与f1[j– 1]和f2[j - 1]的值相关) Compute the values of fi[j](如何计算fi[j]? )– in increasing order of j( j递增)1 2 3

4、构造最优方案(Construct the Optimal Solution) We need the sequence of what line has been used at each station (表示哪条装配线哪些工序台被利用的序列)– li[j]– the line number (1, 2) whose station (j - 1) has been used to get in fastest time through Si,j, j= 2, 3,…, n( li[j]表示经过Si,j的最优排程序列)

increasing j4 5

f1[j] f2[j] Bottom-up approach(自底向上的方法)– First find optimal solutions to subproblems(求解子问题的解)– Find an optimal solution to the problem from the subproblems(从子问题的解构造出原问题的最优解)19

– l* - the line whose station n is used to get in the fastest way through the entire fac

tory( l*表示整个排程问题的最优序列)

increasing j4

2

3

5

l1[j] l2[j]20

1. f1[1]← e1+ a1,1 3. for j← 2 to n 4. 5. 6. 7. 8. 9. 10. 11. 12.21

最优排程算法：FASTEST-WAY(a, t, e, x, n)Compute initial values of f1 and f2(初值计算)

2. f2[1]← e2+ a2,1

do if f1[j - 1]+ a1,j≤ f2[j - 1]+ t2, j-1+ a1, j then f1[j]← f1[j - 1]+ a1, j l1[j]← 1 else f1[j]← f2[j - 1]+ t2, j-1+ a1, j l1[j]← 2 if f2[j - 1]+ a2, j≤ f1[j - 1]+ t1, j-1+ a2, j then f2[j]← f2[j - 1]+ a2, j l2[j]← 2 else f2[j]← f1[j - 1]+ t1, j-1+ a2, j l2[j]← 1Compute the values of f2[j] and l2[j] Compute the values of f1[j] and l1[j]

e1+ a1,1, f1[j]= min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j)1 2 3 4 5

if j= 1 if j≥ 2

f1[j] f2[j]

9 12

18[1] 16[1]

20[2] 22[2]

24[1] 25[1]

32[1] 30[2]

f*=

35[1]

13.

22

FASTEST-WAY(a, t, e, x, n) (cont.)14. if f1[n]+ x1≤ f2[n]+ x2 15. 16. 17. 18. then f*= f1[n]+ x1 l*= 1 else f*= f2[n]+ x2 l*= 2Compute the values of the fastest time through the entire factory(最终的最优解)

4.构造最优的排程方案(Construct an Optimal Solution) Alg.: PRINT-STATIONS(l, n) i← l* print“line” i“, station” n for j← n downto 2 do i←li[j] print“line” i“, station” j - 11 2 3 4 5

line 1, station 5 line 1, station 4 line 1, station 3 line 2, station 2 line 1, station 1

f1[j]/l1[j] f2[j]/l2[j]23

9 12

18[1] 16[1]

20[2] 22[2]

24[1] 25[1]

32[1] 30[2]

l*= 1

24

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

动态规划算法(Dynamic Programming Algorithm)1.–

矩阵链相乘(Matrix-Chain Multiplication)Problem: given a sequence A1, A2,…, An , compute the product:(问题：给定矩阵序列A1, A2,…, An,求它们的积) A1 A2 An Matrix compatibility:(矩阵相乘的条件) C=A B colA= rowB rowC= rowA colC= colB A1 A2 Ai Ai+1 An coli= rowi+126

Characterize the structure of an optimal solution(最优解的结构特征)Fastest time through a station depends on the fastest time on previous stations (比如，通过某个工作台的最快路线与通过前一工作台的最快路线相关)

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究算法设计-LEC8(2)全文阅读和word下载服务。