最新算法设计与分析 动态规划讲义教学讲义PPT.ppt

《最新算法设计与分析 动态规划讲义教学讲义PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析动态规划讲义引言动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。2由简单到复杂……用分治法求n中选k的方案数.有以下的递推关系：1,ifk=0ork=nC(n,k)=C(n-1,k-1)+C(n-1,k),if0nAlgorithmST-C(n,k){

2、ifk=0ork=nthenreturn1;elsereturnST-C(n-1,k-1)+ST-C(n-1,k);}Time=O(2^n)3动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。7例一：矩阵连乘问题给定n个矩阵{M1,M2,...,Mn}，其中Mi与Mi+1是可乘的，i=1,2,...,n-1。考察这n个矩阵的连乘积M1M2...Mn。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

3、若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。设有四个矩阵A,B,C,D，它们的维数分别是：A=13×5，B=5×89，C=89×3，D=3×34，求A*B*C*D=？总共有五种完全加括号的方式：(A((BC)D))、(A(B(CD)))、((AB)(CD))、(((AB)C)D)、((A(BC))D)因为Xp*r*Yr*q所须做的乘法次数为：p*r*q，故以上五种乘法的数乘次数分别为：2856,26418,54201,10582,40558思路一：穷举搜索法问

4、题描述：给定n个矩阵{M1,M2,...,Mn}，其中Mi与Mi+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(M1...Mk)(Mk+1…Mn)可以得到关于P(n)的递推式如下：也就是说，P(n)是随n的增长成指数增长的。9动态规划法——1.

5、分析最优解的结构下面我们考虑用动态规划求解。预处理：将矩阵连乘积M1,M2,...,Mn简记为M[i:j]，这里i≤j。考察计算M[i:j]的最优计算次序。设这个计算次序在矩阵Mk和Mk+1之间将矩阵链断开，i≤k

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

7、,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。12算法描述算法描述：voidMatrixChain(*p，n，*m，*s)//p={p0,p1,…,pn}存储各矩阵的行列数。n：连乘的矩阵个数M1,M2,...,Mn。//输出最优值数组

8、m、最优断开位置的数组s。{for(i=1;i<=n;i++)m[i][i]=0;//一个矩阵时，不必划分了。for(r=2;r<=n;r++)//r表示矩阵的链长