文档介绍：1
动态规划技术
2
主要内容
算法总体思想
动态规划步骤
矩阵连乘问题
动态规划算法的基本要素
最长公共子序列问题
多边形游戏
0-1背包问题
凸多边形最优三角剖分
流水作业调度
3
算法总体思想
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
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)
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)
T(n)
6
动态规划基本步骤
找出最优解的性质,并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息,构造最优解。
7
矩阵连乘问题
给定n个矩阵, 其中与是可乘的, 。考察这n个矩阵的连乘积
由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
完全加括号的矩阵连乘积。
8
矩阵连乘问题
(1)单个矩阵是完全加括号的;
(2)矩阵连乘积是完全加括号的,则可
表示为2个完全加括号的矩阵连乘积和
的乘积并加括号,即
16000, 10500, 36000, 87500, 34500
完全加括号的矩阵连乘积可递归地定义为:
设有四个矩阵,它们的维数分别是:
总共有五种完全加括号的方式
9
矩阵连乘问题
穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。
算法复杂度分析:
对于n个矩阵的连乘积,设其不同的计算次序为P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:
10
矩阵连乘问题
动态规划
将矩阵连乘积简记为A[i:j] ,这里i≤j
考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵
Ak和Ak+1之间将矩阵链断开,i≤k<j,则其相应完全
加括号方式为
计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相乘的计算量