清华大学出版社：《算法设计与分析》课程教学资源（PPT课件讲稿）第3章 动态规划

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第3章动态规划

1 第3章 动态规划

清华大学出版社 TSINGHUA UNIVERSITY PRESS 动态规划算法与分治法类似,其基本思想也是将待求 解问题分解成若干个子问题 T(n) T(n/2) Tn/2) T(n/2) Tn/2)

2 • 动态规划算法与分治法类似，其基本思想也是将待求 解问题分解成若干个子问题 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) =

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 动态规划算法与分治法类似,其基本思想也是将待求 解问题分解成若干个子问题 T(n) T(n/2) Tn/2) T(n/2) Tn/2)

3 算法总体思想 • 动态规划算法与分治法类似，其基本思想也是将待求 解问题分解成若干个子问题 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) =

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 ·但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时,有些子问题被重复计算了许多次。 T(n) T424和2424)TAA4如2)Ta4(4厂(4)T白4(a44Ja

4 • 但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解 时，有些子问题被重复计算了许多次。 算法总体思想 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4)

清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法总体思想 ·如果能够保存已解决的子问题的答案,而在需要时再 找出已求得的答案,就可以避免大量重复计算,从而 得到多项式时间算法。 Those who cannot remember the past are doomed to repeat it -George Santayana, The life of Reason Book Introduction and Reason in Common Sense(1905)

5 • 如果能够保存已解决的子问题的答案，而在需要时再 找出已求得的答案，就可以避免大量重复计算，从而 得到多项式时间算法。 算法总体思想 = n n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4)T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) Those who cannot remember the past T(n) are doomed to repeat it. -----George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905)

清华大学出版社 TSINGHUA UNIVERSITY PRESS 动态规划基本步骤 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优 解

6 动态规划基本步骤 • 找出最优解的性质，并刻划其结构特征。 • 递归地定义最优值。 • 以自底向上的方式计算出最优值。 • 根据计算最优值时得到的信息，构造最优 解

清华大学出版社 TSINGHUA UNIVERSITY PRESS 完全加括号的矩阵连乘积 ◆完全加括号的矩阵连乘积可递归地定义为 1)单个矩阵是完全加括号的 (2)矩阵连乘积A是完全加括号的,则A可 表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号,即A=(BC) 设有四个矩阵A,B,C,们的维数分别是 A=50×10B=10×40C=40×30D=30×5 ◆总共有五中完全加括号的方式 (A(BC)D))(A(B(CD))((AB(CD) (((ABCD) ((A(BCDD) 16000,10500,36000,87500,34500

7 完全加括号的矩阵连乘积 （1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 A A B C A = (BC) A, B,C, D A= 5010 B =1040 C = 4030 D = 305 (A((BC)D)) ((( AB)C)D) ((A(BC))D) (A(B(CD))) ((AB)(CD)) 16000, 10500, 36000, 87500, 34500 ◆ 完全加括号的矩阵连乘积可递归地定义为： ◆ 设有四个矩阵 ，它们的维数分别是： ◆ 总共有五中完全加括号的方式

清华大学出版社 TSINGHUA UNIVERSITY PRESS 矩阵连乘问题 给定n个矩阵{A,A2,中与是可乘 的,i=12,,}考察这n个矩阵的连乘积 ■由于矩阵乘法满足结合律,所以计算矩阵的连乖可以 有许多不同的计算次序。这种计算次序可以用加括号 的方式来确定。 若一个矩阵连乘积的计算次序完全确定,也就是说该 连乘积已完全加括号,则可以依此次序反复调用2个矩 阵相乘的标准算法计算岀矩阵连乘积

8 矩阵连乘问题 ◼ 给定n个矩阵 ， 其中 与 是可乘 的， 。考察这n个矩阵的连乘积 ◼ 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以 有许多不同的计算次序。这种计算次序可以用加括号 的方式来确定。 ◼ 若一个矩阵连乘积的计算次序完全确定，也就是说该 连乘积已完全加括号，则可以依此次序反复调用2个矩 阵相乘的标准算法计算出矩阵连乘积 { , ,..., } A1 A2 An Ai Ai+1 i =1,2,...,n −1 A A An ... 1 2

清华大学出版社 TSINGHUA UNIVERSITY PRESS 矩阵连乘问题 给定n个矩阵{A1,A2…,An},其中A与A1+1是可乘的 ⅰ=1,2灬…,n-1。如何确定计算矩阵连乖积的计算次序,使得 依此次序计算矩阵连乘积需要的数乘次数最少。 ◆穷举法:列举出所有可能的计算次序,并计算出每一种计 算次序相应需要的数乘次数,从中找出一种数乘次数最少的 计算次序。 算法复杂度分析: 对于n个矩阵的连乘积,设其不同的计算次序为P(n) 由于每种加括号方式都可以分解为两个子矩阵的加括号问题 (A1…Ak)(Ak+1.A1)可以得到关于P(n)的递推式如下: n=1 P(m)=1>P(k)P(n-k)n>1 P(n)=92(4"/n2) k=1

9 矩阵连乘问题 给定n个矩阵｛A1 ,A2 ,…,An｝，其中Ai与Ai+1是可乘的， i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得 依此次序计算矩阵连乘积需要的数乘次数最少。 ◆穷举法：列举出所有可能的计算次序，并计算出每一种计 算次序相应需要的数乘次数，从中找出一种数乘次数最少的 计算次序。 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1 ...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： ( ) (4 / ) 1 1 ( ) ( ) 1 ( ) 1 3/ 2 1 P n n n n P k P n k P n n n k  =       = − =  − =

清华大学出版社 TSINGHUA UNIVERSITY PRESS 矩阵连乘问题 ◆穷举法 ◆动态规划 将矩阵连乘积AAx1A,简记为A[i:j],这里≤j 考察计算A[ⅰ:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开,i≤k<j,则其相应完全 加括号方式为(AA4+1A)(A+A+2…A) 计算量:A[ⅰ:k]的计算量加上A[k+1:j的计算量,再加上 A[i:k]和A[k+1:订相乘的计算量

10 矩阵连乘问题 ◆穷举法 ◆动态规划 将矩阵连乘积 简记为A[i:j] ，这里i≤j Ai Ai Aj ... +1 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全 加括号方式为 ( ... )( ... ) Ai Ai+1 Ak Ak+1 Ak+2 Aj 计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量