文档介绍：算法分析与设计课件 动态规划法
*
第一页，共138页
通过应用范例学****动态规划算法设计策略。
（1）矩阵连乘问题；
（2）最长公共子序列；
（3）最大子段和
（4）凸多边形最优三角剖分；
（5）多边形游戏；
（6）图像压缩；
（7）电路布线；
（8）流水作业调度；
（9）背包问题；
（10）最优二叉搜索树。
*
第二页，共138页
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)
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
算法总体思想
*
第三页，共138页
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
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)
*
第四页，共138页
动态规划基本步骤
找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
*
第五页，共138页
假定A为100×1矩阵,B为1×100矩阵，C为100×1矩阵,(A*B) *C需乘法数为
100×1×100＋100×100×1＝20000
而 A* (B*C) 所需乘法数为1×100×1＋100×1×1＝200
长度q的矩阵乘法链有指数量级Ω(2n)的可能的相乘方式(有q个叶节点的二叉数的数目).
要找一种相乘方式,使得元素乘法数最少
*
第六页，共138页
16000, 10500, 36000, 87500, 34500
完全加括号的矩阵连乘积可递归地定义为：
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积A和B的乘积并加括号，即A=(BC)
设有四个矩阵A,B,C,D，它们的维数分别是：
矩阵连乘积
总共有五中完全加括号的方式
*
第七页，共138页
给定n个矩阵 ， 其中 与 是可乘的。考察这n个矩阵的连乘积
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
*
第八页，共138页
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
算法复杂度分析：
对于n个矩阵的连乘积，设其不同的计算次序为P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：
*
第九页，共138页
动态规划
将矩阵连乘积AiAi+1…Aj ，简记为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]相乘的计算量
*
第十页，共138页