动态规划的基本理论以及优化

《动态规划的基本理论以及优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划的基本理论及其优化动态规划的基本理论及其优化南京外国语学校贾志鹏【关键词】动态规划、优化【摘要】本文讨论了一种信息学竞赛中经常使用的算法——动态规划。文章先介绍了动态规划的基本理论和其正确所需满足的两个条件：最优子结构和无后效性。然后列举了动态规划解题的基本步骤，并结合了部分经典例题进行分析。最后介绍了一些动态规划常用的优化方法。【目录】一、动态规划的基本理论（1）引例——数塔问题（2）动态规划的一些术语（3）动态规划正确所需满足的条件二、动态规划的应用（1）解决动态规划问题的基本步骤（2）一些动态规划的经典例题（3）树型动态规划三、动态规划的优化（1）降

2、维（2）预处理（3）使用高级数据结构（4）重新建立模型第1页共32页动态规划的基本理论及其优化一、动态规划的基本理论引例——数塔问题动态规划(DynamicProgramming)是在上世纪50年代，为了解决一类阶段性决策问题而诞生的高效算法。提到动态规划，最先想到的应该是数塔问题。数塔问题是说有如下一个n行的数塔：105367403050263557932314437898然后要你从第一行的第一个数开始，每次向左或向右走到下一行，直到走到最后一行，然后计算经过的所有数的和，问你这个和最大为多少。对于这种问题，最朴素的算法就是搜索（实际上就是一个穷举）。从第一行开

3、始，每次决定是向左走还是向右走，最后再统计一下和，取出最小值。但是这样的算法时间复杂度高达O(2^n)，n稍微一大就会超时。所以我们要考虑更高效的算法。先看一个比较简单的例子：从第一行到第四行的第三个数57可以有很多方案，这些方案中有一个最优的方案。然后57再向下走有2种方案，如果要使最后的方案最优，那么到57这个数的方案也要最优。再来看看我们搜索的过程，对于到57这个数的每种方案，我们可能搜索了很多很多遍，在这个例子中至少搜索了2遍，这就是一种时间上的浪费。所以，我们用数组记录下到数塔中每个数的最优方案，就可以避免这种重复的无用劳动。这就是动态规划算法。动态规划

4、的一些术语阶段：将所给问题按照时间或空间分解成若干互相联系的阶段，以便按次序去求解每一阶段的解。如数塔问题的中阶段就是每一行的最优解。状态：每个阶段都有许多状态，当前阶段中状态的解必定是由前面阶段状态中的状态“变化”而来的，这种变化我们叫做状态转移。如数塔问题中的状态就是每一行每一个数的最优解。决策：对于状态转移的过程，我们有很多种可行的选择，这些选择就叫做决策。我们要根据问题选取最优决策。边界条件：在上述问题中，有一些状态的解无需通过前面阶段上的状态便可得到，我们称这些状态为边界条件。如数塔问题中第一行第一个数的最优解，毫无疑问地就是本身数的值。状态转移方程：在

5、确定了阶段和状态之后，我们就可以用字母表示某一阶段上某一状态的最优值。比如我们用f[i,j]表示数塔问题中到第i行，第j个数的最优解，那么状态转移方程就应该是：f[i,j]=f[i-1,j-1]

6、j=if[i,j]=max(f[i-1,j],f[i-1,j-1])+a[i,j]

7、j

8、i-1,j-1]叫做f[i,j]的子问题。动态规划正确所需的条件动态规划正确需要满足两个条件：最优子结构和无后效性。最优子结构是指，对于当前状态的子问题最优，并且我们做出的决策最优，就能保证当前状态的解最优。这样说可能太过于抽象，我就举一个不满足最优子结构的例子吧。比如前文中的数塔问题，若最后问的不是最大值是多少，而是问绝对值最小是多少，那么对于前面的建模方式就不满足最优子结构了（不是说这题不能用动态规划解决）。应该很容易看出来，子问题解最优无法保证当前状态解最优。动态规划正确需满足的另一个条件是无后效性。无后效性就是说当前阶段的解只能由前面的阶段得到（这里的前面

9、的阶段也可以是同一阶段，但是先计算的状态，如果这样的话，实际上这种状态也可以看做是一种阶段），不能与后面的阶段（即当前还未算出的状态）有关。为了满足无后效性，我们有时会人为地改变阶段的顺序。当然，对于有些问题，无论我们怎么改变顺序，都无法满足无后效性的要求，那么我们就认为这种动态规划是错误的。对于不满足无后效性的问题，我也举一个例子。在下面这张有向图中，要你求出从起点s到终点t的最短路径。15V5V22107V7163V4S8912T5V6V1V3V82863很容易想到的建模方式就是以每个顶点为阶段，那么状态只有一种，转移方程应该也很好想：f[i]=min(f[j

10、]+w[j