动态规划:求最长公共子列

tech2022-08-25  121

动态规划

多阶段决策:每个阶段都做出决策,全部过程为决策序列

动态规划分解子问题相互重叠。 比如计算斐波那契数使用递归,f(n-1)+f(n-2):

f(5){-f(4)-{f(3)+f(2)    

       -f(3)-{f(2)+f(1)...                       其中有多次决策分解的子问题是重复的

动态规划性质:

1.最优子结构性质:该问题可划分成诺干规模较小的子问题,且原问题最优解包含子问题的最优解

2.子问题重叠性质:对重复出现的子问题,在第一次遇到时求解并保存

优化问题:给定一组约束条件和一个代价函数,在解空间种搜索具有最小或最大代价的优化解

动态规划问题的解题步骤:

1.找出最优解性质,并描述其结构特征

2.递归地定义最优值

3.以自底向上方式求出最优值

4.根据计算出的最优值求出最优解

动态规划的使用条件:

1.当一个问题的优化解包含子问题的优化解,该问题具有优化子结构

2.缩小子问题集合,只需要哪些优化问题中包含的子问题

3.优化子结构:可自底向上完成求解过程

求最长公共子列

如:s1={1,5,2,8,9,3,6}    s2={5,6,8,9,3,7}

其中最长公共子序列是{5,8,9,3},最长公共子序列长度是4

解:

1.分析最优子结构性质:

设序列S={z1,z2,...,zk}为s1,s2的公共子序列,则设s1={x1,x2,...,xn},s2={y1,y2,...,ym}

case1: Xn = Ym,则Zk = Xn = Ym,所以S[k-1]是S1[n-1]和S2[m-1]的公共子序列

case2: Xn!= Ym,则Zk!=Xn,则S[k]是S1[n-1]和S2[m]的最长公共子序列

case3: Xn!= Ym,则Zk!=Ym,则S[k]是S1[n]和S2[m-1]的最长公共子序列

所以:两个序列的最长公共子序列包含了两个序列的前缀最长公共子序列,则最长公共子序列具有最优解性质

2.递推公式:

设c[i][j]为s1前i个字符和s2前j个字符的最长公共子序列长度

c[i][j] = 0,                                  i = 0 || j = 0;

c[i][j] = c[i-1][j-1]+1,                  s1[i] = s2[j];

c[i][j] = max{ c[i-1][j] , c[i][j-1] }, s1[i]!=s2[j].  

3.自底向上求解最优值 :

S1={1,5,2,8,9,3,6},S2={5,6,8,9,3,7}

4.算法实现

根据递推公式,首先将第一行和第一列全部设置为0,然后准备一个数组用于记录当前是那种情况

首先计算两个序列的最长公共子序列长度

void LCSLength(int n,int m, int *x, int *y, int **c, int **b){ int i ,j; for(i = 0; i<n; i++){ c[i][0] = 0; } for(j = 0; j<m; j++){ c[0][j] = 0; } for(i = 0; i<n ; i++){ for(j = 0; j<m; j++){ if(x[i] == y[j]){ c[i][j] = c[i-1]+c[i-1]+1; b[i][j] = 1; //在构造最优解中的情形1 } else{ if(c[i-1][j] > c[i][j-1]){ c[i][j] = c[i-1][j]; b[i][j] = 2;//在构造最优解中的情形2 }else{ c[i][j] = c[i][j-1]; b[i][j] = 3;//在构造最优解中的情形3 } } } } }

构造最优解:

void LCS(int i, int j){ if(i == 0 || j == 0){ return; } if(b[i][j] == 1){ LCS(i-1,j-1); printf("%d",s[i]); }else if(b[i][j] == 2){ LCS(i-1,j); }else if(b[i][j] == 3){ LCS(i,j-1); } }

 

最新回复(0)