动态规划学习总结
动态规划简介：
动态规划通常应用于最优化问题，此类问题可能有多种可行解，每个解有一个值，而我们希望找出一个具有最优值的解，称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。
一、装配站调度
问题描述：
某汽车工厂有2个装配线，每个装配线有n 个装配站（按顺序编号1～n ）标记为Si,j，表示第i个装配线的第j个装配站，两个装配线的对应的装配站执行相同的功能，但所用的时间可能不同。经过第i条流水线（i=1，2）的第j 个装配站所花的时间为a[i][j]。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略，而移到另外一个流水线的下一个装配站则需要一定的时间t[i][j]。汽车进入流水线需要花时间，进入装配线1需要时间e[1]，进入装配线2需要时间e[2]; 汽车出流水线时需要花时间，出装配线1需要时间x[1]，出装配线2需要时间x[2] 。汽车的装配需要按顺序经过所有装配站。
现在已知装配时间a[i][j] 、转移时间t[i][j]、进入装配线的时间e[i]、出装配线的时间x[i]，要求输出装配一辆汽车所需要的最短时间，以及经过的装配站。
问题分析：
第一步，最优子结构
通过装配站S1，j的最快路线有两种选择
1.通过装配站S1,j-1的最快路线，然后通过装配站S1,j；
2.通过装配站S2,j-1的最快路线，从装配线2移到装配线1，然后通过装配站S1,j
通过装配站S2，j的最快路线有两种选择
1.通过装配站S2,j-1的最快路线，然后通过装配站S2,j；
2.通过装配站S1,j-1的最快路线，从装配线1移到装配线2，然后通过装配站S2,j
第二部，定义一个递归的解
我们选择在两条装配线上通过装配站j的最快路线的问题为子问题，j=1,2,…，n，令f[i][j]表示一辆汽车从起点到装配站Si,j的最快时间，f表示一辆汽车经过所有路线的最快时间。
f=min(f[1][n]+x[1],f[2][n]+x[2]);
f[1][1]=e[1]+a[1][1];
f[2][1]=e[2]+a[2][1];
f[1][j]=min(f[1][j-1]+a[1][j],f[2][j-1]+t[2][j-1]+a[1][j]);
f[2][j]=min(f[2][j-1]+a[2][j],f[1][j-1]+t[1][j-1]+a[2][j]);
程序代码：#define N 100
int min(int a,int b) {return a > b ? b : a ;}
FastestWay(int a[][],int e[],int x[])
{
int f[N][N];
f[1][1]=e[1]+a[1][1];
f[2][1]=e[2]+a[2][1];
for(int j=2;j<=n;j++)
{
f[1][j]=min(f[1][j]+a[1][j],f[2][j]+t[2][j-1]+a[1][j]);
f[2][j]=min(f[2][j]+a[2][j],f[1][j]+t[1][j-1]+a[2][j]);
}
f=min(f[1][n]+x[1],f[2][n]+x[2]);
return f;
}
二、最长公共子序列
问题描述：
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
问题分析：
这里提到一个定理，LCS的最优子结构：设X={x1,x2,…,xm} 和Y={y1,y2,…,yn} 为两个序列，并设Z={z1,z2,…,zk}为X和Y的任意一个LCS，则
1）如果xm=yn，那么zk=xm=yn，而且Zk-1是Xm-1和Yn-1的一个LCS；
2）如果xm!=yn，那么zk!=xm，蕴含Z是Xm-1和Y的一个LCS；
3）如果xm!=yn，那么zk!=yn，蕴含Z是X和Yn-1的一个LCS；
根据以上定理知，定义c[i,j]为序列Xi和Yj的一个LCS的长度则
当i=0或j=0时，c[i,j]=0；
当i,j>0和xi=yj时，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]);
程序代码：#define N 100
int max(int a,int b) {return a>b ? a : b;}
int LCS(char *str1,char *str2)//n,m为序列的长度
{
int c[N][N];
for(i=1,i<=n;i++) c[i][0]=0;
for(j=0,i<=m;j++) c[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(str1[i]==str2[j])
c[i][j]=c[i-1][j-1]+1;
else
c[i][j]=max(c[i-1][j],c[i][j-1]);
return c[n][m];
}
[ 本帖最后由 C_戴忠意 于 2012-11-8 20:44 编辑 ]
