做网站的都是什么专业毕业的,网站及备案,网站建设实训结论和体会,wordpress的文章分类一、动态规划算法与分治法的异同
相同点#xff1a;
A、二者均是将待求解的问题分成若干子问题来求解。
B、二者在编写代码的时候#xff0c;都要用到递归。
不同点#xff1a;
A、分治法求解的问题#xff0c;在将问题分成若干子问题之后#xff0c;其子问…一、动态规划算法与分治法的异同
相同点
A、二者均是将待求解的问题分成若干子问题来求解。
B、二者在编写代码的时候都要用到递归。
不同点
A、分治法求解的问题在将问题分成若干子问题之后其子问题之间是独立存在的没有相互关联。而动态规划问题划分后得到的子问题之间相互关联。
B、动态规划问题在求解时需要一个表来记录已解决的子问题的答案从而避免大量的重复计算。动态规划算法适合用于解最优化问题。这就表明这类最优化问题可能有很多解但不一定都是最优解而利用本算法找出的解可能还是众多最优解里的一个
二、最优解问题结构性质
最优子结构当问题的最优解包含了其子问题的最优解时称该问题具有最优子结构性质。
重叠子问题在用递归算法自顶向下解决问题的时候每次产生的子问题并不总是新问题有些子问题被反复计算。动态规划算法正式利用这种子问题的重叠性质对每个子问题只解一次并将其保存在表格中。
从一般意义上来讲问题所具有的这两个重要性质是该问题可用动态规划算法求解的基本要素。
三、动态规划问题分析及解决步骤
A、找出最优解的性质刻画其结构特征。
B、递归定义最优值
C、自底向上计算最优值最优值只是一个结果最优解是一个过程
D、根据得到的信息构造最优解A-C是动态规划算法的进本步骤此步在需要求出问题的最优解时才需执行
好了有了上面动态规划的基础知识后我们开始本文的“重头戏”——最长公共子序列。
四、问题描述问题大意
子序列一个给定序列中删除若干元素后得到的序列就是该序列的子序列。
公共子序列如果有两个序列按照上述步骤之后得到的子序列相同那么这个子序列被称为这两个序列的公共子序列。
例有如下两个序列
X{A、B、C、B、D、A、B}Y{B、D、C、A、B、A}
则序列Z{B、C、A}就是二者的公共子序列那么什么是最长的公共子序列大家应该知道了吧
在这里需要说明的是一个长度为n的序列它一共有2的n次方个子序列有(2^n – 1)个非空子序列。大家需要注意的是这里说的是序列和原来的顺序有关联而不是高中所学无序的集合。
下面将按照动态规划算法设计的步骤来设计解决此问题的算法
1、问题结构 上述证明之后本问题具有最优子结构性质。
2、递归结构
要找出X{x1,x2,...,xm}和Y{y1,y2,...,yn}的最长公共子序列可按照以下方式递归
A、当XmYn时找出Xm-1和Yn-1的最长公共子序列然后在其尾部加上XmXmYn即可得X、Y的最长公共子序列。
B、当XmYn时则得解决两个子问题Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列二者中较长者即为X和Y的最长公共子序列。
由这个递归结构来看此问题具有子问题重叠性质例如在计算X和Y的最长公共子序列时可能要计算X和Yn-1及Xm-1和Y的最长公共子序列这两个子问题都包含一个公共子问题即要计算Xm-1和Yn-1的最长公共子序列。
首先建立子问题最优值的递归关系用从c[i][j]记录序列Xi和Yi的最长公共子序列的长度。其中Xi{x1,x2,...,xi};Yj{y1,y2,...,yj}
当i0或j0时空序列是Xi和Yj的最长公共子序列所以此时c[i][j]0;
其他情况
A、i0;j0时,c[i][j]0;
B、i,j0;XiYj时c[i][j]c[i-1][j-1]1
C、i,j0;Xi!Yj时c[i][j]max{c[i][j-1],c[i-1][j]}
3、计算最优值
直接利用上述递归式写出代码。其中XY是输入的两个序列 b[i][j]记录c[i][j]的值是由哪个子问题的解得来的这在构造最长公共子序列时要用到。
void LCSLength(int m,int n,char x[],char y[],int c[][50],int b[][50])
{int i,j;for(i1;im;i)//当j0时c[i][j]0c[i][0]0;for(j1;jn;j)//当i0时c[i][j]0c[0][j]0;for(i1;im;i)//对最长公共子序列的长度进行记录for(j1;jn;j){if(x[i]y[j])//XiYj的情况{c[i][j]c[i-1][j-1]1;//c[i][j]存储Xi和Yj的最长公共子序列的长度b[i][j]1; //斜向上 //b[i][j]记录c[i][j]的值是由哪个子问题的解得来的}else if(c[i-1][j]c[i][j-1]){c[i][j]c[i-1][j];b[i][j]2;//竖直向上}else{c[i][j]c[i][j-1];b[i][j]3;//水平向左}}
}
4、构造最长公共子序列
用二维数组b快速构造序列X和Y的最长公共子序列。首先从b[m][n]开始依照其值在数组b中搜索。
A、当在b[i][j]1时表示Xi和Yi的最长公共子序列是由Xi-1和Yi-1的最长公共子序列在尾部加上Xi所得到的。
B、当在b[i][j]2时表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。
C、当在b[i][j]3时表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。
如此将最长公共子序列打印出来。代码如下
void LCS(int i,int j,char x[], int b[][50])
{if(i0||j0)return;if(b[i][j]1)//表示Xi和Yi的最长公共子序列是由Xi-1和Yi-1的最长公共子序列在尾部加上Xi所得到的{//b[i][j]1时表示左斜45°向上也即这个时候对应的字母时LCS中的一个。LCS(i-1,j-1,x,b);coutx[i] ;}else if(b[i][j]2)//表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。LCS(i-1,j,x,b);else//表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。LCS(i,j-1,x,b);
}
所以上述的所有步骤转变为完整代码如下
#includestdlib.h
#includestdio.h
#includeiostream
using namespace std;
int c[50][50];
int b[50][50];
char x[1000];//存放X字符串
char y[1000];//存放Y字符串
void LCSLength(int m,int n,char x[],char y[],int c[][50],int b[][50])
{int i,j;for(i1;im;i)//当j0时c[i][j]0c[i][0]0;for(j1;jn;j)//当i0时c[i][j]0c[0][j]0;for(i1;im;i)//对最长公共子序列的长度进行记录for(j1;jn;j){if(x[i]y[j])//XiYj的情况{c[i][j]c[i-1][j-1]1;//c[i][j]存储Xi和Yj的最长公共子序列的长度b[i][j]1; //斜向上 //b[i][j]记录c[i][j]的值是由哪个子问题的解得来的}else if(c[i-1][j]c[i][j-1]){c[i][j]c[i-1][j];b[i][j]2;//竖直向上}else{c[i][j]c[i][j-1];b[i][j]3;//水平向左}}
}
void LCS(int i,int j,char x[], int b[][50])
{if(i0||j0)return;if(b[i][j]1)//表示Xi和Yi的最长公共子序列是由Xi-1和Yi-1的最长公共子序列在尾部加上Xi所得到的{//b[i][j]1时表示左斜45°向上也即这个时候对应的字母时LCS中的一个。LCS(i-1,j-1,x,b);coutx[i] ;}else if(b[i][j]2)//表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。LCS(i-1,j,x,b);else//表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。LCS(i,j-1,x,b);
}
int main()
{int xn,yn;//XY字符串的大小cout请输入X集合的元素个数endl;cinxn;cout请输入X集合的元素endl;int i0;//用于循环输入X和Y的字符串for(i1;ixn;i)cinx[i];cout请输入y集合的元素个数endl;cinyn;cout请输入y集合的元素endl;for(i1;iyn;i)ciny[i];LCSLength(xn,yn,x,y,c,b);cout X和Y的最长公共子序列为;LCS(xn,yn,x,b);cout endl;int j 0;int m 0;printf(b[i][j]中的数字\n);for (i 0; i xn; i)for (j 0; j yn; j){ printf(%d , b[i][j]);m;if (m xn){m 0;printf(\n);}}m 0;printf(c[i][j]中的数字\n);for (i 0; i xn; i)for (j 0; j yn; j){printf(%d , c[i][j]);m;if (m xn){printf(\n);m 0;}} system(pause);return 0;
}把c[i][j]和b[i][j]对应起来之后得到下图
从下图中可以看出用二维数组b[i][j]中的信息可以构建出X和Y的一个最长公共子序列。从b[xn][yn]开始沿着橘黄色的箭头方向追踪
A、b[i][j]等于1时左斜45°向上跳并且起跳的字母就是LCS的一个成员
B、b[i][j]等于2时竖直向上跳。
C、b[i][j]等于3时水平向左跳。 参考《计算机算法设计与分析·第五版 》王晓东编著
