欢迎来到天天文库
浏览记录
ID:44955262
大小:650.50 KB
页数:54页
时间:2019-11-06
《第3章动态规划》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第3章动态规划1动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2算法总体思想动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=3但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/
2、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)4如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。算法总体思想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)Thosewhocannotrememberth
3、epastaredoomedtorepeatit.(不记得过去的人注定要重复历史。)-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)5动态规划基本步骤找出最优解的性质,并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息,构造最优解。6完全加括号的矩阵连乘积(1)单个矩阵是完全加括号的;(2)矩阵连乘积是完全加括号的,则可表示为2个完全加括
4、号的矩阵连乘积和的乘积并加括号,即16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为:设有四个矩阵,它们的维数分别是:总共有五中完全加括号的方式7矩阵连乘问题给定n个矩阵,其中与是可乘的,。考察这n个矩阵的连乘积由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积8矩阵连乘问
5、题给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。算法复杂度分析:对于n个矩阵的连乘积,设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:9矩阵连乘问题穷举法动态
6、规划将矩阵连乘积简记为A[i:j],这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开,i≤k7、问题可用动态规划算法求解的显著特征。11建立递归关系设计算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当i8、只有由此可见,在递归计算时,许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法13用动态规划法求最优解voidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;for(inti=1;i<=n;i++)m[i][i]=
7、问题可用动态规划算法求解的显著特征。11建立递归关系设计算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当i8、只有由此可见,在递归计算时,许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法13用动态规划法求最优解voidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;for(inti=1;i<=n;i++)m[i][i]=
8、只有由此可见,在递归计算时,许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法13用动态规划法求最优解voidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;for(inti=1;i<=n;i++)m[i][i]=
此文档下载收益归作者所有