#实验三 动态规划算法
一.实验目的
掌握动态规划算法的设计与分析步骤以及算法的具体实现。
二.实验要求
实验时间:2学时,对于给定的问题描述,生成实验报告。
三.实验内容
问题描述:给定序列X=<x1,x2, … ,xm>, Y=<y1,y2, … ,yn> 求 X 和 Y 的最长公共子序列及其长度。
- 使用蛮力算法解决问题,给出分析过程。
- 使用动态规划算法解决问题,给出分析过程。
- 给出算法的具体实现过程(源码及其详细注释)。
- 给出算法的运行结果。针对不同的输入,给出两种不同算法时间上的差异。
问题连接-学习通(暂时关闭)
蛮力算法
思路
找出一个串的所有子序列,然后依次与另一个串比较,如果该子序列的排列符合另一个串的排列,则是一个公共子序列。记录子序列的长度,找出最大长度即可。
不难看出,此算法的核心在于找出一个串的所有子序列。
怎么找呢。
我们能够联想到,对于一个物品,选择和不选择,我们都能用0、1来表示。
对于一个序列中的每一个位置,我们也能通过选择与不选择的两种状态。
X串长m。则X有2m个子序列。(因为每个位置可以有两种状态)
我们可以将m转化为二进制,每个位次分别将其与X
串的各个位置对应。
复杂度
共有2m个子序列,时间复杂度O(2m)。
每个子序列都需要与Y
比较,Y
长度为n,时间复杂度O(n).
总的时间复杂度O(n2m).
DP
解决DP问题,最重要的是要找出子问题。所以从这里开始。
子问题
我们假设当前Z=<Z1,Z2, … ,Zk>已经是LCS,可能有xm=yn和xm=yn:
如果xm = yn
- 则zk=xm=yn 且
Zk-1
是Xm-1
和Yn-1
的一个LCS
.
如果xm != yn
- 且有 zk=xm,则
Z
是Xm-1
和Y
的一个LCS
.
- 且有zk!=yn,则
Z
是X
和Yn-1
的一个LCS
.
状态转移方程
L[i][j]=⎩⎨⎧0max{L[i−1][j],L[i][j−1]}L[i−1][j−1]+1i=0 or j=0xi=yj,i>0,j>0xi=yj,i>0,j>0
因此,我们只需要从c[0][0]
开始填表,填到c[m][n]
,所得到的c[m-1][n-1]
就是LCS_length
.
回溯
若想得到LCS
,回溯一次b数组
,从最后一个位置开始往前遍历:
- 如果箭头是
↖
,则代表这个字符是LCS
的一员,存下来后 i-- , j--
- 如果箭头是
←
,则代表这个字符不是LCS
的一员,j--
- 如果箭头是
↑
,也代表这个字符不是LCS
的一员,i--
- 如此直到i=0或者j=0时停止,最后存下来的字符就是所有的
LCS
字符
序列 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
X |
A |
B |
C |
B |
D |
A |
B |
Y |
B |
D |
C |
A |
B |
A |
\0 |
Target |
B |
C |
B |
A |
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
B[1,1]= ↑ |
B[1,2]= ↑ |
B[1,3]= ↑ |
B[1,4]=↖ |
B[1,5]= ← |
B[1,6]=↖ |
2 |
B[2,1]=↖ |
B[2,2]= ← |
B[2,3]= ← |
B[2,4]= ↑ |
B[2,5]=↖ |
B[2,6]= ← |
3 |
B[3,1]= ↑ |
B[3,2]= ↑ |
B[3,3]=↖ |
B[3,4]= ← |
B[3,5]= ↑ |
B[3,6]= ↑ |
4 |
B[4,1]= ↖ |
B[4,2]= ↑ |
B[4,3]= ↑ |
B[4,4]= ↑ |
B[4,5]=↖ |
B[4,6]= ← |
5 |
B[5,1]= ↑ |
B[5,2]=↖ |
B[5,3]= ↑ |
B[5,4]= ↑ |
B[5,5]= ↑ |
B[5,6]= ↑ |
6 |
B[6,1]= ↑ |
B[6,2]= ↑ |
B[6,3]= ↑ |
B[6,4]=↖ |
B[6,5]= ↑ |
B[6,6]=↖ |
7 |
B[7,1]=↖ |
B[7,2]= ↑ |
B[7,3]= ↑ |
B[7,4]= ↑ |
B[7,5]= ↖ |
B[7,6]= ↑ |

复杂度
该算法无重复地填写了一张(如果需要具体的子序列内容,则是两张)二维表格,每个格子填写时都仅进行了常数次比较。时间复杂度 O(mn).
回溯时,在任何情况下,都需要从[m][n]
回溯到[1][1]
,即回溯时间复杂度为O(m+n).
所以DP算法的时间复杂度为
O(mn)
代码
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
| #include <iostream> #include <string> #include <cstring> #include <ctime> #include <stack> #include <cmath> #define LL long long using namespace std;
void BFLCS(string s1, string s2) { int ans=0; int m,n; m=s1.length(); n=s2.length(); char sub[m],s[m]; for(int i=1;i<pow(2,m);i++){ int l=0,j=0,k=0; for(j=0;j<m;j++) if(1&(i>>j)) sub[l++]=s1[j]; sub[l]='\0'; j=0; while(j<l && k<n){ if(sub[j]==s2[k]) j++; k++; } if(j==l && j>ans){ ans=j; strcpy(s,sub); } } printf("LCS长度:%d\n",ans); printf("LCS:"); puts(s); } void LCS(string s1,string s2) { int m=s1.length()+1; int n=s2.length()+1; int **c; int **b; c=new int* [m]; b=new int* [m]; for(int i=0;i<m;i++) { c[i]=new int [n]; b[i]=new int [n]; for(int j=0;j<n;j++) b[i][j]=0; } for(int i=0;i<m;i++) c[i][0]=0; for(int i=0;i<n;i++) c[0][i]=0; for(int i=0;i<m-1;i++) { for(int j=0;j<n-1;j++) { if(s1[i]==s2[j]) { c[i+1][j+1]=c[i][j]+1; b[i+1][j+1]=1; } else if(c[i][j+1]>=c[i+1][j]) { c[i+1][j+1]=c[i][j+1]; b[i+1][j+1]=2; } else { c[i+1][j+1]=c[i+1][j]; b[i+1][j+1]=3; } } } cout<<"填表结果:"<<endl; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { cout<<c[i][j]<<' '; } cout<<endl; } cout<<"LCS位置:"<<endl; stack<char> same; stack<int> same1,same2; for(int i = m-1,j = n-1;i >= 0 && j >= 0; ) { if(b[i][j] == 1) { i--; j--; same.push(s1[i]); same1.push(i); same2.push(j); } else if(b[i][j] == 2) i--; else j--; } cout<<s1<<endl; for(int i=0;i<m && !same1.empty();i++) { if(i==same1.top()) { cout<<'^'; same1.pop(); } else cout<<' '; } cout<<endl<<s2<<endl; for(int i=0;i<n && !same2.empty();i++) { if(i==same2.top()) { cout<<'^'; same2.pop(); } else cout<<' '; } cout<<endl<<"LCS长度:"<<c[m-1][n-1]<<endl; for (int i = 0; i<m; i++) { delete [] c[i]; delete [] b[i]; } cout<<"LCS:"; while(!same.empty()) { cout<<same.top(); same.pop(); } cout<<endl; delete []c; delete []b; } int main() { string s1="6234572"; string s2="91822324523452346623452323463"; int begin,end; printf("------------------------\n"); printf("暴力求解:\n"); begin=clock(); BFLCS(s1,s2); end=clock(); printf("所用时间:%d毫秒\n",end-begin); printf("------------------------\n"); printf("DP求解:\n"); begin=clock(); LCS(s1,s2); end=clock(); printf("所用时间:%d毫秒\n",end-begin); return 0; }
|
结果



总结
蛮力算法改进
可以看到,蛮力算法的时间复杂度集中在求X
,即程序中S1
的子序列。若S1
足够短,则所消耗的时间会大大降低。
通过比较S1
与S2
的串长,转而求取较短的串的子序列,可以大幅缩短某些情况下的时间消耗。
S1
过长的情况

交换S1
与S2

DP改进
对于仅需要求取LCS_length
的问题。由于填写第i
行时,仅仅需要表格的第i
行和第i-1
行:利用滚动数组,可以优化空间。同时让更短的串作为列,仅需O(min{m,n})的空间复杂度。
体会
一般来说,蛮力算法是最容易想到的算法。但在此问题中,对于求出一个串的所有子序列这个问题仍然十分困难。我也是参考了网络上(overview)的方法和同学的建议才想出个所以然。
但要能熟悉了DP的解题思路,明白“找出子问题、构建方程、回溯求解”这三个部分,反而会更加地便于解决问题。