动态规划.docx
《动态规划.docx》由会员分享，可在线阅读，更多相关《动态规划.docx（25页珍藏版）》请在冰点文库上搜索。
动态规划
动态规划
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。
但是经分解得到的子问题往往不是互相独立的。
不同子问题的数目常常只有多项式量级。
在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
动态规划基本步骤:
（1）找出最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
实例一、完全加括号的矩阵连乘积
问题可递归定义：
（1）单个矩阵是完全加括号的；
（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。
设有四个矩阵A,B,C,D它们的维数分别是:
A=50*10,B=10*40,C=40*30,D=30*5
总共有五中完全加括号的方式：
例如：
（（A（BC））D）:
10*40*30+10*30*50+50*30*5=34500
给定矩阵{A1,A2,A3,...,An}，其中Ai与A（i+1）是可乘的。
i=1,2,3,...,n-1。
考察这n个矩阵的连乘积A1*A2*A3...An.
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。
这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
矩阵连乘问题
给定矩阵{A1,A2,A3,...,An}，其中Ai与A（i+1）是可乘的。
i=1,2,3,...,n-1。
考察这n个矩阵的连乘积A1*A2*A3...An.如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少.
穷举法：
列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
算法复杂度分析：
对于n个矩阵的连乘积，设其不同的计算次序为P（n）
由于每种加括号方式都可以分解为两个子矩阵的加括号问题
（A1...Ak）（A（k+1）…An）可以得到关于P（n）的递推式如下：
动态规划：
将矩阵连乘积A（i）A（i+1）…A（j）简记为A[i:
j]，这里i<=j。
考察计算A[i:
j]的最优计算次序。
设这个计算次序在矩阵A（k）和A（k+1）之间将矩阵链断开，i<=k计算量：
A[i:
k]的计算量加上A[k+1,j]，再加上A[i:
k]*A[k+1][j]的计算量。
分析最优解的结构
特征：
计算A[i:
j]的最优次序所包含的计算矩阵子链A[i:
k]和A[k+1:
j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
建立递归关系
设计算A[i:
j]，1<=i<=j<=n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]
当i=j时，A[i:
j]=Ai，因此，m[i,i]=0，i=1,2,…,n
当i这里A（i）的维数为p（i-1）*（i）（注：
p（i-1）为矩阵A（i）的行数，p（i）为矩阵A[i]的列数）
可以递归地定义m[i,j]为：
k的位置只有j-i种。
计算最优值
对于1<=i<=j<=n不同的有序对（i,j）对应于不同的子问题。
因此，不同子问题的个数最多只有：
（大括号表示C（n,2），组合的意思。
后面的符号表示“紧渐近界记号”）
但是，在递归计算时，许多子问题被重复计算多次。
这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。
在计算过程中，保存已解决的子问题答案。
每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。
用动态规划法求最优解
连乘矩阵假如为：
计算过程为：
从m可知最小连乘次数为m[1][6]=15125
从s可知计算顺序为（（A1（A2A3））（（A4A5））A6））
实现：
代码
/*主题：
矩阵连乘问题
*作者：
chinazhangjie
*邮箱：
chinajiezhang@
*开发语言：
C++
*开发环境：
MircosoftVirsualStudio2008
*时间:
2010.11.14
*/
#include
#include
usingnamespacestd;
classmatrix_chain
{
public:
matrix_chain（constvector&c）{
cols=c;
count=cols.size（）;
mc.resize（count）;
s.resize（count）;
for（inti=0;imc[i].resize（count）;
s[i].resize（count）;
}
for（inti=0;ifor（intj=0;jmc[i][j]=0;
s[i][j]=0;
}
}
}
//使用备忘录方法计算
voidlookup_chain（）{
__lookup_chain（1,count-1）;
min_count=mc[1][count-1];
cout<<"min_multi_count="<//输出最优计算次序
__trackback（1,count-1）;
}
//使用普通方法进行计算
voidcalculate（）{
intn=count-1;//矩阵的个数
//r表示每次宽度
//i,j表示从从矩阵i到矩阵j
//k表示切割位置
for（intr=2;r<=n;++r）{
for（inti=1;i<=n-r+1;++i）{
intj=i+r-1;
//从矩阵i到矩阵j连乘，从i的位置切割，前半部分为0
mc[i][j]=mc[i+1][j]+cols[i-1]*cols[i]*cols[j];
s[i][j]=i;
for（intk=i+1;kinttemp=mc[i][k]+mc[k+1][j]+
cols[i-1]*cols[k]*cols[j];
if（tempmc[i][j]=temp;
s[i][j]=k;
}
}//fork
}//fori
}//forr
min_count=mc[1][n];
cout<<"min_multi_count="<//输出最优计算次序
__trackback（1,n）;
}
private:
int__lookup_chain（inti,intj）{
//该最优解已求出，直接返回
if（mc[i][j]>0）{
returnmc[i][j];
}
if（i==j）{
return0;//不需要计算，直接返回
}
//下面两行计算从i到j按照顺序计算的情况
intu=__lookup_chain（i,i）+__lookup_chain（i+1,j）
+cols[i-1]*cols[i]*cols[j];
s[i][j]=i;
for（intk=i+1;kinttemp=__lookup_chain（i,k）+__lookup_chain（k+1,j）
+cols[i-1]*cols[k]*cols[j];
if（tempu=temp;
s[i][j]=k;
}
}
mc[i][j]=u;
returnu;
}
void__trackback（inti,intj）{
if（i==j）{
return;
}
__trackback（i,s[i][j]）;
__trackback（s[i][j]+1,j）;
cout<}
private:
vectorcols;//列数
intcount;//矩阵个数+1
vector>mc;//从第i个矩阵乘到第j个矩阵最小数乘次数
vector>s;//最小数乘的切分位置
intmin_count;//最小数乘次数
};
intmain（）
{
//初始化
constintMATRIX_COUNT=6;
vectorc（MATRIX_COUNT+1）;
c[0]=30;
c[1]=35;
c[2]=15;
c[3]=5;
c[4]=10;
c[5]=20;
c[6]=25;
matrix_chainmc（c）;
//mc.calculate（）;
mc.lookup_chain（）;
return0;
}
算法复杂度分析：
算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。
循环体内的计算量为O
（1），而3重循环的总次数为O（n^3）。
因此算法的计算时间上界为O（n^3）。
算法所占用的空间显然为O（n^2）。
动态规划算法的基本要素
一、最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：
首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
最优子结构是问题能用动态规划算法求解的前提。
同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
二、重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。
因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
三、备忘录方法
备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
实现（见矩阵连乘源码）
实例二、最长公共子序列
若给定的序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格下表序列{i1,i2,…,ik}使得对于所有的j=1,2,…k有zj=xij。
例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
问题表述：
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
最长公共子序列的结构
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则
（1）若xm=yn，则zk=xm=yn，且z（k-1）是x（m-1）和y（n-1）的最长公共子序列。
（2）若xm!
=yn且zk!
=xm，则Z是x（m-1）和Y的最长公共子序列。
（3）若xm!
=yn且zk!
=yn，则Z是X和y（n-1）的最长公共子序列。
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。
因此，最长公共子序列问题具有最优子结构性质。
子问题的递归结构
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。
用c[i][j]记录序列Xi和Yi的最长公共子序列的长度。
其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。
当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。
故此时C[i][j]=0。
其它情况下，由最优子结构性质可建立递归关系如下：
由于在所考虑的子问题空间中，总共有θ（mn）个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率
计算最优值和构造最长公共子序列（见源码）
实现：
代码
/*主题：
最长公共子序列
*作者：
chinazhangjie
*邮箱：
chinajiezhang@
*开发语言：
C++
*开发环境：
MicrosoftVisualStudio2008
*时间:
2010.11.14
*/
#include
#include
usingnamespacestd;
//longestcommonsequence
classLonComSequence
{
public:
typedefvector>LCS_Type;
typedefvector>MarkType;
public:
LonComSequence（constvector&vSeq1,
constvector&vSeq2）
:
mc_nEqual
（1）,mc_nSq1move
（2）,mc_nSq2move（3）
{
m_vSeq1=vSeq1;
m_vSeq2=vSeq2;
m_nLen1=vSeq1.size（）;
m_nLen2=vSeq2.size（）;
//初始化最长公共子序列的长度
m_lcsLen.resize（m_nLen1+1）;
m_mtMark.resize（m_nLen1+1）;
for（inti=0;im_lcsLen[i].resize（m_nLen2+1）;
m_mtMark[i].resize（m_nLen2+1）;
}
}
//计算最长公共子序列的长度
intcalLcsLength（）
{
for（inti=1;i<=m_nLen1;++i）{
m_lcsLen[i][0]=0;//序列二的长度为0，公共子序列的长度为0
}
for（inti=1;i<=m_nLen2;++i）{
m_lcsLen[0][i]=0;//序列一的长度为0，公共子序列的长度为0
}
for（inti=0;ifor（intj=0;jif（m_vSeq1[i]==m_vSeq2[j]）{
m_lcsLen[i+1][j+1]=m_lcsLen[i][j]+1;
m_mtMark[i+1][j+1]=mc_nEqual;
}
elseif（m_lcsLen[i][j+1]>=m_lcsLen[i+1][j]）{
m_lcsLen[i+1][j+1]=m_lcsLen[i][j+1];
m_mtMark[i+1][j+1]=mc_nSq1move;
}
else{
m_lcsLen[i+1][j+1]=m_lcsLen[i+1][j];
m_mtMark[i+1][j+1]=mc_nSq2move;
}
}
}
returnm_lcsLen[m_nLen1][m_nLen2];
}
//构造最长公共子序列
voidLCS（）{
cout<<"LCSis:
";
__LCS（m_nLen1,m_nLen2）;
cout<}
private:
void__LCS（inti,intj）
{
if（i==0||j==0）{
return;
}
if（m_mtMark[i][j]==mc_nEqual）{
__LCS（i-1,j-1）;
cout<}
elseif（m_mtMark[i][j]==mc_nSq1move）{
__LCS（i-1,j）;
}
else{
__LCS（i,j-1）;
}
}
private:
vectorm_vSeq1;//序列一
vectorm_vSeq2;//序列二
intm_nLen1;//序列一的长度
intm_nLen2;//序列二的长度
LCS_Typem_lcsLen;//最长公共子序列的长度
MarkTypem_mtMark;//记录m_lcsLen
constintmc_nEqual;//相等的标志
constintmc_nSq1move;//序列一左移的标志
constintmc_nSq2move;//序列二左移的标志
};
intmain（）
{
vectors1;
s1.push_back（'A'）;
s1.push_back（'B'）;
s1.push_back（'C'）;
s1.push_back（'D'）;
s1.push_back（'E'）;
s1.push_back（'F'）;
vectors2;
s2.push_back（'B'）;
s2.push_back（'D'）;
s2.push_back（'F'）;
s2.push_back（'G'）;
s2.push_back（'H'）;
LonComSequencelcs（s1,s2）;
cout<lcs.LCS（）;
return0;
}
算法的改进
在算法lcsLength和lcs中，可进一步将数组b省去。
事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。
对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。
事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。
因此，用2行的数组空间就可以计算出最长公共子序列的长度。
进一步的分析还可将空间需求减至O（min（m,n））。
实例三、最大子段和
问题表述
n个数（可能是负数）组成的序列a1,a2,…an.求该序列
例如:
序列（-2,11,-4,13,-5,-2），最大子段和：
11-4+13＝20。
（1）穷举算法：
O（n3）,O（n2）
（2）分治法：
将序列a[1:
n]从n/2处截成两段：
a[1:
n/2],a[n/2+1:
n]
实例三、最大子段和
问题表述
n个数（可能是负数）组成的序列a1,a2,…an.求该序列
子序列的最大值。
也就是
例如:
序列（-2,11,-4,13,-5,-2），最大子段和：
11-4+13＝20。
（1）穷举算法：
O（n3）,O（n2）
（2）分治法：
将序列a[1:
n]从n/2处截成两段：
a[1:
n/2],a[n/2+1:
n]
一共存在三种情况：
a.最大子段和出现在左边一段
b.最大子段和出现在右边一段
c.最大子段和跨越中间的断点
对于前两种情况，只需继续递归调用，而对于第三种情况：
那么S1+S2是第三种情况的最优值。
（3）动态规划法：
定义b[j]：
含义：
从元素i开始，到元素j为止的所有的元素构成的子段有多个，这些子段中的子段和最大的那个。
那么：
如果：
b[j-1]>0,那么b[j]=b[j-1]+a[j]
如果：
b[j-1]<=0,那么b[j]=a[j]
这样，显然，我们要求的最大子段和，是b[j]数组中最大的那个元素。
实现：
代码
/*主题：
最大子段和
*作者：
chinazhangjie
*邮箱：
chinajiezhang@
*开发语言：
C++
*开发环境：
MicrosoftVirsualStudio2008
*时间
升级会员 