Review of Divide and Conquer Lecture02动态规划 ■分:如何分:要考虑合 治:如何治:递归+临界条件下使用其它方 ■合:艺术!! ■递推公式。T(n)=T(n/b)+f(n) ■ Master定理:控制定理 Strassen矩阵乘法 矩阵乘法是线性代数中最常见的问题之一,它在数值计 ■矩阵相乘的分治算法( Strassen) Cj=∑Ak]BAⅡ ■其它的算法 要℃1每计题B的 元素所需的计算时间为0(n3) 20世纪60年代末期, Strassen采用了类似于在大整数乘 法中用过的分治技术,将计第2个阶矩阵乘积所需的计算时 其基本思想还是使用分治法。 清华太学未证想 将矩阵A,B和C中每一 分块成4个大小相等的子 如果n=2,则2个阶方阵的乘积可以直接计算出来 矩阵【假设n是2幂】,每个子矩阵都是(n/2)x(n2) 巨阵的阶大于时,为求2个 的方阵。由此可将方程 C=AB重写为 C1C12_4141TB1B 阶方阵的加法。2个(n2)×(n2)矩阵的加法显然 CnC2L41A2⊥B1B2 以在O(n2)时间内完成。因此,上述分治法的计算时间 耗费T 利用矩阵块乘可得 C12=A1B2+A2B2 O(1) C21=A2B1+A2B2 T(n)=
1 清华大学 宋斌恒 1 Lecture 02 动态规划 清华大学 宋斌恒 清华大学 宋斌恒 2 Review of Divide and Conquer n 分：如何分：要考虑合 n 治：如何治：递归＋临界条件下使用其它方法 n 合：艺术！！！ n 递推公式。T(n)=aT(n/b)+f(n) n Master定理：控制定理 清华大学 宋斌恒 3 Strassen 矩阵乘法 n 矩阵相乘的分治算法（Strassen） n 其它的算法 清华大学 宋斌恒 4 矩阵乘法是线性代数中最常见的问题之一，它在数值计 算中有广泛的应用。设A和B是2个n×n矩阵，它们的乘积 AB同样是一个n×n矩阵。A和B的乘积矩阵C中元素C[i][j]定 义为： 若依此定义来计算A和B的乘积矩阵C，则每计算C的一 个元素C[i][j]，需要做n次乘法运算和n－1次加法运算。因 此，算出矩阵C中的n 2个元素所需的计算时间为O（n 3）。 20世纪60年代末期，Strassen采用了类似于在大整数乘 法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时 间改进到O（n log7）= O（n 2.81）, 其基本思想还是使用分治法。 å= = n k C i j A i k B k j 1 [ ][ ] [ ][ ] [ ][ ] 清华大学 宋斌恒 5 将矩阵A，B和C中每一矩阵都分块成4个大小相等的子 矩阵【假设n是2幂】，每个子矩阵都是（n/2）×（n/2） 的方阵。由此可将方程 C＝AB重写为： 利用矩阵块乘可得： ú û ù ê ë é ú û ù ê ë é =ú û ù ê ë é 21 22 11 12 21 22 11 12 21 22 11 12 B B B B A A A A C C C C 22 21 12 22 22 21 21 11 22 21 12 11 12 12 22 11 11 11 12 21 C A B A B C A B A B C A B A B C A B A B = + = + = + = + 清华大学 宋斌恒 6 如果n＝2，则2个2阶方阵的乘积可以直接计算出来， 共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个 子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降 为2。由此产生分治降阶的递归算法。依此算法，计算2个 n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2 阶方阵的加法。2个（ n/2）×（ n/2）矩阵的加法显然可 以在O（n 2）时间内完成。因此，上述分治法的计算时间 耗费T（n）应满足： î í ì + > = = 8 ( / 2) ( ) 2 (1) 2 ( ) 2 T n O n n O n T n
这个递归方程的解仍然是T(n)=O(m)。因此 该方法并不比用原始定义直接计算更有效。究其原 只用7次乘法运算 因,乃是由于该方法并没有减少矩阵的乘法次数 而矩阵乘法耗费的时间要比矩阵加(减)法耗费的 Strassen发现通过7次乘法运算: 时间多得多。要想改进矩阵乘法的计算时间复杂 性 须减少乘法运算 MAu(B1-B2 M2=(A1+A12)B 按照上述分治法的思想可以看出,要想减少乘 M3=(A21+A2)B 法运算次数,关键在于计算2个2阶方阵的乘积时 否用少于8次乘法运算。 Strassen提出了一种新的 算法来计算2个2阶方阵的乘积 M5=(A1+Az)(Bn+Bz M=(A12-Az)(B21+B2) 得到C1等值 效果 =M5+M4-M2+M6 C12=M1+M C21=M3+M4 T(n) O(1) C22=M5+M-M3-M7 77(m/2)+O(n)n>2 比速方的时向复H比含超闻 清华太学未证想 Strassen是如何发现的? 讨论 ■谁知道? 一种可能的方法:分析法 Hopcroft和Ker在1971年已经证明,计算个2×2矩阵 乘积,7次乘法是必要的 strassen之后又有许多算法改进了矩阵乘法的计算时间 8种基本元素A月1 复杂性。目前最好的计算时间上界是On2) ■有可能用少于8次乘法完成 实际使用很少,有4条理由 如何利用7次乘法计算【具体参见P736】? 1.阶数低系数大【 Cross point,不同情况下n=8 Dignam 12[ Huss-Lederman20实嗣,用试验方法】 2.稀疏矩阵有更好方法 3.数值稳定性不够 4.占用空间大
2 清华大学 宋斌恒 7 这个递归方程的解仍然是T(n)= O(n3)。因此， 该方法并不比用原始定义直接计算更有效。究其原 因，乃是由于该方法并没有减少矩阵的乘法次数。 而矩阵乘法耗费的时间要比矩阵加（减）法耗费的 时间多得多。要想改进矩阵乘法的计算时间复杂 性，必须减少乘法运算。 按照上述分治法的思想可以看出，要想减少乘 法运算次数，关键在于计算2个2阶方阵的乘积时， 能否用少于8次乘法运算。Strassen提出了一种新的 算法来计算2个2阶方阵的乘积。 清华大学 宋斌恒 8 只用7次乘法运算 Strassen发现通过7次乘法运算： M1=A11(B12－B22) M2=(A11+A12) B22 M3=(A21+A22) B11 M4=A22(B21－B11) M5=(A11+A22) (B11+B22) M6=(A12 － A22) (B21+B22) M7=(A11－ A21) (B11+B12) 清华大学 宋斌恒 9 得到C11等值 C11＝M5＋M4－M2＋ M6 C12＝M1＋M2 C21＝M3＋M4 C22＝M5＋M1－M3－ M7 清华大学 宋斌恒 10 效果 Strassen矩阵乘法中，用了7次对于n/2阶矩阵乘的递归调 用和18次n/2阶矩阵的加减运算。由此可知，该算法所 需的计算时间T(n)满足如下的递归方程： 解此递归方程得T(n) =O(n log7) ≈ O(n2.81)。由此可 见，Strassen矩阵乘法的计算时间复杂性比普通矩阵 乘法有较大改进。 î í ì + > = = 7 ( / 2) ( ) 2 (1) 2 ( ) 2 T n O n n O n T n 清华大学 宋斌恒 11 Strassen是如何发现的？ n 谁知道？ n 一种可能的方法：分析法 n 4个式子 n 8种基本元素AijBij n 有可能用少于8次乘法完成 n 如何利用7次乘法计算【具体参见P736】？ 清华大学 宋斌恒 12 n Hopcroft和Kerr在1971年已经证明，计算2个 2 ×2矩阵 的乘积，7次乘法是必要的。 n Strassen之后又有许多算法改进了矩阵乘法的计算时间 复杂性。目前最好的计算时间上界是O(n2.376)。 n 实际使用很少，有4条理由 1. 阶数低系数大【Cross Point, 不同情况下n = 8[Hignam], 12[Huss-Lederman], 20[ 实际]，用试验方法】 2. 稀疏矩阵有更好方法 3. 数值稳定性不够 4. 占用空间大 讨论
有关算法的实现和实用化 Assembly line scheduling ■ Strassen算法实现注意事项: 如何一般化? ■递归到什么程度? ■接口如何设计 接口说明书内容是什么 ■如何针对接口进行编程和编程测试 I A manufacturing problem, See p 325 for detail Problem analysis a For the above assembly_problem, please find Optimal solutions and optimal structural he fastest way to complete the work for any Optimal problems and its optimal sub- ven assembly work instance a What is a problem? 2 Afastest way from start to any station a What is an instance 3 a fastest way from any one to other station Space of sub-problems 清华太学未证想 Mathematical model of the Solution Solution: A way from start to the er a How to express a solution? a Sub-problem solution: a way from start to a a We use a string A=to middle station solution, where a, belongs to (1, 2)means the ih station in line 1 or line 2
3 清华大学 宋斌恒 13 有关算法的实现和实用化 n Strassen算法实现注意事项： n 如何一般化？ n 递归到什么程度？ n 接口如何设计？ n 接口说明书内容是什么？ n 异常如何处理 n 如何针对接口进行编程和编程测试。 清华大学 宋斌恒 14 Assembly line scheduling n A manufacturing problem, See p.325 for detail. a1,1 a1,2 a1,3 a1,n a2,1 t2,1 a2,2 t1,1 a2,3 a2,n t2,2 t1,2 Start e2 e1 x2 x1 end Station1,1 Station1,2 Station1,3 Station1,n Station2,1 Station2,2 Station2,3 Station2,n 清华大学 宋斌恒 15 Problem n For the above assembly problem, please find the fastest way to complete the work for any given assembly work instance. n Thinking … … n What is a problem? n What is an instance ? 清华大学 宋斌恒 16 Analysis: n Optimal solutions and optimal structural. n Optimal problems and its optimal subproblems: 1. A fastest way from start to end 2. A fastest way from start to any station 3. A fastest way from any one to other station n ? Space of sub-problems 清华大学 宋斌恒 17 Solution n Solution: A way from start to the end n Sub-problem solution: a way from start to a middle station 清华大学 宋斌恒 18 Mathematical Model of the solution n How to express a solution? n We use a string A= to express a solution, where ai belongs to {1,2} means the i th station in line 1 or line 2
Cost function[成本函数] Phase cost function f(1122,2,1,1>) Cost function for computing the cost of starting at some elta 0j1,1222,1,1>) a12+1+t12+1 a23+ Optimal value Phase optimal value function a F= minimum f(A): A is a solution We define the function a An optimal solution A takes the optimal value F(ij)=minimum F(i,j, s): s is the stations used in the work between step i to step j. 1 F(ij is the optimal solution between the two steps. FiO=the fastest possible time to get a chassis from the starting point through station S A recursive solution Starting costs B F0=the fastest possible time to get a chassis the stating point through station f111=e1+a1 Then the fastest time is f21=e2+a21 F=min(,(n]+x,, f2nJ+x2) please see page 327
4 清华大学 宋斌恒 19 Cost function[成本函数] f() = e1+a11 +a12+t12 +a23+a24+a25+t25 +a16 +a17+x1 清华大学 宋斌恒 20 Phase cost function Cost function for computing the cost of starting at some station i to the station j. i !=start, j != end f(i,j,) = a1,1+i-1 +a1,2+i- 1+t1,2+i-1 +a2,3+i- 1+a2,4+i-1+a2,5+i-1+t2,5+i-1 +a1,6+i- 1 +a1,7+i- 1 清华大学 宋斌恒 21 Optimal value n Optimal value: n F = minimum {f(A): A is a solution} n An optimal solution A takes the optimal value: f(A)=F. 清华大学 宋斌恒 22 Phase optimal value function We define the function F(i,j)=minimum {F(i,j, s): s is the stations used in the work between step i to step j. } F(i,j) is the optimal solution between the two steps. Fi [j]=the fastest possible time to get a chassis from the starting point through station Si,j 清华大学 宋斌恒 23 A recursive solution n Fi [j]=the fastest possible time to get a chassis from the stating point through station Si,j n Then the fastest time is n F* = min(f1 [n] + x1 , f2 [n]+x2 ) please see page 327 清华大学 宋斌恒 24 Starting costs nf1 [1] = e1 + a1,1 nf2 [1] = e2 + a2,1
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 computed
5 清华大学 宋斌恒 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 …
Find the least operation to get the The structure of an optimal a Direct divide and conquer method, one get the a If a parenthesis is an optimal one then its sub parenthesis is optimal for the su Pm)=∑Pk)(n-k) a Catalan number grows as? (4/n 2 A recursive solution Computing the optimal costs m[i,jI 0 if i=j n小 minmei. 1+mik+1 /1+P-PP, if i<j 437525003500 清华太学未证想 A2 A3 A4 A5A6 Constructing an optimal solution Elements of dynamic programming ■S[』 records the values of k such that the optimal a Two important points enthesization of AA A, splits the product between A and A.t. m Optimal structure m Overlapping sub-problems
6 清华大学 宋斌恒 31 Find the least operation to get the result n Direct divide and conquer method, one get the recurrence formula n Catalan number grows as ? (4n /n3/2) å - = = - 1 1 ( ) ( ) ( ) n k P n P k P n k 清华大学 宋斌恒 32 The structure of an optimal parenthesization n If a parenthesis is an optimal one then its sub parenthesis is optimal for the sub-problems 清华大学 宋斌恒 33 A recursive solution { } ïî ï í ì + + + < = = - £ £ mi k m k j p p p i j i j mi j i k j i k j min [ , ] [ 1, ] if 0 if [ , ] 1 清华大学 宋斌恒 34 Computing the optimal costs 15125 11875 10500 9375 7125 7875 4375 2500 3500 5375 15750 2625 750 1000 0 0 0 0 0 0 5000 m[i,j] i=1 i=6 i=2 j=1 j=6 A1 A2 A3 A4 A5 A6 Matrix dimension 30,35,15,5,10,20,25 清华大学 宋斌恒 35 Constructing an optimal solution n S[i,j] records the values of k such that the optimal parenthesization of AiAi+1… Aj splits the product between Ak and Ak+1. 清华大学 宋斌恒 36 Elements of dynamic programming n Two important points n Optimal structure n Overlapping sub-problems
Optimal substructure a principle How to find the optimal substructure a Keep the sub-problem space as simple m Make a choice to split the problem into one or more sub-problems ■ Just assume a choice with such a choice, you should determine the space of sub-problems a Prove your choice is optimal by cut and paste Two factors Which problems is suitable? ms are nv a Shortest path in a graph ptimal solution? a Longest path in a graph a How many choices you should determine which sub-problems should be used in an optimal solution? 清华太学未证想 Overlapping sub-problems Reconstructing an optimal solution a Need some other information to constructing the optimal solution, generally e choice of the sub-problems
7 清华大学 宋斌恒 37 Optimal substructure n How to find the optimal substructure n Make a choice to split the problem into one or more sub-problems n Just assume a choice n With such a choice, you should determine the space of sub-problems. n Prove your choice is optimal by cut and paste technique. 清华大学 宋斌恒 38 A principle n Keep the sub-problem space as simple as possible! 清华大学 宋斌恒 39 Two factors n How many sub-problems are involved in an optimal solution? n How many choices you should determine which sub-problems should be used in an optimal solution? 清华大学 宋斌恒 40 Which problems is suitable? n Shortest path in a graph n Longest path in a graph 清华大学 宋斌恒 41 Overlapping sub-problems n Is the way to reduce the computation 清华大学 宋斌恒 42 Reconstructing an optimal solution n Need some other information to reconstructing the optimal solution, generally, the choice of the sub-problems