动态规划_最长公共子序列-Aet

Bingliaolong 2020-09-05 10:36 Aet | 隐藏边栏 | 抢沙发 | 0 0

文章评分 0 次，平均分 0.0 ：

简述

最长公共子序列算法思想，令 X=< x1,x2,...xm > Y=<y1,y2,...yn> 为两个序列， Z=<z1,z2,...zk>为X和Y的某一个最长公共子序列：

如果 xm=yn，则zk=xm=yn,且Z(k-1)是X(m-1)和Y(n-1)的一个最长公共子序列

如果 xm != yn, 则如果 zk!=xm,意味着 Z是 X(m-1) 和 Y的一个最长公共子序列

如果 xm != yn, 则如果 zk!=yn,意味着 Z是 Xm 和 Y(n-1)的一个最长公共子序列

总结：
如果目标序列A和目标序列B一样长的情况下，它们的最长公共子序列就是序列A(n-1)与序列B(n-1)这两个最长子序列的公共最长子序列。
如果目标序列A和目标序列B不一样长的情况下：
如果是序列A长一些，可能的情况是A(n-1)和B一样长或者A(n-1)都比B长，这样的情况下，A和B的最长公共子序列就是序列A(n-1)和序列B这两个序列的公共最长子序列。如果是序列B长一些，情况也是一样。

定义

定义c[i,j]为Xi和Yj的最长公共子序列长度，则 c[i,j]= 0（若 i=0或j=0) ;c[i-1,j-1]+1 (若i,j>0,且xi=yj)；max(c[i,j-1],c[i-1,j])(若x,j>0 且 xi!=yj),通过动态规划方法从底向上计算

复杂度

时间复杂度：O(m*n)，空间复杂度O(m*n)

实现

begin : 第一个序列的起始迭代器
end: 第一个序列的终止迭代器
flag_matrix: 标记矩阵
seq1_index: 第一个子序列为X[0..seq1_index1]（从0计数）
seq2_index: 第二个子序列为Y[0..seq1_index2]（从0计数）
out_begin: 存放最长公共子序列结果的起始迭代器(注意必须是引用类型)(要求输出容器足够大可以存放结果)

在计算最长公共子序列过程中，顺便计算了标记矩阵。定义c[i,j]为Xi和Yj的最长公共子序列长度，则

c[i,j]= 0（若 i=0或j=0)

c[i,j]=c[i-1,j-1]+1 (若i,j>0,且xi=yj)

c[i,j]=max(c[i,j-1],c[i-1,j])(若x,j>0 且 xi!=yj)

其中：flag_matrix表征的是如何从c[i-1,j-1]、c[i,j-1]、c[i-1,j]这三者之一到达c[i,j]。即flag_matrix（i,j)对应的是矩阵:

c[i][j] c[i+1][j]

c[i+1][j] c[i+1][j+1]

如果 xi=yj，则标记flag_matrix[i-1][j-1]为 11，表示<x1...xi>与<y1...yj>的最长公共子序列也是<x1...x(i-1)>与<y1...y(j-1)>的最长公共子序。此时递归至X(i-1)和Y(j-1)

如果 xi！=yj，且c[i-1,j]> c[i,j-1]则标记flag_matrix[i-1][j-1] 为10，表示<x1...xi>与<y1...yj>的最长公共子序列也是<x1...x(i-1)>与<y1...yj>的最长公共子序。此时递归至X(i-1)和Yj

如果 xi！=yj，且c[i,j-1]> c[i-1,j]则标记flag_matrix[i-1][j-1] 为01，表示<x1...xi>与<y1...yj>的最长公共子序列也是<x1...x>与<y1...y(j-1)>的最长公共子序。此时递归至Xi和Y(j-1)


c[i][j]	c[i+1][j]
c[i+1][j]	c[i+1][j+1]

template<typename Iterator,typename OutIterator>

std::size_t make_LCS(const Iterator begin

,const Iterator end,

const std::vector<std::vector<int>>& flag_matrix,

typename std::iterator_traits<Iterator>::difference_type seq1_index,

typename std::iterator_traits<Iterator>::difference_type seq2_index,

OutIterator& out_begin)

{

typedef typename std::iterator_traits<Iterator>::value_type T;

typedef typename std::iterator_traits<OutIterator>::value_type Out_T;

static_assert(std::is_same<T, Out_T>::value,"输入序列与输出序列必须包含相同类型的元素");

std::size_t result=0;

if(seq1_index<0||seq2_index<0)

return result;

if(flag_matrix[seq1_index][seq2_index]==11) //两个子序列尾部相同

{

result+=(make_LCS(begin,end,flag_matrix,seq1_index-1,seq2_index-1,out_begin)+1);

*out_begin=*(begin+seq1_index); //由于是从尾部向前打印，这里要递归调用之后输出

out_begin++; //这里修改了out_begin,从而在不同迭代次数下，其值会发生改变

return result;

}

else if(flag_matrix[seq1_index][seq2_index]==10)//表示c[i-1,j]较大，此时X[0...i]与Y[0...j]最长公共子序列也是X[0...i-1]与Y[0...j]最长公共子序列

{

result+=make_LCS(begin,end,flag_matrix,seq1_index-1,seq2_index,out_begin);

return result;

}

else//表示c[i,j-1]较大，此时X[0...i]与Y[0...j]最长公共子序列也是X[0...i]与Y[0...j-1]最长公共子序列

{

result+= make_LCS(begin,end,flag_matrix,seq1_index,seq2_index-1,out_begin);

return result;

}

template<typename Iterator1,typename Iterator2,typename OutIterator>

std::size_t longest_common_subsequence(const Iterator1 first_begin,

const Iterator1 first_end,

const Iterator2 second_begin,

const Iterator2 second_end,OutInerator out_begin)

{

typedef typename std::iterator_traits<Iterator1>::value_type T1;

typedef typename std::iterator_traits<Iterator2>::value_type T2;

typedef typename std::iterator_traits<Iterator>::value_type T3;

static_assert(std::is_same<T1,T2>::value,"两个序列必须包含相同类型的元素");

static_assert(std::is_same<T1,T3>::value,"输入序列与输出序列必须包含相同类型的元素");

auto len1 = std::distance(first_begin,first_end);

auto len2 = std::distance(second_begin,second_end);

if (len1 <= 0 || len2 <= 0)

return 0;

auto rows = len1;

auto columns = len2;

//创建数据矩阵

//c_matrix[i,j]为Xi和Yj的最长公共子序列长度，因为i,j可能为0，所以矩阵外扩一个单位

std::vector<std::vector<int>> c_matrix(rows+1);

for (int i = 0;i < rows+1;i++)

{

//这里大小为什么为 (m+1)*(n+1)：因为X序列的子序列可以为空、<x1>、...<x1...xm>一共（m+1）个；Y序列的子序列有 (n+1)个

c_matrix.at(i) = std::vector<int>(columns+1);

}

//用于构造最长公共子序列，它存放的是从c[i-1][j-1]到c[i,j]的路径

std::vector<std::vector<int>> falg_matrix(rows);

for (int i = 0;i < rows;i++)

{

//这这里大小为什么为m*n:因为它表征的是如何从c[i-1,j-1]、c[i,j-1]、c[i-1,j]这三者之一到达c[i,j]。即flag_matrix（i,j)对应的是矩阵：

flag_matrix.at(i) = std::vector<int>(columns);

}

//初始化矩阵

for (int i = 0;i < rows + 1;i++)// c[i,j]= 0（若 i=0或j=0)

c_matrix[i][0] = 0;

for (int i = 0;i < columns + 1;i++)// c[i,j]= 0（若 i=0或j=0)

c_matrix[0][i] = 0;

//开始计算

for (int r = 1;r < rows + 1;r++)

{

for (int c = 1;c < columns + 1;c++)

{

//c[i,j]=c[i-1,j-1]+1 (若i,j>0,且xi=yj)

if (*(first_begin+r-1) == *(second_begin+c-1))

{

c_matrix[r][c] = c_matrix[r-1][c-1] + 1;

//c[i,j]=c[i-1,j-1]+1，标记flag_matrix[i-1][j-1] 为11

flag_matrix[r-1][c-1] = 11;

}

else if (*c_matrix[r-1][c] >= c_matrix[r][c-1])//c[i,j]=max(c[i,j-1],c[i-1,j]) (若i,j>0,且xi=yj)

{

c_matrix[r][c] = c_matrix[r-1][c];

// 标记flag_matrix[i-1][j-1] 为10，表示c[i-1,j]较大

flag_matrix[r-1][c-1] = 10;

}

else//c[i,j]=max(c[i,j-1],c[i-1,j]) (若i,j>0,且xi=yj)

{

c_matrix[r][c] = c_matrix[r][c-1];

flag_matrix[r-1][c-1] = 1;

}

return make_LCS(first_begin,first_end,flag_matrix,len1-1,len2-1,out_begin);

}

简述
定义
复杂度
实现

本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0 最后编辑于：2021-11-20

Everything will be better.

一	二	三	四	五	六	日
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

简述

定义

复杂度

实现

你可能也喜欢

热评文章

发表评论

标签云集