题目
2.[简答题]若序列X=(B,C,A,D,B,C,D),Y=(A,C,B,A,B,D,C,D),利用动态规划算法找出X和Y 的最长公共子序列。利用c[i][j]和b[i][j]记录问题最优值和构造问题最优解。
2.[简答题]若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},利用动态规划算法找出X和Y 的最长公共子序列。利用c[i][j]和b[i][j]记录问题最优值和构造问题最优解。
题目解答
答案
根据动态规划,构建 $ c[i][j] $ 表如下:
```
A C B A B D C D
0 0 0 0 0 0 0 0 0
B 0 0 0 1 1 1 1 1 1
C 0 0 1 1 1 1 1 2 2
A 0 1 1 1 2 2 2 2 2
D 0 1 1 1 2 2 3 3 3
B 0 1 1 2 2 3 3 3 3
C 0 1 2 2 2 3 3 4 4
D 0 1 2 2 2 3 4 4 5
```
回溯路径:
1. $ c[7][8] = 5 $,$ X[7] = Y[8] = D $。
2. $ c[6][7] = 4 $,$ X[6] = Y[7] = C $。
3. $ c[5][6] = 3 $,$ X[5] = Y[6] = D $。
4. $ c[4][5] = 2 $,$ X[4] = Y[5] = B $。
5. $ c[3][4] = 2 $,$ X[3] = Y[4] = A $。
6. $ c[2][3] = 1 $,$ X[2] = Y[3] = C $。
7. $ c[1][2] = 1 $,$ X[1] = Y[2] = B $。
最终,LCS为:$ B, C, A, B, D $。
答案:$ B, C, A, B, D $(或 $ B, C, A, D, C $ 等,长度均为5)。
解析
本题考查动态规划算法在求解最长公共子序列(LCS)问题中的应用。解题思路是通过构建一个二维数组 $c[i][j]$ 来记录序列 $X$ 的前 $i$ 个元素和序列 $Y$ 的前 $j$ 个元素的最长公共子序列的长度,同时构建另一个二维数组 $b[i][j]$ 来记录在构建 $c[i][j]$ 时的决策信息,以便后续回溯构造最长公共子序列。
1. 初始化
设序列 $X = \{x_1, x_2, \cdots, x_m\}$,序列 $Y = \{y_1, y_2, \cdots, y_n\}$,这里 $m = 7$,$n = 8$。
初始化 $c[i][0] = 0$($0 \leq i \leq m$)和 $c[0][j] = 0$($0 \leq j \leq n$),这表示当其中一个序列为空时,最长公共子序列的长度为 0。
2. 填充 $c[i][j]$ 表
根据以下递推公式填充 $c[i][j]$ 表:
$c[i][j] = \begin{cases}c[i - 1][j - 1] + 1, & \text{if } x_i = y_j \\\max(c[i - 1][j], c[i][j - 1]), & \text{if } x_i \neq y_j\end{cases}$
具体计算过程如下:
- 当 $i = 1$,$x_1 = B$:
- 对于 $j = 1$,$y_1 = A$,$x_1 \neq y_1$,$c[1][1] = \max(c[0][1], c[1][0]) = 0$。
- 对于 $j = 2$,$y_2 = C$,$x_1 \neq y_2$,$c[1][2] = \max(c[0][2], c[1][1]) = 0$。
- 以此类推,得到 $c[1][j]$($1 \leq j \leq 8$)的值。
- 当 $i = 2$,$x_2 = C$:
- 对于 $j = 1$,$y_1 = A$,$x_2 \neq y_1$,$c[2][1] = \max(c[1][1], c[2][0]) = 0$。
- 对于 $j = 2$,$y_2 = C$,$x_2 = y_2$,$c[2][2] = c[1][1] + 1 = 1$。
- 以此类推,得到 $c[2][j]$($1 \leq j \leq 8$)的值。
- 按照这样的方式,逐步计算出整个 $c[i][j]$ 表,如下所示:
A C B A B D C D 0 0 0 0 0 0 0 0 0 B 0 0 0 1 1 1 1 1 1 C 0 0 1 1 1 1 1 2 2 A 0 1 1 1 2 2 2 2 2 D 0 1 1 1 2 2 3 3 3 B 0 1 1 2 2 3 3 3 3 C 0 1 2 2 2 3 3 4 4 D 0 1 2 2 2 3 4 4 5
3. 回溯构造最长公共子序列
从 $c[m][n]$ 开始回溯,根据 $b[i][j]$ 记录的信息(这里虽然题目未给出 $b[i][j]$ 表,但可以根据 $c[i][j]$ 的值判断)来构造最长公共子序列。
- 当 $c[i][j] = c[i - 1][j - 1] + 1$ 且 $x_i = y_j$ 时,说明 $x_i$(或 $y_j$)是最长公共子序列的一个元素,将其加入结果序列,并回溯到 $c[i - 1][j - 1]$。
- 当 $c[i][j] = c[i - 1][j]$ 时,回溯到 $c[i - 1][j]$。
- 当 $c[i][j] = c[i][j - 1]$ 时,回溯到 $c[i][j - 1]$。
回溯路径如下:
- $c[7][8] = 5$,$X[7] = Y[8] = D$,将 $D$ 加入结果序列,回溯到 $c[6][7]$。
- $c[6][7] = 4$,$X[6] = Y[7] = C$,将 $C$ 加入结果序列,回溯到 $c[5][6]$。
- $c[5][6] = 3$,$X[5] = Y[6] = D$,将 $D$ 加入结果序列,回溯到 $c[4][5]$。
- $c[4][5] = 2$,$X[4] = Y[5] = B$,将 $B$ 加入结果序列,回溯到 $c[3][4]$。
- $c[3][4] = 2$,$X[3] = Y[4] = A$,将 $A$ 加入结果序列,回溯到 $c[2][3]$。
- $c[2][3] = 1$,$X[2] = Y[3] = C$,将 $C$ 加入结果序列,回溯到 $c[1][2]$。
- $c[1][2] = 1$,$X[1] = Y[2] = B$,将 $B$ 加入结果序列,回溯到 $c[0][1]$,结束回溯。
最终得到的最长公共子序列为 $B, C, A, B, D$。