Mengzelev's Blog

算法导论学习笔记-动态规划

Word count: 1,396 / Reading time: 5 min
2018/08/31 Share

基本原理

以下是大段算法导论原句搬运。

只有带下划线的句子才是自己总结的。

最优化问题

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。我们成这样的解为问题的一个最优解,而不是最优解。

算法设计步骤

  • 刻画一个最优解的结构特征
  • 递归地定义最优解的值
  • 计算最优解的值,通常采用自底向上的方法
  • 利用计算出的信息构造一个最优解(有时不需要)

动态规划求解最优化问题应该具备的两个要素:最优子结构子问题重叠

简单来说就是,能根据原问题得到一个递推式(最优子结构),但是在这个递推式的计算过程中会出现大量重复计算的时候(子问题重叠),可以使用动态规划。

最优子结构性质

问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。

在发觉最优子结构性质的过程中,实际上遵循了如下的通用模式:
1.证明问题最优解的第一个组成部分是做出一个选择;
2.对于一个给定问题,在其可能的第一步选择中,你假定已经知道哪种选择才会得到最优解。
3.给定可获得的最优解的选择后,你确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间;
4.利用“剪切-粘贴”技术证明:作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解(反证法):假设子问题存在更优解,将子结构从整体中删除替换为更优解,与最优假设矛盾。

保持子问题空间尽可能简单,只在必要时才扩展它。(e.g.矩阵链乘法问题必须允许子问题在“两端”都可变)

可以用子问题的总数每个问题需要考察多少种选择这两个因素的乘积来粗略肥西动态规划算法的运行时间。

具有最优子结构的问题子问题之间是无关,同一个原问题的一个子问题的解不影响另一个子问题的解。e.g.无权最短路径vs无权最长路径

子问题重叠

如果递归方法反复求解相同的子问题,我们就称最优化问题具有重叠子问题性质。与之相对的,利用分治方法求解的问题通常在递归的每一步都生成全新的子问题。

重构最优解:用另一个数组来记录最优解

实现

  • 自顶向下的备忘算法
  • 自底向上的动态规划算法
    一般自底向上的动态规划算法会比较快(没有递归调用开销,表的维护开销也更小)

如果子问题空间中的某些子问题完全不必求解,备忘方法就会体现出优势

钢条切割问题

问题描述

某公司出售一段长度为i英寸的钢条的价格为$p_i(i=1,2,…,$单位为美元)。给定一段长度为n英寸的钢条和一个价格表$p_i(i=1,2,…,n)$,求切割钢条方案,使得销售收益$r_n$最大。

分析

长度为n英寸的钢条共有$2^{n-1}$中不同的切割方案。

如果一个最优解将钢条切割为k段$(1\le k\le n$),那么最优切割方案
$$ n=i_1+i_2+…+i_k$$

将钢条切割为长度分别为$i_1,i_2,…,i_k$的小段,得到最大收益
$$ r_n=p_{i_1}+p_{i_2}+…+p_{i_k}$$

对于$r_n\ge 1$,我们可以用更短的钢条的最优切割收益来描述:
$$r_n=max(p_n,r_1+r_{n-1},r_2+r_{n-2},…,r_{n-1}+r_1)$$

更简单的,我们将钢条从左边切割下长度为$i$的一段,只对右边剩下的长度为$n-i$的一段继续进行切割(递归求解),对左边的一段则不再进行切割。可以得到$$r_n=max\limits_{1\le i\le n}(p_i+r_{n-i})$$
这样原问题只包含一个相关子问题的解而不是两个。

复杂度

时间复杂度:$\Theta(n^2)$

子问题图



矩阵链乘法

懒得写了。

最优子结构



对子问题的分析发现必须是子问题必须是两头可动的(i.e.一维数组是不够的)

伪代码

为什么原书是分页的我还得手敲一遍不能忍

MATRIX-CHAIN-ORDER(p)    //自底向上的动态规划实现
    n=p.length-1
    let m[1..n,1..n] and s[1..n-1,2..n] be new tables
    for i=1 to n
        m[i,i]=0
    for l=2 to n
        for i=1 to n-l+1
            j=i+l-1
            m[i,j]=\infty
            for k=i to j-1
                q=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
                if q<m[i,j]
                    m[i,j]=q
                    s[i,j]=k
    return m and s

最长公共子序列(LCS)

问题定义

先略

最优子结构




伪代码




最优二叉搜索树

和矩阵链乘法类似

也懒得抄了

一份毫无营养的学习笔记就完成了

CATALOG
  1. 1. 基本原理
    1. 1.1. 最优化问题
    2. 1.2. 算法设计步骤
    3. 1.3. 最优子结构性质
    4. 1.4. 子问题重叠
    5. 1.5. 实现
  2. 2. 钢条切割问题
    1. 2.1. 问题描述
    2. 2.2. 分析
    3. 2.3. 复杂度
    4. 2.4. 子问题图
  3. 3. 矩阵链乘法
    1. 3.1. 最优子结构
    2. 3.2. 伪代码
  4. 4. 最长公共子序列(LCS)
    1. 4.1. 问题定义
    2. 4.2. 最优子结构
    3. 4.3. 伪代码
  5. 5. 最优二叉搜索树