第4章动态规划

《第4章动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章动态规划第四章动态规划目录概述矩阵连乘问题凸多边形最优三角剖分最长公共子序列问题加工顺序问题0-1背包问题最优二叉查找树教学目标理解动态规划的思想掌握动态规划、分治法及贪心法的异同掌握动态规划的基本要素掌握动态规划的设计步骤通过实例学习，掌握动态规划设计的策略学习动态规划的意义动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用，例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的

2、优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解，因此研究该算法具有很强的实际意义。动态规划算法通常用于求解具有某种最优性质的问题，动态规划的基本思想基本思想将待求解问题分解成若干个子问题，经分解得到的子问题往往不是互相独立的。先求解子问题，然后从这些子问题的解构造得到原问题的解。动态规划的解题步骤（1）分析最优解的性质，刻画最优解的结构特征——考察是否适合采用动态规划法。（2）递归地定义最优值（即建立递归式或动态规划

3、方程）。（3）以自底向上的方式计算出最优值，并记录相关信息。（4）根据计算最优值时得到的信息，构造出最优解。动态规划的基本要素最优子结构性质子问题重叠性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠性质。在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决，并把已解决的各个子问题的解储存在表中，便于以后遇到时直接引用，从而不必重新求解，可大大提高解题的效率。自底向上的求解方式矩阵连乘问题描述给定n个矩阵{A1,A2,A3,…,An}，其中Ai与A

4、i+1(i=1,2,3,…,n-1)是可乘的。用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。完全加括号的矩阵连乘积（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵，它们的维数分别是：总共有五中完全加括号的方式矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵

5、的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积矩阵连乘问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵

6、的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k

7、计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。建立递归关系设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]当i=j时，A[i:j]=A[i:i]，因此，m[i,i]=0，i=1,2,…,n当i

8、于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法例:要计算矩阵连乘积A1A2