常见动态规划算法问题策略分析

1、常见动态规划算法问题策略分析 2目录一、动态规划策略11.动态规划介绍12.求解动态规划问题步骤1二、几种动态规划算法的策略分析11.装配线调度问题12.矩阵链乘问题23.最长公共子序列（LCS）34.最大字段和45.0-1背包问题4三、两种解决策略51.自底向上策略52.自顶向上（备忘录）策略53.优缺点分析5四、总结6一、 动态规划策略1. 动态规划介绍动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子

2、阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。2. 求解动态规划问题步骤（1） 确定最优解结构（2） 递归定义最优解的值（3） 自底向上计算最

3、优解的值（4） 重构最优解二、 几种动态规划算法的策略分析1. 装配线调度问题分析：首先确定最优解结构，分析问题可知大致分为两种情况：从第一个站出站（j=1）和从第j个站出站（j>=2）。当j=1：货物上线后只经过一个站，f1j=e1+a1,1当j>=2，又可分为跳线和不跳线两种情况：不跳线：f1j=f1j-1+a1,j跳线：当货物从f2跳到f1，有一个跳转时间t2,j-1，则：f1j=f2j-1+t2,j-1+a1,j由对称关系，f2j可同理得出，最后： f1,j=e1+ a1,1 j=1minf1,j-1+a1,j,f2,j-1+ t2,j-1+a1,j j2 f2,j=e2+

4、 a2,1 j=1minf2,j-1+a2,j,f1,j-1+ t1,j-1+a2,j j2传输完后，加上自动下线时间x1,x2,总装配时间：f*=minf1,j+x1,f2,j+x2最后采用自底向上的方法求解算法并递归的输出最优解的值。2. 矩阵链乘问题分析：若只有一个矩阵，无最优解。若大于一个矩阵：对于A1,A2,An， 我们得在Ak和Ak+1之间加上一个括号使得分开的两个子矩阵链乘积最小，再分别对两个子问题找到最优的划分结果：设mi,j 为计算矩阵链Ai.j 的乘积所需的最少标量乘法次数。若：i=j，不需任何计算，即mi,j=0，否则：mi,j =mi,k+ mk+1,j+pi-1pkp

5、j则最终公式为：f1,j=0 i=jmin(mi,k+ mk+1,j+pi-1pkpj) i<j在计算时，采用了自底向上的方法来求解最优解，在求解过程中用一个辅助的数组S1.n-1,2.n来记录最优值mi，j对应的分割点K，这样能够构造出最优解。最后，借助辅助数组递归的输出最优解的值。3. 最长公共子序列（LCS）分析：可分为最后一个元素相同和不相同两种情况：最后一个元素相同：求X1m-1和Y1n-1两个子序列的最长公共子序列。最后一个元素不同：求X1m-1和Y1n或者X1m-1和Y1n两个子序列的最长公共子序列。令Ci,j为Xi 和Yj的LCS的长度，如果i=0或者j=0则LCS=0，

6、则根据LCS的最优子结构特征我们可以构造出：Ci,j =0 i=0 or j=0Ci-1,j-1+1 i,j>0 and xi=yj max(Ci-1,j,Ci,j-1) i,j>0 and xi yj6根据递归式，我们能写出一个递归算法来计算最长公共子序列，由于LCS的子问题过多，所以我们采用自底向上的计算。在这个过程中，我们需要借组一个数组bi,j来记录最优解得构造过程，利用bi,j所记录的元素来输出最优解。4. 最大字段和分析:求给定的n个整数（可能但不全为负）a1,a2,an, 的i跟j，使 ai 到 aj 的和最大。我们定义bj=max(sum(i:j)，为从i到j子段的

7、最大子段和。我们比较bj-1+aj和aj的大小,如果bj-1<0,显然bj-1不是最大子段，此时bj=aj。反之，我们令bj-1 + aj = bj,找出最大的子段和。则：bj=max( bj-1+aj, aj ), 1<=j<=n由上面的递归公式我们可以写出一个自底向上的递归算法，在算法中我们借助一个变量sum来记录过程中的最大子段和，若此时的bj>sum，更新sum中的值，反之，继续求解。直到程序进行完毕，输入sum中的最大子段和。5. 0-1背包问题分析：分数背包问题可以采用贪心策略解决，但我们在求解0-1背包问题时，我们只能采用动态规划策略。同样地：首先构造最优

8、子结构。令ci,j表示利用前i个物品装容量为j的背包所能获得的最大价值，可分两种情况：含物品n：去掉第n个物品，用W-wn容量的背包装物品1,2，,n-1：ci,j=ci-1,j-wi+vi不含物品n：用W容量背包装物品1,2,n-1：ci,j=ci-1,j当然，没有物品或没有容量，ci,j=0则总的递归式：Ci,j=0 i=0 or j=0Ci-1,j wi>jmax(Ci-1,j- wi+ vi,Ci-1,j) i>0 and wij有上述递归方程，就可写出相应递归算法，但该递归算法复杂度太高，可用V0.n,0.W来保存子问题(i,j)的最大值。b1.n,1.W用来保存所做出的

9、最优选择，以便构造最优解。在计算最优解的时候，保存所做出的最优决策，便可得到最优解。三、 两种解决策略1. 自底向上策略一般动态规划问题都是基于此策略。在用这种方法时一般需要恰当的定义子问题的规模，使得任何子问题都只依赖于更小的子问题的求解。我们可以将问题的规模按照由大到小排列依次求解。每个子问题都只求解一次。2. 自顶向上（备忘录）策略动态规划有一个性质为子问题重叠性质，就是对于子问题在递归过程中不断求解，虽然问题规模很小，但是求解次数会非常多，造成程序运行非常慢。在使用自顶向下的求解过程中，我们一般要设计一个备忘录，在递归求解过程中对于已经求解过的问题保存在备忘录中，当下次要使用时直接拿出来，不用再次求解。3. 优缺点分析自顶向下只需要求解问题需要的解，不需要对所有子问题都去求解。但是它需要额外的递归开销。自底向上必须对所有子问题进行求解但是可有效减少计算时间和所需的存储空间。四、 总结动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。解决动态规划问题的关键是找到最最优子结构并定义出递归式，根据经验，通常会分为若干种情况分开讨论，尤其注意容易遗漏的特殊情况（0、1、相等）。在求解