算法设计与分析教案 第章动态规划.pptVIP

《算法设计与分析》第04章 动态规划 基本思想 动态规划方法常用来求解最优化问题。 其思想是：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，再构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上，从最终子问题向原问题逐步求解。 设计步骤 分析最优值的性质，得到最优值的递归定义； 自底向上地计算子问题的最优值，逐步得到原问题的最优值，并记录计算过程； 由最优值的计算过程出构造原问题的最优解； 动态规划算法的基本要素 最优子结构性质 问题的最优解包含了子问题的最优解。 子问题重叠性质 在自顶向下递归求解时，有些子问题会重复出现，而被重复计算。 矩阵连乘问题 在矩阵连乘过程中，结合顺序的不同会影响总的计算量，因此选择最优的计算顺序将有助于提高计算的效率； 矩阵连乘问题 分析 为方便描述，将Ai×Ai+1……×Aj记作Ai,j； 设最优解的最后一步乘法是A1,k×Ak+1,n，则显然，A1,k和Ak+1,n应分别是该子式的最优解；总计算量是这两个子式的计算量加上子式结果相乘的计算量； 这种最优解包含了子问题最优解的性质即称为最优子结构性质； 容易看出，按分治法自顶向下计算时，子问题将会大量重复出现； 矩阵连乘问题 定义最优值递归规则 若设mij表示Ai,j的最优解的计算量，最后一步乘法是Ai,k*Ak+1,j，则：mii=0mij=min{mik+mk+1,j+pi-1*pk*pj | i≤kj} pi表示矩阵Ai的列数，Ai+1的行数； 并令sij ? k，用来记录计算过程 矩阵连乘问题 算法过程 为了避免重复的计算，从mi,i出发，依次计算mi,i+1、mi,i+2、...mi,n，同时记录si,j；过程如下： 设P[0…n]向量为各矩阵的维数，P[i]为Ai的列数，P[0]为A1的行数；初始化m[i][i] = 0；i = 1…nL循环从1到n-1，计算m[i][i+L]： i(行下标)循环从1到n-L： j(列下标) = i+L； m[i][j]=min{ m[i][k]+m[k+1][j]+P[i-1]P[k]P[j] | k=i..j-1 }  并纪录：s[i][j] = k; 矩阵连乘问题 构造最优解——矩阵连乘顺序 由计算过程中得到的s向量，可以递归地得到矩阵连乘的计算顺序； 递归算法如下：问题形式：计算Ai,j；递归规则： k = s[i][j]; X = Ai,k;  Y = Ak+1,j;  结果为：X×Y；终结条件：Ai,i = Ai 最长公共子序列 问题：给定两个序列X={x1,x2,…,xm}，Y={y1,y2,…,yn}，求X和Y的一个最长公共子序列； 最长公共子序列 分析：设待求的公共子序列为Z={z1,z2,…,zk}，则可推论：若xm=yn，则Z是Xm-1和Yn-1的最长公共子序列+xm；否则，则Z是X和Yn-1的最长公共子序列（当zk≠xm时）或是Xm-1和Y的最长公共子序列（当zk ≠yn时）； 最长公共子序列 递归解法 问题形式：求X1…i，Y1…j的最长公共子序列； 递归规则：若xi=yj，则 求X1…i-1，Y1…j-1的最长公共子序列Z1…k； Z1…k+{xi}即结果；否则 求X1…i-1，Y1…j的最长公共子序列Z1; 求X1…i，Y1…j-1的最长公共子序列Z2； 比较Z1和Z2，长度较长的序列即结果； 终结条件：若X或Y为空序列，则Z为空序列； 最长公共子序列 自底向上构造最优值 求解X1…m和Y1…n的最长公共子序列，记为(Xm,Yn)引入辅助向量c0…m,0…n和b1…m,1…n：c0…m,0…n记录子问题的最优值，ci,j表示(Xi,Yj)的长度，i或j为0表示X或Y为空序列；b1…m,1…n记录子问题的解，bi,j表示(Xi,Yj)是由哪一个子问题的解得到的，约定：若是由(Xi-1,Yj-1)的解得到的，bi,j记为1；若是由(Xi-1,Yj)的解得到的，bi,j记为2；若是由(Xi,Yj-1)的解得到的，bi,j记为3。 最长公共子序列 自底向上构造最优值 从空序列开始，逐步计算子问题：初始化c[i][0] = 0; c[0][i] = 0;对比X和Y的全部字符对，i=1..m, j=1..n： 若X[i]=Y[j]，则 由递归规则：c[i][j] = c[i-1][j-1]+1； 记录b[i][j] = 1; 否则 选子问题中的最小值作为当前问题的最优值，即： c[i][j] = max{ c[i-1][j]，c[i][j-1] } 并分别记录b[i][j]=2 或 b[i][j]