最长公共子序列

最长公共子序列问题（动态规划）

给定两个序列X和Y：

image-20220502210804170

其公共序列为：

image-20220502210820695

这里我们要找出它的最长子序列，由上面的情况得出最长的公共自序列长度为4 为BCAB

如果我们采用枚举法的话，有如下这种情况：

image-20220502211056663

我们再次观察一下这个公共自序列：

image-20220502211214029

我们发现长一点的数组依靠于短一点的数组：这时候可能会出现最优子结构 和重叠子问题

当一个结构里面包含最优子结构问题和重叠子问题的时候我们就应该想到使用动态规划来解决这个问题

动态分析问题

我们采用C[i, j] 来表示[1…i]和Y[1…j]的最长公共子序列长度

我们从最后一个字母来开始推导，有两种情况，

情况一：

这两个序列的最后一个字母不相同

image-20220502211652786

如果最后两个字母不同的话，可分为两种情况

情况一

C[i, j] = C[i, j -1 ] + 0

情况二

C[i, j] = C[i-1, j] + 0

image-20220502211938610

情况二：

这两个序列的最后一个字母相同。

image-20220502211606410

这里面需要分为三种情况：

  1. 第一种：最后这个相同的字符在最长子序列中
  2. 第二种：最后这个相同的字符不一定出现在最长子序列中，我们删除第一个序列的最后一个，在和第二个序列相比较
  3. 第三种：最后这个相同的字符不一定出现在最长子序列中，我们删除第二个序列的最后一个，在和第一个序列相比较

image-20220502212425684

在这里我们看到：

c[i-1,j]比c[i -1,j -1]至多大1

c[i,j -1]比c[i -1, j -1]至多大1

c[i- 1,i -1]+1，另外两个+0

c[i- 1,i -1]+1 ≥ {c[i,j -1]，c[i-1,j] }

递推公式为：

image-20220502212741379

追踪数组递推公式为：

image-20220502212815454

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 初始化矩阵 
# 把矩阵的第零行第零列都设置为零
def init_matrix(mt_length, mt_width):
    matrix =  [[ [] for m in range(mt_length+1) ] for i in range(mt_width+1)]
    for i in range(mt_width+1):
        matrix[i][0] = 0
    for m in range(mt_length+1):
        matrix[0][m] = 0
    return matrix

# 进行最大子数组求导
def max_subsequence(A_strand, B_strand, matrix, rec):
    mx_width = len(A_strand)
    mx_height = len(B_serand)

    for line_num in range(mx_height):
        for column_num in range(mx_width):
            # 这里分为三种情况
            # 情况一：这两个字符相同
            
            if B_strand[line_num] ==  A_strand[column_num]:

                matrix[line_num+1][column_num+1] = matrix[line_num][column_num]+1
                rec[line_num][column_num] = "LU"
            # 情况二：这两个字符串不同，但是上大于左
            elif matrix[line_num + 1][column_num] > matrix[line_num][column_num+1]:
                 matrix[line_num+1][column_num+1] = matrix[line_num+1][column_num]
                 rec[line_num][column_num] = "L"
            # 左大于上 
            else:
                matrix[line_num+1][column_num+1] = matrix[line_num][column_num+1]
                rec[line_num][column_num] = "U"

# 追踪数组
def trace(rec, mx_length, mx_width, trace_list):
    if mx_length ==  0 or mx_width ==  0:
        return trace_list.append((mx_length, mx_width))
    if rec[mx_length][mx_width] ==  "LU":
        trace_list.append((mx_length,mx_width))
        trace(rec, mx_length-1, mx_width-1, trace_list)
    elif rec[mx_length][mx_width] ==  "L":
        trace(rec, mx_length, mx_width-1, trace_list)
    elif rec[mx_length][mx_width] ==  "U":
        trace(rec, mx_length-1, mx_width, trace_list)

测试数据

A_strand = “BDCABABCFGASDFGS”

B_serand = “ABCBDABCFGDFGAS”

最后结果：

B C B A B C F G D F G S