《动态规划》ppt课件

《《动态规划》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章动态规划理解动态规划算法的概念。掌握动态规划算法的基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。学习要点:2(1)矩阵连乘问题；(2)最长公共子序列；(3)最大子段和;(4)凸多边形最优三角剖分；(5)多边形游戏；(6)图像压缩；(7)电路布线；(8)流水作业调度；(9)背包问题；(10)最优二叉搜索树。通过应用范例学习动态规划算法设计策略3动态规划基本步骤找出最优解的性质，并刻划其

2、结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。1~3是动态规划算法最基本的步骤,若需要最优解,则必须执行步骤44完全加括号的矩阵连乘积完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)设有四个矩阵A,B,C,D，总共有五种完全加括号的方式:(A((BC)D))(A(B(CD)))((AB)(CD))(((AB)C)D)((A(BC)D))5完全加括号的矩阵连乘积设有四个矩阵A,B,C,D，它们的维数分

3、别是：A=50×10,B=10×40,C=40×30,D=30×5矩阵A和B可乘的条件是:矩阵A的列数等于矩阵B的行数.设A是p×q的矩阵,B是q×r的矩阵,则乘积是p×r的矩阵;计算量是pqr.上述5种完全加括号方式的计算工作量为:(A((BC)D)),(A(B(CD))),((AB)(CD)),(((AB)C)D),((A(BC)D))16000,10500,36000,87500,34500BC:10×40×30=12000,(BC)D:10×30×5=1500,(A((BC)D)):50×10×5=25006示例7示例8矩阵连乘问题定义：给定n个矩阵{A1

4、,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…n-1。考察这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积9算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：矩阵连乘问题给定n个矩阵｛A1,A2

5、,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少？穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。10矩阵连乘问题穷举法动态规划将矩阵连乘积AiAi+1…Aj简记为A[i:j],这里i≤j;考察计算A[i:n]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤k

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

7、有种可能建立递归关系13m[i][j]给出了最优值，最优断开位置为k：若将对应于m[i,j]的断开位置k记为s[i,j],在计算出最优值m[i,j]后,可递归的由s[i,j]构造出相应的最优解.建立递归关系14计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查一下，从而避免大量的重复计

8、算，最终得