[工学]计算机理论与算法分析3动态规划.ppt

元组法的过程 ①初始化i←0 ，S(1）←（0,0） ②计算 S(i+1)’ ③合并S(i+1)’与S(i) Q合并，并按支配规则舍弃被支配的元组即可得到S(i+1)。 ④i←i+1 ⑤如果in 重复② 元组法时间复杂性分析 S(i)中的数对个数至多为S(i)’中数对个数的2倍。初始P(1)=2, 1≤i≤n，所以： 计算所有S(i) 时所需要的总时间O(2n)。 算法时间在最坏情形下为2n量级 3.6 最长公共子序列 一个給定序列的子序列是在该序列中删除若干元素后得到的序列。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列。 给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 X={A,B,C,C,D,A,B} X={A,B,C,C,D,A,B} Y={C,A,D,B,A,B,C,B,D,C,D,B} Y={C,A,D,B,A,B,C,B,D,C,D,B} Z={A,B,C, D, B} Z={C,C, D, B} 1、最长公共子序列的结构 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则 (1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 xm x1 ……. yn y1 ……. Zk Z1 (2)若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列。 xm x1 ……. yn y1 ……. Zk Z1 Xm-1 Xm与公共子序列Z无关 (3)若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。 xm x1 ……. yn y1 ……. Zk Z1 Yn-1 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 子问题的递归结构 xi x1 ……. yj y1 ……. xi-1 yj-1 Xi={x1,x2,…,xi} Yj={y1,y2,…,yj} 如果xi≠yj 则C[i][j]=max{C[i-1][j], xi x1 ……. yj y1 ……. xi-1 yj-1 C[i][j-1]} xi x1 ……. yj y1 ……. yj-1 用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。 当i=0或j=0时， C[i][j]=0 当i,j0， 如果xi=yj 则C[i][j]= C[i-1][j-1]+1 xi-1 子问题的递归结构 用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。 当i=0或j=0时， C[i][j]=0 其它情况下， 由最优子结构性质可建立递归关系如下： xi x1 ……. yj y1 ……. xi-1 yj-1 Xi={x1,x2,…,xi} Yj={y1,y2,…,yj} 计算最优值 LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 1; i = m; i++) c[i][0] = 0; //初始化 for (i = 1; i = n; i++) c[0][i] = 0; for (i = 1; i = m; i++) for (j = 1; j = n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; // b[i][j]记录小[i]和y[j]的状态 } else if (c[i-1][j]=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } 计算最优值 例 X=(B,C,B,D) m=4 Y=(B,D,C,B,D) n=5 B C B D i = 1 j = 1 B D