算法设计技巧与分析 第7章 动态规划.ppt

《算法设计技巧与分析 第7章 动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计技巧与分析AlgorithmsDesignTechniquesandAnalysis南方医科大学医工学院信息技术系第7章动态规划理解动态规划的基本原理掌握动态规划的算法实例（难点）掌握用动态规划设计算法的方法（重点）TeachingRequestContent动态规划原理算法实例最长公共子序列问题矩阵链相乘最短路径问题0-1背包问题动态规划范式1n=0f(n)=1n=1f(n-1)+f(n-2)n>1F(4)F(3)F(2)F(2)F(1)F(1)F(0)FibonacciSerialProblemRecursionForm算法过程：1.proceduref(n)

2、2.if(n=1)or(n=2)thenreturn13.elsereturnf(n-1)+f(n-2)时间复杂性：1若n=1或n=2若n≥3DynamicProgrammingForm计算过程：从f1开始，自底向上计算到fn。时间复杂性：Θ(n)空间复杂性：Θ(1)DynamicProgrammingPrinciple将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。DifferencebetweenDCandDP都是分解成子问题，由子问题的解得到原问题的解。分治中子问题相互独立，而动态规划中子问题互相

3、有联系，且存在重复计算，即存在重叠子问题。7.2LongestCommonSerialProblem:给出两个长度为n和m的字符串A和B，A=a1a2…an，B=b1b2…bm，确定在A和B中最长公共子序列的长度。Example:若A=zxyxyz，B=xyyzx，则A和B的最长公共子序列为xyyz，其长度为4。令L[i,j]表示a1a2…ai和b1b2…bj的最长公共子序列的长度，如果i和j都大于0，那么若ai=bj，L[i,j]=L[i-1,j-1]+1若ai≠bj，L[i,j]=max{L[i,j-1]，L[i-1,j]}观察结论7.1若i=0或j=0若i>0,j>

4、0和ai=bj若i>0,j>0和ai≠bj算法7.1　LCS输入:字母表上的两个字符串A和B，长度分别为n和m。输出:A和B最长公共了序列的长度。1.fori←0ton2.L[i，0]←03.endfor4.forj←0tom5.L[0，j]←06.endfor7.fori←1ton8.forj←1tom9.ifthenL[i，j]←L[i-1，j-1]+110.elseL[i，j]←max{[i，j-1]，L[i-1，j]}11.endif12.endfor13.endfor14.returnL[n，m]定理7.1最长公共子序列问题的最优解能够在时间和空间内得到。7.3

5、MatrixChain给定n个矩阵{A1,A2,…,An}，其中Ai是一个ri-1×ri矩阵(1≤i≤n)，即Ai×Ai+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。BasePrinciple考查两个矩阵相乘的情形：C=AB。如果矩阵A,B分别是p×r和r×q矩阵，则它们的乘积C将是p×q矩阵，其(i,j)元素为则共需要prq次数乘。BaseAlgorithmvoidMatrixMultiply(int**a,int**b,int**c,intra,intca,intrb,intcb){if(ca!=rb)error(“矩阵不可乘”)；for(inti=0

6、;i

7、Bracket矩阵相乘满足结合律，连乘积可以有许多不同的次序，可以用加括号的方式确定。设三个矩阵A1,A2,A3大小分别为2×10，10×2，2×10，考虑(A1(A2A3)),(A1A2)A3)的结果与相乘的次数。对于n个矩阵的连乘积，设有f(n)个计算次序。我们可以在第k个和第k＋1个矩阵之间将原矩阵划分为两个子矩阵序列，则：Catalan其中f(n)=C(n-1)，AnalyzethestructureoftheOptimizationResult设M[i:j]为矩阵连乘积MiMi+1···Mj。计算M[1:n]的最优次