【CLRS】15-动态规划DynamicProgramming

动态规划Dynammic Programming

  1. 四步骤:
    1. 刻划一个最优解的结构特征
    2. 递归的定义最优解的值
    3. 计算最优解的值,通常采用自底向上的方法
    4. 利用计算出的信息构造一个最优解
  2. 动态规划方法是付出额外的内存空间来节省计算时间,是典型的以空间换时间的例子。当然其节省时间的效果是很明显的
  3. 动态规划有两种等价的实现方法:
    1. 带备忘的自顶向下法 top-down with memoization
    2. 自底向上法 bottom-up method
      两者的渐进时间相同

子问题图

  1. 子问题图是一个有向图,每个顶点唯一对应一个子问题
  2. 若求子问题x的最优解时需要直接用到子问题y的最优解,那么在子问题图中就会有一条从子问题x的顶点到子问题y的有向边。
  3. 子问题图 G=(V,E)的规模可以确定动态规划算法的运行时间:
    • 每个子问题只求解一次,一次算法运行时间等于每个子问题求解时间之和
    • 通常,一个子问题的求解时间与子问题图中对应顶点的出度成正比
    • 通常,动态规划算法的运行时间与顶点和边的数量线性关系

钢材切割问题

矩阵链乘法问题

动态规划原理

1. 最优子结构

  1. 问题是否适合应用动态规划算法,看是否具有最优子结构性质
  2. 发觉最优子结构的通用模式:
    1. 会做出一个选择。做出这次选择会产生一个或多个待解的子问题
    2. 假定已经知道哪种选择才会得到最优解
    3. 给定可获得最优解的选择后,我们可以确定这次选择会产生哪些子问题,以及如何最好的刻划子问题空间。
    4. 利用剪切-粘贴 Cut-and-paste:利用反证法证明每个子问题的解就是它本身的最优解
      1. 假定子问题的解不是其自身的最优解
      2. 剪切掉这些非最优解
      3. 将最优解粘贴进去
      4. 得到一个更优的解
      5. 与假设矛盾,因为你现在已经有了一个最优解
  3. 保持子问题尽可能简单,只在必要时才扩展他
  4. 对于不同问题,最优子结构的不同体现在两个方面:
    1. 原问题的最优解中涉及多少个子问题
    2. 在确定最优解使用哪些子问题时,我们需要考虑多少中选择
  5. 可以用子问题的总数和每个子问题需要考虑多少选择的乘积来粗略分析算法的运行时间
  6. 子问题图也可用来做类似的分析:图中每个顶点对应一个子问题,而选择对应子问题顶点的边
  7. 在动态规划方法中,我们通常自底向上的使用最优子结构