第三章-动态规划

动态规划算法

DynamicProgramming万玲1、概述什么是动态规划?它能解决哪些问题?解决的步骤又是什么样的?

动态规划（dynamicprogramming）作为一种多阶段决策优化过程的通用方法，它是在20世纪50年代由一位卓越的美国数学家RichardBellman所发明的。因此，这个技术名字中的programming是计划和规划的意思，不是代表计算机中的编程。

规划（programming）的含义意味着一系列的决策，而动态（dynammic）的含义则传递着这样一种思想，就是所作的决策可能依赖于当前状态，而与此前所作的决策无关。3.2举例：最短路径问题为了找到由A到E的最短路线，可以将该问题分成A-B-C-D-E4各阶段，在每个阶段都需要作出决策，即在A点需要决策下一步到B1还是B2或B3；同样，若到达第二阶段某个状态，比如B1,需要决定走向C1还是C2；依次类推，可以看出：各个阶段的决策不同，由A到E的路线就不同，当从某个阶段的某个状态发出一个决策，则这个决策不仅影响到下一各阶段的距离，而且直接影响后门各个阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条线路对应的线路最短。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法总体思想但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)WhyDivideandConquer技术的问题子问题是相互独立的如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低优化问题给定一组约束条件和一个代价函数,在解空间中搜索具有最小或最大代价的优化解很多优化问题可以分解为多个子问题,子问题相互关联,子问题的解被重复使用What动态规划的特点把原始问题分为一系列子问题求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复结算,节约计算时间自底向上的计算适用范围一类优化问题:可分为多个相关子问题,子问题的解被重复使用How使用动态规划的条件优化子结构当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构缩小子问题的集合,只要哪些优化问题包含了优化子问题,降低实现复杂性重叠子问题在问题的求解过程中,很多子问题的解被多次重复使用动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。3.3矩阵连乘（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵，它们的维数分别是：总共有五中完全加括号的方式矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积矩阵连乘问题

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为计算量：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<j时，可以递归地定义m[i,j]为：这里的维数为

的位置只有种可能计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法用动态规划法求最优解publicstaticvoidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;

for(inti=1;i<=n;i++)m[i][i]=0;

for(intr=2;r<=n;r++)

for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;

for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}A1A2A3A4A5A6303535

1515

55

1010

2020

25动态规划算法的基本要素一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。3.40/1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。

对于0/1背包问题，可以通过作出变量X1,X2,...,Xi的一个决策序列来得到它的解。而对变量X的决策就是决定它是取0值还是取1值。鉴定决策这些X的次序为Xn,Xn-1,...,X1。在对Xn作出决策之后，问题处于下列两种状态之一：背包的剩余容量是X=M，没有产生任何价值；剩余容量是X=M-wn，价值增长了pn。显然，剩余下来对Xn,Xn-1,...,X1的决策相对于决策X所产生的问题状态应该是最优的，否则Xn,Xn-1,...,X1就不可能是最优决策序列。背包问题的实例分析考虑以下情况的背包问题，n=3,W=6,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)f1(1)=max{f0(1),f0(1-w1)+p1}=0f1(2)=max{f0(2),f0(2-w1)+p1}=p1=1f1(3)到f1(6)与f1(2)相同f2(1)=max{f1(1),f1(1-w2)+p2}=0f2(2)=max{f1(2),f1(2-w2)+p2}=1f2(3)=f2(4)=max{f1(3),f1(3-w2)+p2}=2f2(5)=f2(6)=max{f1(5),f1(5-w2)+2}=3f3(6)=max{f2(6),f2(6-w3)+p3}=max{3,f1(2)+4}=40-1背包问题设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，在前i各物体中，能够装入载重量为j的背包中的物体的最大价值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。动态规划求解0/1背包的算法描述template<classType>Typeknapsack_dynamic(intw[],Typep[],intn,intm,BOOLx[]){intI,j,k;Typev,(*optp)[m+1]=newType[n+1][m+1];for(i=0;i<=n;i++){optp[i][0]=0;x[i]=FALSE;}for(i=0;i<=m;i++)optp[0][i]=0;//初始化动态规划０／１背包算法for(i=1;i<=n;i++){／／计算optp[i[]j]for(j=1;j<=m;j++){optp[i][j]=optp[i-1][j];if((j>=w[i])&&(optp[i-1,j-w[i]]+p[i])>optp[i-1][j])optp[i][j]=optp[i-1,j-w[i]]+p[i];}}j=m;//递推装入背包的物体for(i=n;i>0;i--){if(optp[i][j]>optp[i-1][j]){x[i]=FALSE;j=j-w[i];}}v=optp[n][m];Deleteoptp;Returnv;}//结束例题0/1背包问题有五个物体，其重量分别为2，2，6，5，4，价值分别是6，3，5，4，6，背包的载重量为10，求装入背包的物体及其总价值表。

012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515答案是110013.5最长公共子序列若给定序列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，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。Algorithm

lcsLength(x,y,b)1:m

x.length-1;2:n

y.length-1;3:c[i][0]=0;c[0][i]=0;4:for(inti=1;i<=m;i++)5:for(intj=1;j<=n;j++)6:if(x[i]==y[j])7:c[i][j]=c[i-1][j-1]+1;8:b[i][j]=1;9:elseif(c[i-1][j]>=c[i][j-1])10:c[i][j]=c[i-1][j];11:b[i][j]=2;12:else13:c[i][j]=c[i][j-1];14:b[i][j]=3;构造最长公共子序列Algorithmlcs(inti,intj,char[]x,int[][]b){

if(i==0||j==0)return;

if(b[i][j]==1){

lcs(i-1,j-1,x,b);System.out.print(x[i]);}

elseif(b[i][j]==2)lcs(i-1,j,x,b);

elselcs(i,j-1,x,b);}动态规划最长公共子序列例题求A=xyxzyxyzzy,B=xzyzxyzxyzxy的最长公共子序列。解：用两个表，来分别用来存放搜索过程中所得到的子序列的长度c[i][j]和状态b[i][j].

最终得到的最长公共子序列是A(1,2,3,4,6,7,8,10)=xyxzxyzy最长公共子序列的两个存储表012345678910111200000000000000101111111111112011222222222230112233333333401223334444445012333444555560123344455566701233455566678012344566677790123445666777100123445667778子序列的长度表最长公共子序列的状态表及搜索01234567891011120000000000000010133313313313202213313313313012221331