201020112《算法分析》ppt7动态规划

1、最长公共子序列，LCS最长公共子序列，两个一维事物的比较：相似性：LCS算法完全相等，一一对应，概率算法相等，部分相等，模式匹配霍斯普算法，最长公共子序列：应用：打字比赛(规则，中外差异)，非典病毒文件比较等。两个一维事物的比较定义：带子串的差分算法：穷举法，动态编程代码实现：C，如果给定序列X=x1，x2，xm，那么另一个序列Z=z1，z2，zk，它是一个序列X的子序列，意味着有一个严格递增的下标序列i1，i2，ik，从而对于所有的J=例如，序列Z=B，C，d，B是序列X=A，B，C，B，d，A，B的子序列，并且相应的递增下标序列是2，3，5，B子字符串要求左右元素在母字符串中相邻。给定两个

2、序列x和y，当另一个序列z都是x的子序列和y的子序列时，z被称为x和y的公共子序列，最长公共子序列的定义：最长公共子序列的定义：给定两个序列x=x1，x2，XM和y=y1，y2，yn，找出x和y的最长公共子序列，穷举方法：如果需要两个序列x，y的最长公共子序列，则获得x，y的所有子序列并逐一比较。有如下不同的组合：需要不同的比较：最长公共子序列的结构，我们用Xm来表示x1，x2，XM XM-1来表示x1，x2，XM-1x1来表示x1也可以定义yn，yn-1。如果序列x=x1，x2，XM和y=y1，y2，yn的最长公共子序列是z=Z1，z2，ZK，那么(1)如果xm=yn，zk=xm=yn，并且

3、zk-1是xm-1和yn-1的最长公共子序列。(2)如果xmyn和zk=xm，则z是xm-1和y的最长公共子序列。最长公共子序列的结构，可以看出两个序列的最长公共子序列包含这两个序列的前缀最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。最长公共子序列的结构，子问题的递归结构，以及基于最长公共子序列问题的最优子结构性质的子问题最优值的递归关系。使用Cij记录序列和的最长公共子序列的长度。其中Xi=x1，x2，Xi；Yj=y1，y2，Yj .当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。因此，此时Cij=0。在其他情况下，递归关系可以通过如下的最优子结构性质来建立：子问题的递

4、归结构，计算最长公共子序列的长度，虚长长度(char x，char y，int m，int n) int Cmn，I，j；对于(I=0；I=Cij-1)Cij=Ci-1j；else Cij=Cij-1。返回Cmn。由于在所考虑的子问题空间中存在(mn)个不同的子问题，因此可以提高动态规划算法自下而上计算最优值的效率。示例：填写表格并找出表格中最长的公共子序列：(1)从(m，n)到(0，0) (2)如果当前网格与左边的相同，则绘制 ；如果当前网格与前一个网格相同，则绘制 ；以上两者不一致。将 从当前网格绘制到左上角网格。(3)从当前网格向箭头方向前进一个网格，并为此网格创建(2) (4)条从(m

5、，n)到(0，0)的不同路径。与 对应的网格元素构成了最长的公共子序列。找出最长的公共子序列、(bcbd，bcdb，badb)，问最长的公共子序列，空LCS (char a，int l，int m，int n) int I，j，k；char ZmI=m；j=n。k=m；do if(Cij=Ci-1j)I-；否则，如果(Cij=Cij-1) j -。否则Zk=aik-；我。j-；而(i0)，时间复杂度为：m n=O n，最长公共子序列得到改进。如果只需要计算最长公共子序列的长度，算法的空间要求可以大大降低。事实上，只有数组C的第一行和第一行用于计算Cij。因此，最长公共子序列的长度可以用两行数组

6、空间来计算。进一步的分析还可以将空间需求减少到0(最小(m，n)。思考问题：如何将程序纠正为思考问题。子串比较等搜索工具的目的是从信息海洋中搜索字符串匹配。最著名的子串匹配算法是KMP算法。KMP算法利用关键字的相似特性来节省时间复杂度：O(m n)数据结构中的相关内容，矩阵连续乘积问题，矩阵连续乘积问题，可以定义为：给定n个矩阵，其中和是乘法的。研究这N个矩阵的连续乘积因为矩阵乘法满足关联法则，所以计算矩阵的连续乘积有许多不同的计算顺序。这个计算顺序可以通过括号来确定。矩阵连续乘积问题，如果一个矩阵连续乘积的计算顺序被完全确定，也就是说，这个连续乘积已经被完全括起来，那么矩阵乘法的标准算法就

7、可以在这个顺序中被反复调用来计算矩阵连续乘积。有四个矩阵A，B，C，D，它们的维数是：A=50*10，B=10*40，C=40*30，D=30*5。总共有五种完全括号内的方法(a (BC) d) (a (b (CD) 34500，检查矩阵乘法：检查矩阵乘法：单次乘法：n次加法：n-1次总乘法：m*n*l次总加法：m*(n-1)*l，矩阵连续积问题，给定n个矩阵a1，a2，an，其中Ai和a1是乘法的。如何确定矩阵连续乘积的计算顺序，使按此顺序计算矩阵连续乘积所需的次数最少。矩阵连续积问题，穷举法：列出所有可能的计算顺序，计算每个计算顺序所需的次数，找出次数最少的计算顺序。算法复杂度分析：对于n个矩阵的连续乘积，不同的计算顺序为P(n)。因为每个括号方法可以分解成两个子矩阵的括