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中的 n2个元素所需的计算时间为 O（ n3）。 20世纪 60年代末期 ， Strassen采用了类似于在大整数乘 法中用过的分治技术 ， 将计算 2个 n阶矩阵乘积所需的计算时 间改进到 O（ nlog7） = O（ n2.81） , 其基本思想还是使用分治法 。 ∑ = = n k jkBkiAjiC 1 ]][[]][[]][[ 清华大学 宋斌恒 5 将矩阵 A， B和 C中每一矩阵都分块成 4个大小相等的子 矩阵 【 假设 n是 2幂 】 ， 每个子矩阵都是 （ n/2） × （ n/2） 的方阵 。 由此可将方程 C＝ AB重写为 ： 利用矩阵块乘可得 ： ?? ? ?? ? ?? ? ?? ?= ?? ? ?? ? 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC 2222122122 2122112121 2212121112 2112111111 BABAC BABAC BABAC BABAC += += += += 清华大学 宋斌恒 6 如果 n＝ 2， 则 2个 2阶方阵的乘积可以直接计算出来 ， 共需 8次乘法和 4次加法 。 当子矩阵的阶大于 2时 ， 为求 2个 子矩阵的积 ， 可以继续将子矩阵分块 ， 直到子矩阵的阶降 为 2。 由此产生分治降阶的递归算法 。 依此算法 ， 计算 2个 n阶方阵的乘积转化为计算 8个 n/2阶方阵的乘积和 4个 n/2 阶方阵的加法 。 2个 （ n/2） × （ n/2） 矩阵的加法显然可 以在 O（ n2） 时间内完成 。 因此 ， 上述分治法的计算时间 耗费 T（ n） 应满足 ： ?? ? >+ == 2)()2/(8 2)1()( 2 nnOnT nOnT 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矩阵乘法的计算时间复杂性比普通矩阵 乘法有较大改进 。 ?? ? >+ == 2)()2/(7 2)1()( 2 nnOnT nOnT 清华大学 宋斌恒 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. 占用空间大 讨论 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 sub- problems: 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= <a1,a2,… ,an> to express a solution, where ai belongs to {1,2} means the ith station in line 1 or line 2. 4 清华大学 宋斌恒 19 Cost function[成本函数 ] f(<1,1,2,2,2,1,1>) = 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,<1,1,2,2,2,1,1>) = 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 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 li[j] nFor help tracking the work route, it needs to save the information of line switching: nli[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=CA 2 n … 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 knPkPnP 清华大学 宋斌恒 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 { }???? ? <+++ = = ?≤≤ jipppjkmkim ji jim jkijki if ],1[],[min if 0 ],[ 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 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