第3章动态规划1详解.ppt

第3章 动态规划 学习要点: 理解动态规划算法的概念 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值 (3)以自底向上的方式计算出最优值 (4)根据计算最优值时得到的信息，构造最优解。 生活中的实例 ( 1) 汽车加油问题: 设有路程长度为L 公里的公路上，分布着m 个加油站，它们的位置分别为p( i = 1，2，……，m) ，而汽车油箱加满油后( 油箱最多可以加油k 升) ，可以行驶n 公里。设计一个方案，使汽车经过此公路的加油次数尽量少( 汽车出发时是加满油的) 。 ( 2) 田忌与齐王赛马各有n 匹马参赛( n≤100) ，每场比赛赌注为1 两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金( 输用负数表示) 。 通过应用范例学习动态规划算法设计策略 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉有哪些信誉好的足球投注网站树。 时间复杂度是O(p(n))的算法称为多项式时间算法，p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。 例如：时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 动态规划基本步骤 找出最优解的性质，并刻画其结构特征。 递归地定义最优值。 以自底向上的方式计算最优值。 根据计算最优值时得到的信息，构造最优解。 1－3基本步骤。 动态规划算法常用于求解具有某种最优性质的问题. 可能有许多可行解, 希望找到具有最优值的那个解. 用算法RecurMatrixChain(1,4,m,s)计算a[1:4]的计算递归树如下图所示： 用数学归纳法可以证明 ，因此，算法RecurMatrixChain的计算时间也随n指数增长。 步骤四: 构造最优解 动态规划算法的第4步: 构造问题的一个最优解 算法MatrixChain仅给出矩阵连乘积所需的最少数乘次数, 但未给出具体按什么次序做矩阵乘法. 但注意到: MatrixChain已记录了构造一个最优解所需的全部信息: 由s[i,j]中的数k知, 计算矩阵链A[i,j]的最佳方式应在Ak和Ak+1之间断开. A[1:n]=(A[1:s[1,n]])(A[s[1,n]+1:n]) A[1:s[1,n]]=(A[1:s[1,s [1,n]]])(A[s[1,s[1,n]]+1,s[1,n]]) 造此递推, 最终可以确定A[1:n]的最优完全加括号方式, 即构造出问题的一个最优解. 动态规划算法的基本要素 最优子结构：问题的最优解是由其子问题的最优解所构成的。 重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。 备忘录项 动态规划算法的基本方法 动态规划算法通常可以按以下几个步骤进行： (1)找出最优解的性质，并刻画其结构特征； (2)递归地定义最优值； (3)以自底向上的方式计算出各子结构的最优值并添入表格中保存； (4)根据计算最优值时得到的信息，构造最优解。 步骤1~3是动态规划算法的基本步骤。 若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。 首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中有哪些信誉好的足球投注网站。 当b[i,j]中遇到“↖“时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列； 当b[i,j]中遇到“↑“时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同； 当b[i,j]中遇到“←“时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。 3.4 最大子段和 （自学） 分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。 在一般情况下，机器M2上会有机器空闲和作业积压两种情况。 设全部作业的集合为N={1，2，…，n}。S?N是N的作业子集。 通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。 将这种情况下完成S中作业所需的最短时间记为T(S, t)。 流水作业调度问题的最优值为T(N, 0)。 0-1背包问题的形式描述 问题的形式描述是：给定c＞0，wi＞0，vi＞0，1≤i≤n，求n元0-1向量(x1, x2, …, x