Dynamic Programming

动态规划使用于子问题重叠的最优化问题 (Optimization Problem),求解的是一个最优解而不是最优解,因为可能不只有一个解达到最优值。
同时,动态规划也具有”无后效性”,或者说,动态规划对状态空间的遍历构成一张有向无环图,遍历顺序是该有向无环图的一个拓扑序。
我们通常按照如下四个步骤设计一个动态规划算法:

  1. 刻画一个最优解的结构特征.
  2.  递归地定义最优解的值.
  3. 计算最优解的值.
  4. 利用计算出的信息构造出一个最优解.

一个问题是否适用于动态规划求解同时依赖于子问题的无关性与重叠性,这里的无关性是指两个子问题不共享资源,而重叠性则是指一个子问题重复出现多次而已。同时我们要让子问题空间尽可能简单,只有在必要的时候才扩展它,虽然不是必须,但这是一个好的习惯。
在尝试使用动态规划方法时要小心,要注意问题是否具有最优子结构性质。
动态规划有两种等价的实现方法,第一种是带备忘的自顶向下法 (Top-Down With Memoization),此方法仍按自然的递归形式编写过程,但过程保存每个子问题的解。当需要一个子问题的解时,先检查是否已经保存过此解,如果是那就直接返回保存的值,从而节省计算时间;否则,按通常方法计算这个子问题,我们称这个递归是带备忘的 (Memoized),因为它”记住”了之前已经计算出的结果。而第二种是自底向上法 (Bottom-Up Method)。这种方法一般需要恰当的定义子问题”规模”的概念,使得任意子问题的求解都只依赖于”更小的”子问题的求解,因而我们可以将子问题按照规模排序,按由小至大的顺序求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已经保存。每个子问题只需要求解一次,当我们求解它时,它的所有前提子问题都已经求解完成。
通常情况下,如果每个子问题都必须至少求解一次,自底向上动态规划算法会比自顶向下备忘算法快一个常量系数,因为自底向上算法没有递归调用的开销,表的维护开销也更小。相反,如果子问题空间中的某些子问题完全不必求解,备忘方法就体现出优势了,因为它只会求解那些绝对必要的问题。
动态规划是付出额外的内存空间来节省时间,是典型的时空权衡 (Time-Memory Trade-Off)的例子。
“状态”、”阶段”和”决策”是构成动态规划算法的三要素,而”子问题重叠性”、”无后效性”和”最优子结构性质”是问题能用动态规划求解的三个基本条件。
动态规划算法把相同的计算过程作用于各阶段的同类子问题,就好像把一个固定的公式在格式相同的若干输入数据上运行。因此,我们一般只需要定义出动态规划的计算过程,就可以编程实现了。这个计算过程就被称为“状态转移方程”

© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发

请登录后发表评论