《算法导论》中的动态规划算法分析

本篇以《算法导论》第15章的钢条切割问题为例分析了适合用动态规划算法求解的问题,该算法的核心思想、实现方法、求解步骤。

概述

动态规划和分治方法相似,都是通过组合子问题的解来求解原问题。

对于分治法,它的英文“Divide and Conquer Algorithm”便很好地解释了它的思想,即将原问题分割成子问题各个击破,再将它们的解组合起来求出原问题的解;动态规划算法也大体类似。

区别在于,用分治法解决问题时,原问题分割成的子问题互不相交;但是如果将原问题为子问题后,这些分割后的子问题互相重叠(即不同的子问题有相同的子子问题),而这时仍然采用分治算法,时间复杂度会大大增加。而动态规划的提出就是为了解决这样一类问题,它采用某种手段对每个子子问题只求解一次,从而大大降低了时间复杂度。

特别注意的是,动态规划算法用来求解最优化/最值问题,即这类问题可能有多个解都达到最优值,但是它只能求出 an\ optimal\ solution ,而不是 the\ optimal\ solution

对于适合用动态规划算法解决的最优化问题具备的两个要素动态规划算法对重复子子问题只求解一次的“手段”以及设计一个动态规划算法的步骤我们将稍后提出。

适合用动态规划算法解决的最优化问题具备的两个要素

适合用动态规划算法解决的最优化问题必须具备的两个要素是最优子结构和重叠子问题。

最优子结构

当解决一个问题时,如果该问题的最优解包含其子问题的最优解,我们就称此问题满足最优子结构

具体的,我们使用如下范式判断一个问题是否满足最优子结构:

  1. 证明问题最优解的第一个组成部分是尝试做出一个选择。这个选择会产生一个或多个待解决的子问题,比如钢条第一次切割位置,矩阵链的第一次划分位置。

  2. 做出该选择后,我们确定这次选择产生的子问题以及如何最好地刻画子问题空间。

  3. 利用“cut-and-paste”反证出该问题本身的最优解其实就是它的子问题的最优解。

对于不同的问题,最优子结构的不同体现在两个方面:

  1. 原问题的最优解中涉及多少个子问题。比如在钢条切割问题中第一次选择后只产生一个子问题,而矩阵链乘法选择一次后会产生两个子问题。

  2. 在确定最优解使用哪些子问题时,我们需要考察多少种选择。

特别的,在使用动态规划算法时要尤其注意问题是否具有最优子结构的性质。比如无权最短路径的求解是符合最优子问题的性质的,但是无权最长路径的求解不满足最优子问题的性质。原因在于,最长路径子问题是相关的,原问题的一个子问题会影响到另一个子问题的解。而若想满足最优子结构,子问题之间必须相互独立。

重叠子问题

如果递归算法求解相同的子问题,我们就称为最优化问题具有重叠子问题性质。

最熟悉的一个例子是斐波那契序列最简单的递归实现,这种方法的运行时间是n的指数级别,原因随着递归的深入,重复出现的子问题导致工作量爆炸性地增长,这种情况体现在钢条切割问题的递归树中如图所示。

img

而如何解决这种问题,我们接下来提出。

动态规划算法的实现

动态规划算法的本质依然是“穷举”,但它是“有记忆”的穷举,有如下两种方式。

带备忘的自顶向下法

此方法仍然用自上而下的递归方法实现,但是过程种会保存每个子问题的解。当进入一个子问题的求解过程时,首先检查这个子问题的解是否已经计算过。如果是,则直接使用;如果不是,则递归计算。

自底向上法

这种方法中,当我们求解某个子问题时,它需要用到的更小的子问题都已经求解完毕,直接调用就可以了。

两种方法的比较

接下来以钢条切割为例展示最普通的递归调用和以上两种方法的伪代码。

不带备忘的最简单递归:

CUT-ROD(p, n)   //p是每种长度钢条的单价, n表示该问题求长度为n的钢条切割后的最大收益
    if n == 0
        return 0
    q = -∞
    for i = 1 to n
        q = max(q, p[i] + CUT-ROD(p, n-i))
    return q

带备忘的自顶向下法:

MEMOIZED-CUT-ROD(p, n)  //p是每种长度钢条的单价, n表示该问题求长度为n的钢条切割后的最大收益
    let r[0...n] be a new array
    for i = 0 to n
        r[i] = -∞   //初始化为-∞,表示初始时每种长度的钢条都不知道如何切割才能得到最大收益

MEMOIZED-CUT-ROD-AUX(p, n, r)
    if r[n] >= 0 //当前长度下的最大收益已知
        return r[n]
    if n == 0   //当前长度下的最大收益未知,则求出最大长度并保存
        q = 0
    else q == -∞
        for i = 1 to n
            q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))
    r[n] = q
    return q

自底向上法:

BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] be a new array
    r[0] = 0
    for j = 1 to n
        q = -∞
        for i = 1 to j
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

对比两种实现的设计思想:带备忘的递归直接从大规模问题出发,遍历了第一次的选择情况,然后递归的进入子问题的求解;自底向上法从小规模问题出发,遍历每个小规模问题的可能选择情况,最终得到大规模问题的求解。相同点在于二者均开辟空间保留小问题的最优解,这也是动态规划的核心思想。

分析两种实现的时空代价:一般来说,如果每个问题都必须至少求解一次,自底向上动态规划算法会比带备忘的递归算法快一个时间常数,因为自底向上算法没有递归调用的开销,表的维护开销也更小(目前我还不太理解“表的维护开销也更小”这一点);而且对于某些问题,我们可以利用表的访问模式进一步降低时空代价(比如背包问题)。相反,如果子问题空间中的某些子问题不必求解,备忘方法就会体现出优势了,因为他只会求解那些绝对必要的子问题。(本段英文版见文末注记)

解的重构和优化

我们已经经历了动态规划算法的核心,但是不难发现,我们之前的操作只是返回了最优解的收益值,并未返回解本身。为此,我们扩展动态规划算法,再次开辟空间,使之不仅保存每个子问题的最优收益值,还保存对应的切割方案。

代码如下:

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] and s[0...n] be  new arrays
    r[0] = 0
    for j = 1 to n
        q = -∞
        for i = 1 to j
            if q < p[i] + r[j-i]
                q = p[i] + r[j-i]
                s[j] = i
        r[j] = q
    return r[n]

由函数名也可以看出来该函数是BOTTOM-UP-CUT-ROD(p, n)的扩展,区别只在于第一行创建了数组s,并在max函数中增加了一行s[j] = i,表示长度为j的钢条获得最大收益时需要在i处割一刀。

最后输出接解决方案:

PRINT-CUT-ROD-SOLUTION(p, n)
    r, s = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    while n > 0
        print s[n]
        n = n - s[n]

动态规划的核心已经介绍完了。但是在某些动态规划问题中,可能还会涉及空间复杂度的优化。比如斐波那契数列由于当前状态只和前两种状态有关,所以只需存储前两个状态即可,即时间复杂度可以优化为O(n);再比如基本的背包问题中可以将二维的数组优化为一维等等。

设计一个动态规划算法的步骤

看完代码之后,我们可以抽象出设计一个动态规划算法的步骤。

  1. 刻画一个最优解的结构特征。在分析最优子结构的时候这一步其实已经完成了。

  2. 递归地定义最优解的值。即写出状态转移方程。

  3. 计算最优解的值,通常采用自底向上的办法。即设计代码。

  4. 利用计算出的信息构造一个最优解。即重构解。

注记

关于时空开销对比的英文原版:

In general practice, if all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms the corresponding top-down memoized algorithm by a constant factor, because the bottom-up algorithm has no overhead for recursion and less overhead for maintaining the table. Moreover, for some problems we can exploit the regular pattern of table accesses in the dynamicprogramming algorithm to reduce time or space requirements even further. Alternatively, if some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required.

引用:

  1. 《算法导论》第15章 动态规划

  2. 文中图片摘自CSDN中的一篇博客

发表评论

电子邮件地址不会被公开。 必填项已用*标注