Dynamic Programming (NPTEL)

08 Mar 2014 Comments

NPTEL 讲的 Dynamic Programming 是我听过讲的最好的，给人一种看穿本质的感觉，这篇笔记对视频所讲内容做个总结。

DP 过程

视频里给出的用 DP 解决问题的过程包含以下 3 个步骤：

  1. 将问题描述为一个搜索问题，定义问题的 search space 和 objective function。比如对于 Longest Common Subsequence 问题，search space 就是所有的 common subsequence，objective function 是 longest。

  2. 给出解决这个问题的 recursive process。实现方法是将 search space 分割成若干个 subspace，然后在每个 subspace 中递归搜索，伪代码如下。

     Search(S):
   divide S into S[1], S[2], ... S[N]
   for i in [1, N]:
     best[i] = Search(S[i])
   return best of best[1, N]

  3. 将 recursive process 转化成 non-recursive process。这是通过观察每个 recursive call 的 argument 并将每个 recursive call 转换成查表操作实现。当然在查表之前，我们得先填表，在填表的每一项时，我们都假设填这一项依赖的其他项都已经填上 (这个假设如果不成立，就没法 DP 了)。

经过上述步骤就完成整个 DP 过程，最终的 non-recursive process 的 running time = O(table size * time to fill each entry)，recursive process 的 running time 通常是 exponential 的，所以 DP 让不可能变成可能。

下面 3 个小节中给出 3 个具体的例子。

Longest Common Subsequence (LCS)

问题描述

给定两个字符串 A 和 B，找出这两个字符串的最长公共子串 C。

套用上述步骤，解决过程如下。

定义问题

search space all common subsequence between A and B
objective function longest subsequence

Recursive Process

将 S 分成两个两部分。

S[1] common subsequences starting with A[1]
S[2] common subsequences not starting with A[1]

根据这种空间划分法，可以定义如下 recursive process：

LCS(A[1:M], B[1:N]): 
    if A == null or B == null: 
        return null 
     
    /* search S1 */
    cs1 = null 
    k = first index of A[1] in B 
    if k != null: 
        cs1 = A[1] | LCS(A[2:M], B[k+1, N]) 
     
    /* search S2 */
    cs2 = LCS(A[2:M], B[1:N]) 
     
    return longer of (cs1, cs2)

其实函数的 signature 写成 LCS(A[i:M], B[j:N]) 是更准确的，之所以写成 LCS(A[1:M], B[1:N]) 其实是故意的，是为了传递这么一个信息，就是 无论你从其他函数调用 LCS，还是在 LCS 内部递归调用 LCS，你都应该把 LCS 的参数看成是它自身的一个完整的整体，而不是原始 A 或者 B 的一部分 。从物理上讲，递归调用的 LCS 的参数确实是最开始调用的 LCS 参数的一部分，但是，逻辑上，你应该把它单独看成自身的一个整体，这种对输入参数的看法对于你想象递归过程是有好处的。(看完这 3 个例子会更明白这个意思)。

Non-recursive Process

观察上面 recursive call 的 argument，它包含这么几个信息：

  1. A
  2. B
  3. A 的开始位置
  4. A 的结束位置
  5. B 的开始位置
  6. B 的结束位置

其中每次调用发生变化的有两个：A 的开始位置和 B 的开始位置。

由此我们可以定义一个二维表 T：

其中 M+1, N+1 对应 A = null 和 B = null 的情况。

填表操作可以用如下代码表示：

Fill (i, j): 
    if i == M + 1 or j == N + 1: 
        return 

    /* search S1 */
    cs1 = null 
    k = first index of A[i] in B[j:N] 
    if k != null: 
        cs1 = A[1] | T[i+1, k+1] 

    /* search S2 */
    cs2 = T[i+1, j] 

    T[i, j] = longer of (cs1, cs2)

在填 T[i, j] 时，我们假设 T[i+1, k+1], T[i+1, j] 已经填上。为了保证这个假设在整个过程中都成立，我们必须按一定的顺序调用 Fill 函数，从上面的代码可以看出 T[i, j] 依赖项的索引中第一维都大于 i，第二维都大于 j，这样我们只要按 i, j 从大到小遍历即可，如下代码所示。

LCS(A[1:M], B[1:N]): 
    for i in [1, M+1]: 
        T[i][N+1] = null 
    for j in [1, N+1]: 
        T[M+1][j] = null 
     
    for i in [M, 1]: 
        for j in [N, 1]: 
            Fill(i, j) 
     
    return T[1, 1]

到此就完成了 recursion 到 non-recursion 的转换。也就实现了用 DP 解决 LCS 的想法。视频中给出了一个性能更好的 Fill 函数，这里就不给出了。

Knapsack

问题描述

给定 W[1:N], V[1:N]，其中 W[i] 表示第 i 个 object 的 weight，V[i] 表示第 i 个 object 的 value。再给定 C，C 表示 knapsack 的容量限制，问题是要最大化装入 knapsack 的 object 的 value 总和。

定义问题

search space all possible object combinations, which are of size $2^N$
objective function maximum value of object combination, under the constrain that the weight <= C

Recursive Process

将 S 分成两个两部分。

S[1] combinations not containing the first object
S[2] combinations containing the first object

Recursive process 可以表示为：

/* @i denotes the index of first object */
KS(W[1:N], V[1:N], N, C, i): 
    if C <= 0 || i > N: 
        return 0 
     
    /* search S1 */
    v1 = KS(W, V, N, C, i+1) 
     
    /* search S2 */
    v2 = 0 
    if W[i] <= C: 
        v2 = V[i] + KS(W, V, N, C-W[i], i+1) 
     
    return max(v1, v2)

Non-recursive Process

观察上面 recursive call 的 argument，它包含这么几个信息：

  1. W: weight array
  2. V: value array
  3. N: number of objects
  4. C: total capacity
  5. i: index of first object

其中变化的有两个：C 和 i。

由此我们可以定义一个二维表 T：

填表操作可以用如下代码表示：

Fill(W, V, c, i): 
    if c <= 0 || i > N: 
        T[c][i] = 0 
        return 

    v1 = T[c][i+1] 
    v2 = 0 
    if W[i] <= c: 
        v2 = V[i] + T[c-W[i]][i+1] 

    T[c][i] = max(v1, v2)

同样在写上面的 Fill 函数时，我们假设某些项已经被填上。项之间的依赖关系可以由下图表示，其中曲线箭头表示依赖关系。

根据项与项之间的依赖关系，我们应该按 i 从大到小，C 从小到大的顺序调用 Fill 函数。

KS(W, V, C, N): 
    for c = 0 to C: 
        T[c][N+1] = 0 
    for i = 1 to N+1: 
        T[0][i] = 0 
     
    for i = N to 1: 
        for c = 1 to C: 
            T[c][i] = Fill(W, V, c, i)

Matrix Multiplication

问题描述

给定 N 个 matrix，每个 matrix 的维度在 d[0:N] 数组中给出，其中第 i 个 matrix 的维度为 (d[i-1], d[i])，问题是要得到 N 个 matrix 相乘的代价最小的乘法。

定义问题

search space all possible ways of matrix multiplication
objective function minimum multiplication cost

Recursive Process

按最后一次乘积发生的位置来分割 search space，这样共有 N-1 个 subspace。

| S[i] | subspace in which the last multiplication happens between the ith matrix and the (i+1)th one | |:–|:–|

Recursive process 可以表示为：

MM(d[0:N]): 
    if N == 1: 
        return 0 

    m = INF 
    for i = 1 to N-1: 
        c = MM(d[0:i]) + MM(d[i:N]) + d[0]*d[i]*d[N] 
        if c < m: 
            m = c 
    return m

Non-recursive Process

观察上面 recursive call 的 argument，它包含这么几个信息：

  1. d
  2. d 的开始位置
  3. d 的结束位置

其中变化的有两个：d 的开始位置和结束位置。

由此我们可以定义一个二维表 T：

填表操作可以用如下代码表示：

Fill(d[0:N], i, j): 
    if j - i == 1: 
        T[i][j] = 0 

    m = INF 
    for k = i + 1 to j - 1: 
        c = T[i:k] + T[k:j] + d[i]*d[k]*d[j] 
        if c < m: 
            m = c 

    T[i][j] = m

T[i][j]与表中其他项得依赖关系如下图所示。

其中蓝色的框表示 T[i][j]，它依赖于绿色部分的项，另外注意到这个表是 half-full 的，对角线的下方是不需要的。这样调用 Fill 函数的过程如下面伪代码所示：

MM(d[0:N]): 
    fori = 0 to N-1: 
        T[i][i+1] = 0 
     
    for i = N-2 to 0: 
        for j = i+2 to N: 
            Fill(d, i, j) 
     
    return T[0][N]

心得

  1. 在第二步设计递归函数时将所有输入都作为函数参数，然后再看其中变化的是什么。

  2. 把表项之间的依赖关系用图画出来，同时也可以把 Fill 调用中 i，j 的变化用图画出来，这样一切都会变得清晰起来。

  3. 项之间的依赖不能是随意的，T[i, j] 依赖项的两个下标至少得有一维是只往一个方向发展的。

在学会上述招数之后， 你会发现以前觉得复杂的 DP 问题原来都是这么的简单。

UVA 做题感想