第3章动态规划ppt课件.ppt

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

1、第3章动态规划算法总体思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如

2、果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrememberthepastaredoomedtorepeatit.-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCo

3、mmonSense(1905)分治法---Fibonacci数列分治法求解Fibonacci数列。publicstaticfibonacci_recur(intn){if(n==1

4、

5、n==2)return1;returnfibonacci_recur(n-2)+fibonacci_recur(n-1);}分治法求解Fibonacci数列的问题：划分以后，我们独立地求解每一个子问题，递归过程中存在大量的重复计算。解决方法：动态规划，保存已经解决的子问题的答案，在需要时直接使用，避免了大量重复计算。Fibonacci数列

6、的动态规划算法(迭代法）publicstaticintfibonacci(intn){f[1]=1;f[2]=1;for(inti=3;i<=n;i++)f[i]=f[i-1]+f[i-2];returnf[n];}递归中的重复问题—备查技术动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算

7、次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积完全加括号的矩阵连乘积（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵A,B,C,D，它们的维数分别是：总共有五中完全加括号的方式矩阵连乘问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与

8、Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j考察计算A[i:j]的最优计算

9、次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k

10、数乘次数m[i,j]，则原问题的最优值为m[1,n]当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n当i