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

《常见动态规划算法问题策略分析.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、f1,j-1+a1,j,f2,j-1+t2,j-1+a1,jj≥2f2,j=e2+a2,1j=1minf2,j-1+a2,j,f1,j-1+t1,j-1+a2,jj≥2传输完后，加上自动下线时间x1,x2,总装配时间：f*=min⁡{f1,j+x1,f2,j+x2}最后采用自底向上的方法求解算法并递归的输出最优解的值。1.矩阵链乘问题分析：若只有一个矩阵，无最优解。若大于一个矩阵：对于A1,A2,…,An，我们得在Ak和Ak+1之间加上一个括号使得分开的两个子矩阵链乘积最小，再分别对两个子问题找到最优的划分结果：设m[i,j]为计算矩阵链Ai..j的乘积所需的

5、最少标量乘法次数。若：i=j，不需任何计算，即m[i,j]=0，否则：mi,j=mi,k+mk+1,j+pi-1pkpj则最终公式为：f1,j=0i=jmin(mi,k+mk+1,j+pi-1pkpj)i

6、最后一个元素不同：求X[1…m-1]和Y[1…n]或者X[1…m-1]和Y[1…n]两个子序列的最长公共子序列。令C[i,j]为Xi和Yj的LCS的长度，如果i=0或者j=0则LCS=0，则根据LCS的最优子结构特征我们可以构造出：C[i,j]=0i=0orj=0Ci-1,j-1+1i,j>0andxi=y[j]max(Ci-1,j,Ci,j-1)i,j>0andxi≠y[j]根据递归式，我们能写出一个递归算法来计算最长公共子序列，由于LCS的子问题过多，所以我们采用自底向上的计算。在这个过程中，我们需要借组一个数组b[i,j]来记录最优解得构造过程，利用b[

7、i,j]所记录的元素来输出最优解。1.最大字段和分析:求给定的n个整数（可能但不全为负）a1,a2,…,an,的i跟j，使ai到aj的和最大。我们定义b[j]=max(sum(i:j))，为从i到j子段的最大子段和。我们比较b[j-1]+a[j]和a[j]的大小,如果b[j-1]<0,显然b[j-1]不是最大子段，此时b[j]=a[j]。反之，我们令b[j-1]+a[j]=b[j],找出最大的子段和。则：b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n由上面的递归公式我们可以写出一个自底向上的递归算法，在算法中我们借助一个变量sum来记录过

8、程中的最大子段和，若此时的b[j]>s