第6章动态规划法.pptVIP

证明近似串匹配问题满足最优性原理。 如果样本p1p2…pm在文本T的某一位置上有最优（差别数最小）的对应关系，则样本P的任意一个子串pi…pj（1≤i＜j≤m）与文本T的对应关系也必然是最优的。 动态规划函数： 定义一个代价函数D(i, j)(0≤i≤m,0≤j≤n)表示样本前缀子串p1…pi与文本前缀子串t1…tj之间的最小差别数，则D(m, n)表示样本P与文本T 的最小差别数。 根据近似匹配的定义，容易确定代价函数的初始值： （1）D(0, j)=0，因为空样本与文本t1…tj有0处差别； （2）D(i, 0)=i，因为样本p1…pi与空文本t1…tj有i 处差别。 当样本p1…pi与文本t1…tj对应时，D(i, j)有四种可能的情况： （1）字符pi与tj相对应且pi=tj，则总差别数为D(i-1, j-1)； （2）字符pi与tj相对应且pi≠tj，则总差别数为D(i-1, j-1)＋1； （3）字符pi为多余，即字符pi对应于tj后的空格，则总差别数为D(i-1, j)＋1； （4）字符tj为多余，即字符tj对应于pi后的空格，则总差别数为D(i, j-1)＋1。 ? ? ? H a v e ? a ? h s p p y ? d a y ? ? 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 h 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a 2 2 2 1 2 2 2 1 2 1 1 2 2 2 2 2 2 2 p 3 3 3 2 2 3 3 2 2 2 2 1 2 3 3 3 2 3 p 4 4 4 3 3 3 4 3 3 3 3 2 1 2 3 4 3 3 y 5 5 5 4 4 4 4 4 4 4 4 3 2 1 2 3 3 4 例：已知样本P=happy，K=1，T=Have a hsppy day是一个可能有编辑错误的文本，在T中求1-近似匹配的过程如下： 由于D(5, 12)=1且m=5，所以，在t12处找到了差别数为1的近似匹配，此时的对应关系如下： T: H a v e a h s p p y d a y P: h a p p y 修改编辑错误 算法6.6——近似串匹配问题 int ASM(char P[ ], char T[ ], int m, int n, int K) { for (j=1; j=n; j++) //初始化第0行 D[0][j]=0; for (i=0; i=m; i++) //初始化第0列 D[i][0]=i; for (j=1; j=n; j++) //根据递推式依次计算每一列 { for (i=1; i=m; i++) { if (P[i]= =T[j]) D[i][j]=min(D[i-1][j-1], D[i-1][j]+1, D[i][j-1]+1); else D[i][j]=min(D[i-1][j-1]+1, D[i-1][j]+1, D[i][j-1]+1); } if (D[m][j])=K) return j; } } 算法6.6的时间复杂性为O(m×n)。 6.5 实验项目——最大子段和问题 1. 实验题目 给定由n个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 2. 实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 3. 实验要求 （1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （2）比较