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

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

1、算法设计与分析第3章动态规划03.1矩阵连乘问题3.2动态规划算法的基本要素3.3最长公共子序列3.4最大子段和3.5凸多边形最优三角剖分3.6多边形游戏3.7图像压缩3.8电路布线3.9流水作业调度3.100-1背包问题3.11最优二叉搜索树1算法总体思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已

2、求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。2动态规划基本步骤①找出最优解的性质，并刻划其结构特征。②递归地定义最优值。③以自底向上的方式计算出最优值。④根据计算最优值时得到的信息，构造最优解。33.1矩阵连乘问题给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。考察这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。4完全加括号的矩阵连乘积若一个矩阵连乘积的计

3、算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：①单个矩阵是完全加括号的；②矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。5例：设有四个矩阵A,B,C,D，可以有以下5种不同的加括号方式：每一种完全加括号方式对应于一种矩阵连乘积的计算次序，而矩阵连乘积的计算次序与其计算量有密切关系。6两个矩阵的乘积矩阵A(p×q)和矩阵B(q×r)的乘积C=AB是一

4、个p×r的矩阵。7voidMatrixMultiply(int**a,int**b,int**c,intra,intca,intrb,intcb){if(ca!=rb)cerr("矩阵不可乘！");for(inti=0;i

5、设有三个矩阵A1(10×100)、A2(100×5)、A3(5×50)相乘，则有两种加括号方式：①((A1A2)A3)10×100×5+10×5×50=7500②(A1(A2A3))100×5×50+10×100×50=750009矩阵连乘问题给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。10穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘

6、次数最少的计算次序。对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：Catalan（卡塔兰）数：1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,...11动态规划法将矩阵连乘积AiAi+1…Aj简记为A[i:j]，这里i≤j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k

7、则其相应完全加括号方式为：(AiAi+1…Ak)(Ak+1Ak+2…Aj)计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。121.分析最优解的结构特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。132.建立递归关系设计算A[i:j]，1≤i≤j≤n，所需要

8、的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。设Ai的维数为pi-1×pi，则当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n当i