7算法分析及设计 第七讲 动态规划.pdf

算法分析与设计第七讲 动态规划 1 主要内容 动态规划的基本概念 动态规划的基本步骤 动态规划问题求解实例 2 动态规划的求解对象 最优化问题 工程问题中设计参数的选择 有限资源的合理分配 车间作业调度 交通系统的规划 不胜枚举…………. 3 动态规划（dynamic programming） 分治法求解回顾 子问题相互独立，不包含公共子问题 动态规划 与分治法类似，也是将问题分解为规模逐渐减小的 同类型的子问题 与分治法不同，分解所得的子问题很多都是重复的 4 动态规划求解实例-矩阵连乘问题 矩阵连乘问题 （矩阵链乘法） 一般描述： 对于给定的n个矩阵，M ，M ，…，M ，其中矩 1 2 n 阵M 和M 是可乘的，要求确定计算矩阵连乘积 i j （M M …M ）的计算次序，使得按照该次数计算 1 2 n 矩阵连乘积时需要的乘法次数最少 5 矩阵连乘问题 例，设有矩阵M ,M ,M ,M 1 2 3 4 其维数分别是：1020, 2050,501 ,1100 现要求出这4个矩阵相乘的结果 计算次序可以通过加括号的方式确定 当n很大时，n个矩阵连乘的加括号的方法 数是指数量级的，逐一检查不现实 6 矩阵连乘问题 目标：求出矩阵连乘M M ┅M M （ij ） i i+1 j -1 j 所需的最少乘法次数 共有j-i+1个矩阵，可称这个矩阵连乘的规 模是j-i+1 按照做最后一次乘法的位置进行划分，矩 阵连乘一共可分为j-i种情况 若已知任一个规模不超过j-i的矩阵连乘所 需的最少乘法次数，则可计算出 M M ┅M M 所需的最少乘法次数 i i+1 j -1 j 7 矩阵连乘问题 j -i种划分情况表示为通式： (M ┅M ) (M ┅M ) （i≤kj ） i k k+ 1 j 记第t个矩阵M 的列数为r ，并令r 为矩阵 t t 0 M 的行数 1 M ┅M 连乘所得是r r 维矩阵 i k i-1 k M ┅M 连乘所得是r r 维矩阵 k+ 1