动态规划简介

Posted on In , Views: Waline:

How should I explain dynamic programming to a 4-year-old? ref
1+1+1+1+1+1+1+1 = ?
1+1+1+1+1+1+1+1+1 = ?
Dynamic programming is just a fancy way to say ‘memoizing to save time later’.

动态规划的要点：

  1. 将复杂的问题分解为很多子问题(分治法)
  2. 存储子问题结果避免重复计算(空间换时间)

动态规划问题的特征：

  1. 存在最优的子结构 (Bellman最优化原理ref)
  2. 子问题间存在重叠

前一特征指问题的最优解可由子问题的最优解得到，如最短路径问题，确保分而治之是可行的。后一特征确保空间换时间是可行的，如果子问题间不存在重叠则应考虑贪心算法或普通分治法。最简单的例子是计算Fibonacci数，问题可分解为依次嵌套的子问题，相同子问题不断重复出现；一个反例是最长路径问题，该问题就不存在最优的子结构，全局最优不能由子问题最优解得到(因为子问题最优合并后可能出现不符合要求的环路)。
注：最优子结构不仅取决于问题本身，还与划分子问题的方式相关。

动态规划问题在计算时，可选择自顶向下或自底向上两种方式，分别被称为记忆存储/记忆化(Memoization)和表格填充/列表化(Tabulation)。
以计算Fibonacci数为例

  • 记忆化：由所求项fib(n)向下递归迭代，并通过一个共享变量在递归函数间共享子问题的解，避免重复计算
  • 表格化：由初始项fib(0)、fib(1)向上循环递推建立列表，直至到达所求项数fib(n)，作为列表最后一项返回

普通递归

1
2
3
4
5
6
7
8
9
def fib_rec(n):
    if type(n)==int:
        if n == 0 or n==1:
            return n
        if n>1:
            return fib_rec(n-1) + fib_rec(n-2)
    raise TypeError("input should be non-negative integer")
     
 fib_rec(30)

记忆化递归(自上而下)
记忆化递归相对于普通递归，多了一个共享变量，存储子问题的解，并在递归的函数间传递共享，在计算前首先在表中确认之前未计算过，以避免不必要的重复计算。

1
2
3
4
5
6
7
8
9
10
11
def fib_mem(n, fib):
    if type(n)==int:
        if n == 0 or n==1:
            fib[n] = n
        if fib[n] is None:
            fib[n] = fib_mem(n-1, fib) + fib_mem(n-2, fib)
        return fib[n]
    raise TypeError("input should be non-negative integer")
     
fib = [None]*31
fib_dyn(30, fib)

递推循环(自下而上)

1
2
3
4
5
6
7
8
9
10
11
def fib_tab(n):
    fib = [None]*(n+1)
    if type(n)==int:
        fib[0] = 0
        fib[1] = 1
        for i in range(2, n+1):
            fib[i] = fib[i-1] + fib[i-2]
        return fib[n]
    raise TypeError("input should be non-negative integer")

fib_tab(30)

事实上对于这个问题本身，我们甚至不需要保存整个数列：

1
2
3
4
5
6
7
8
9
10
def fib_iter(n):
    if type(n)==int:
        if n ==0:
            return 0
        prev_fib, curr_fib = 0, 1
        for i in range(1, n):
            curr_fib = prev_fib + curr_fib
            prev_fib = curr_fib - prev_fib
        return curr_fib
    raise TypeError("input should be non-negative integer")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = 30
fib_list = [None]*(N+1)

%timeit fib_rec(N)
565 ms ± 2.53 ms

%timeit fib_mem(N, fib_list)
276 ns ± 1.57 ns

%timeit fib_mem(N, [None]*(N+1))
17.9 µs ± 1.2 µs

%timeit fib_tab(N)
4 µs ± 84.3 ns

%timeit fib_iter(N)
2.19 µs ± 30.5 ns
fib_rec fib_mem fib_tab fib_iter fib_mem(N, [None]*(N+1))
N=100
N=1000

基于动态规划的算法相比普通递归，fib(30)的计算速度直接提升了5~6个数量级，正是由于Fibonacci数列问题中子问题大量重复。如果分析时间复杂度就会发现，普通递归是O(2n)，而通过记忆子问题结果避免重复计算，时间复杂度降为O(n)。

总结：

  • 通常当递归中出现反复求解相同问题的情况时，就该考虑通过存储中间结果优化递归速度，通常可以将时间复杂度由指数级降至多项式量级。
  • 循环递推方法自下而上，直接了当，无需每次计算前确认是否已算过，也没有函数递归调用的额外开销，但列表必须逐个全部填充，不能跳过。
  • 记忆化递归则由上而下，列表只在必要时才进行填充，在某些情况下可跳过不必要的子问题，且对于某些问题相对循环迭代实现起来会更直观。
  • 对Fibonacci数列两者看起来区别不大，因为每步只有一个状态，存储是一维的(列表)，对于一些需二维及以上存储的问题区别会更明显link。
Tabulation Memoization
由前一状态直接得出下一状态 反复递归调用函数，存在额外开销
多数情况状态转移关系相对复杂 状态转移关系简单直观
条件多时，代码将变复杂 代码相对直观明了
由初始项开始逐项递推填表，不能跳过 必要时才填充子项，某些情况可跳过不必要的子问题
根据上述分析，对于全部子问题都必须计算的情况，自上而下的记忆化递归由于函数调用等额外开销，速度会稍慢，Fibonacci数列的计算就属于这种情况。但上述计算中，记忆化递归的速度却比递推快了一个量级，原因有待分析。

fib_tab(N)的速度则会随N增加而逐渐降低；而fib_mem(N, fib_list)的速度却始终为300ns的量级，不随N变化；fib_mem(N, [None]*(N+1))计算速度相对大幅降低，且同样随N增加而降低。原因？？

由于递归存在大量函数调用的开销，传统意义的动态规划通常是指自下而上的递推，但很多情况下递推的通项(状态转移关系)并不直观，因此通常是由最直观的递归开始，到记忆化递归，再最终分析得出递推的通项。
最后，对Python而言，递归深度默认限制为3000层(sys.getrecursionlimit())，超出会报错，而自下而上的递推则不存在该问题。

为什么被称为动态规划？
分治+缓存，上面介绍中完全未提及“动态”或“规划”，为什么称之为动态规划？历史原因！动态规划提出者Richard Bellman在自传中解释说，他当时在一家受雇于空军的公司，而当时的国防部长异常厌恶学术词汇，于是Bellman就造了“动态规划”这么一个听起来高大上，又不会让人产生任何负面联想的名字。“动态”表达的是问题解决是分阶段的(一系列子问题)，后续决策会受之前决策的影响；而“规划”类似线性规划，表示要解决的通常是最优化或决策问题。不过有人指出，Bellman首次使用该术语其实比那个国防部长上任更早，因此上述说法半真半假。而在与其他人的对话中，Bellman曾说这个名字就是在规划前加上“动态”，显得比George B. Dantzig(线性规划之父，当时同为空军工作)所解决的线性规划问题更高大上。
概括起来，之所以叫动态规划就是因为听起来让人感觉很高大上，类似于现在服务器公司都改“云计算”了。动态规划中没什么“动态”的(就是分而治之)，也不一定必须是“规划”问题(如上述Fibonacci数列计算)，而重要的缓存记忆更是丝毫未在名字中体现。或者可以说计算机科学中的动态规划与运筹学/控制论中的动态规划ref是类似但又不同的概念。有观点ref1, ref2认为记忆化(Memoization)是动态规划中最核心的概念，动态规划本质上就是空间换时间，通过缓存加速普通递归/递推，是一种更聪明的递归/递推，相比之下动态规划这个概念本身(对于计算机科学)反倒没太大必要性。
当然也有不认同上述看法的，知乎ref1,ref2上不少高票答案就持另一类观点，认为状态转移才是关键，所谓“动态”规划指的就是随状态转移而动态调整决策。按照这类观点，无论选择递推还是递归，将原始问题拆分为一系列子问题(阶段)处理，每步迭代前后都对应一个包含很多可能选择的状态空间，由当前状态空间到后续状态空间中最优选择的转移关系是一切的关键(与问题的拆分直接相关)。对于具有最优子结构的问题，如果当前最优选择只取决于前一阶段最优选择，可使用贪心算法；如果当前最优选择(直接或间接)依赖之前的所有状态，且具有无后效性状态间存在重叠，则可以考虑动态规划，否则就需借助搜索算法。记忆缓存或空间换时间在这类观点中反而不重要，似乎跟美版知乎(Quora)的高票观点相反。不清楚为什么存在这么大的分歧，只能说提供了一个新的视角，仅供参考。最后，无后效性(Non-aftereffect)，即当前状态不会受其后状态影响，这个概念在中文动态规划介绍中较普遍，但在算法导论和红宝书中并未找到，所能搜到的英文参考相对少，知乎有人指出最优子结构其实已暗含了无后效性。

Memoization v.s. Memorization
Memoization专用于计算机领域，特指缓存中间结果供后续复用，以实现计算加速，是计算机领域中空间换时间最直观的实现方式之一。
Memorization “记住”，比Memoization多了一个r，与memory对应，无特殊含义。

动态规划 v.s. 贪心算法ref
贪心算法与动态规划类似，同样基于分治思想，且同样要求问题存在最优子结构。针对一系列子问题，贪心算法每步都只做出当前的最优选择(贪心的选择)，不会回头审视之前的选择，期望通过一个个局部最优解最终导向全局最优解。相比之下，动态规划的每步决策都依赖于之前的选择，可以选择自顶向下(递归)或自底向上(递推)，但最终都是综合所有子问题的解得出整体的解，并确保决策是全局最优。
总结来说，在状态迭代过程中，动态规划需要计算所有(必要的)状态，同时存储备用；相对的，贪心算法则只选择当前最优的状态，直接忽略其他及过往所有状态。从这个角度看，动态规划是优化了的暴力求解，而之所以能优化的关键在于文章开头提到的“子问题间存在重叠”，这一点保证了我们可以空间换时间。
显然贪心算法只对特定问题有效，很多情况下由一系列局部最优并不能找到全局最优；而对于那些贪心算法确实有效的问题，它通常更快、也更省内存(无需记忆)。