Dynamic Programming Algorithmic 动态规划算法

理解动态规划算法的思想；

对相应问题能建立基本的递归关系式并用从底至上的方法来求解，在求解过程中知道如何建立数据储存的表格。

重点掌握的问题：

• 带权重的活动安排问题、
• 0-1背包问题、
• 最长公共子序列问题、
• 矩阵连乘的最优计算次序问题，

典型考题：作业1中第3题。

理解0-1背包问题的动态规划算法不是多项式时间算法。

★Algorithmic paradigms 算法范式

Greed. Build up a solution incrementally, myopically optimizing some local criterion.
贪心：局部最优解，逐步形成最终解。

Divide-and-conquer. Break up a problem into independent subproblems; solve each subproblem; combine solutions to subproblems to form solution to original problem.
分治：将问题分解为独立的子问题；解决每个子问题；组合子问题的解，形成原问题的解。

Dynamic programming. Break up a problem into a series of overlapping subproblems; combine solutions to smaller subproblems to form solution to large subproblem.
动态规划：将问题分解为一系列重叠的子问题；将较小子问题的解组合成较大子问题的解。

Dynamic programming: fancy name for caching intermediate results in a table for later reuse
动态规划：用于在表中缓存中间结果以供以后重用而得名

★问题 > Weighted interval scheduling 带权活动安排

问题描述

• Job j starts at s_j, finishes at f_j, and has weight w_j > 0.
  活动j从s_j开始，在f_j结束，具有正权值w_j > 0
• Two jobs are compatible if they don’t overlap.
  如果两个活动时间不重叠，则两活动兼容
• Goal: find max-weight subset of mutually compatible jobs.
  目标：找到权值最大的相互兼容的活动子集

Earliest-finish-time first algorithm 最早结束时间优先算法

Earliest finish-time first.
最早结束时间优先

• Consider jobs in ascending order of finish time.
  按结束时间对活动排序
• Add job to subset if it is compatible with previously chosen jobs.
  如果与之前选的活动兼容，则将其加入结果集

Recall. Greedy algorithm is correct if all weights are 1.
回忆：当权值都为1时，贪心算法是正确的

Observation. Greedy algorithm fails spectacularly for weighted version.
观察：带权值的版本，贪心算法失效

Weighted interval scheduling 带权活动安排

Convention. Jobs are in ascending order of finish time: f₁ ≤ f₂ ≤ . . . ≤ f_n .
规定：工作按结束时间升序编号

Def. p(j) = largest index i < j such that job i is compatible with j. (i is leftmost interval that ends before j begins)
定义：p(j)是编号小于j的、编号最大的、与j兼容的活动（活动i是在活动j开始之前结束的最右的活动）

Ex. p(8) = 1, p(7) = 3, p(2) = 0.
例如

Dynamic programming: binary choice 动态规划：二路选择

Def. OPT(j) = max weight of any subset of mutually compatible jobs for subproblem consisting only of jobs 1, 2, ..., j.
定义：OPT(j)是前j个活动中相容的活动最大权值

Goal. OPT(n) = max weight of any subset of mutually compatible jobs.
目标：求OPT(n)

Case 1. OPT(j) does not select job j.
情况1：OPT(j)没有选择第j个活动

• Must be an optimal solution to problem consisting of remaining jobs 1, 2, ..., j – 1.
  必然是前j-1个活动中相容的活动最大权值

Case 2. OPT(j) selects job j.
情况1：OPT(j)选择了第j个活动

• Collect profit w_j.
  会获得权值w_j
• Can’t use incompatible jobs { p(j) + 1, p(j) + 2, ..., j – 1 }.
  不能使用不相容活动
• Must include optimal solution to problem consisting of remaining compatible jobs 1, 2, ..., p(j).
  必须包括前p(j)个活动中最优解

Bellman equation. 贝尔曼方程

Brute force 暴力破解

将活动按结束时间递增排序

计算每个活动的p(j)

计算每个活动的OPT(j)

Observation. Recursive algorithm is spectacularly slow because of overlapping subproblems ⇒ exponential-time algorithm.
观察：由于子问题重叠，递归算法非常慢 ⇒ 这是个指数时间算法

Ex. Number of recursive calls for family of “layered” instances grows like Fibonacci sequence.
例如：对“分层”实例的递归调用的数量会像斐波那契序列一样增长。

Memoization 记录

Top-down dynamic programming (memoization).
自上而下的动态编程（记录）

• Cache result of subproblem j in M[j].
  在M[j]中缓存子问题j的结果
• Use M[j] to avoid solving subproblem j more than once.
  使用M[j]避免多次求解子问题j

Running time 运行时间

Claim. Memoized version of algorithm takes O(n log n) time.
断言：记录化版的算法花费O(n log n)时间

Pf. 证明

• Sort by finish time: O(n log n) via mergesort.
  按结束时间排序：归并排序O(n log n)

• Compute p[j] for each j : O(n log n) via binary search.
  计算p[j]：二分查找O(n log n)

• M-COMPUTE-OPT(j): each invocation takes O(1) time and either
  计算M-COMPUTE-OPT(j)：每次调用花费O(1)以及下面二选一

  • (1) returns an initialized value M[j]
    找到已有值

  • (2) initializes M[j] and makes two recursive calls
    没有已有值：再调用2次

• Progress measure Φ = # initialized entries among M[1.. n].
  进度度量Φ：M中已完成的数量

  • initially Φ = 0; throughout Φ ≤ n.
    初始Φ为0，最大为n

  • (2) increases Φ by 1 ⇒ ≤ 2n recursive calls.
    第(2)步每次使Φ+1，总共最多需要2n次调用

• Overall running time of M-COMPUTE-OPT(n) is O(n).
  M-COMPUTE-OPT(n)的整体运行时间是n

Finding a solution 选了哪些活动

Q. DP algorithm computes optimal value. How to find optimal solution?
问：动态规划算法算出了最值，如何找到最优解？

A. Make a second pass by calling FIND-SOLUTION(n).
答：调用FIND-SOLUTION(n)

Running time. The bottom-up version takes O(n log n) time.
运行时间：自底向上版本花费O(n log n)时间

例题

问题 > Maximum Subarray Problem 最大连续子数组问题

Goal. Given an array x of n integer (positive or negative), find a contiguous subarray whose sum is maximum.
目标：给定n个整数（正或负）的数组x，找到一个和最大的连续子数组。

动态规划解法：……

★问题 > Knapsack problem 0-1背包问题

Goal. Pack knapsack so as to maximize total value.
目标：使总体价值最大

• There are n items: item i provides value v_i > 0 and weighs w_i > 0.
  n个物体：每个物体有重量和价值
• Knapsack has weight capacity of W.
  背包有最大重量W

Assumption. All input values are integral.
假设所有值都是整数

Dynamic programming: adding a new variable 动态规划：添加新的变量

Def. OPT(i, w) = max-profit subset of items 1, …, i with weight limit w.
定义：OPT(i, w)是前i个物体中装进最大重量为w的背包中的最大价值

Goal. OPT(n, W).
目标：找到OPT(n, W)

Case 1. OPT(i, w) does not select item i.
情况1：没有选择第i个物体

• OPT(i, w) selects best of { 1, 2, …, i – 1 } using weight limit w.
  其余选择同前i-1个物体中装进最大重量为w的背包中

Case 2. OPT(i, w) selects item i.
情况2：选择了第i个物体

• Collect value v_i.
  获得了价值v_i
• New weight limit = w – w_i.
  最大重量变为为w – w_i
• OPT(i, w) selects best of { 1, 2, …, i – 1 } using this new weight limit.
  其余选择同前i-1个物体中装进最大重量为w – w_i的背包中

Bellman equation. 贝尔曼方程

Bottom-up dynamic programming 自底向上动态规划

Bottom-up dynamic programming demo 示例

例题

再加一个条件

Running time 运行时间

Theorem. The DP algorithm solves the knapsack problem with n items and maximum weight W in Θ(n W) time and Θ(n W) space.
定理：动态规划求解n个物体，最大容量为W的0-1背包问题花费Θ(n W)时间和Θ(n W)空间

Pf.

• Takes O(1) time per table entry.
  每个单元格花费O(1)
• There are Θ(n W) table entries.
  有Θ(n W)个单元格
• After computing optimal values, can trace back to find solution: OPT(i, w) takes item i iff M [i, w] > M [i – 1, w].
  回溯可以找到选了哪些物体：选了i当且仅当则M [i, w] > M [i – 1, w]

运行时间Θ(n W)不是多项式时间

问题输入：

• n个物体（规模为n，即数组长度）
• 最大容量为W（W是一个数，规模为log W，即这个数的位数）

Θ(n W) = Θ(n 2^{log W}) 是指数规模

问题 > Coin changing 找硬币

贪心算法无法找到解，但是动态规划算法……

★问题 > 最长公共子序列

子序列 公共子序列

最长公共子序列的结构

子问题的递归结构

计算最优值

时间复杂度

O(mn)

例题

★问题 > 矩阵连乘的最优计算次序

矩阵连乘问题

给定n个矩阵{A₁, A₂, … , A_n} ， 其中A_i与A_i-1是可乘的，i=1, 2,…,n-1。考察这n个矩阵的连乘积A₁A₂A_n。

由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘。

矩阵乘法基础

对于 p × q 矩阵 A 和 q × r 矩阵 B，A × B 需要多少次乘法计算？p × q × r 次乘法计算

例如: A 和 B 分别是 20 × 100, 100 × 10 矩阵, 则乘法总数为20 × 100 × 10 = 20000

如果 A₁, A₂ 和 A₃ 是 20 × 100, 100 × 10 和 10 × 50 矩阵, A₁ × A₂ × A₃乘积运算次数是多少?

完全加括号的矩阵连乘积

完全加括号的矩阵连乘积可递归地定义为：

• （1）单个矩阵是完全加括号的；
• （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A = (BC)

矩阵连乘问题

穷举法

动态规划

分析最优解的结构

特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

建立递归关系

计算最优值

用动态规划法求最优解

例题

问题 > Segmented least squares 分段最小二乘

Least squares 最小二乘

Segmented least squares 分段最小二乘

Dynamic programming: multiway choice 动态规划：多路选择

Segmented least squares algorithm 分段最小二乘算法

Segmented least squares analysis 分段最小二乘算法分析

问题 > RNA secondary structure

略

问题 > Sequence alignment

略

Dynamic programming summary 动态规划算法总结

Outline 概述

Define a collection of subproblems. 定义子问题集合

Solution to original problem can be computed from subproblems. 原始问题的解可以从子问题中计算出来

Natural ordering of subproblems from “smallest” to “largest” that enables determining a solution to a subproblem from solutions to smaller subproblems. 子问题从“最小”到“最大”的自然排序，能够确定子问题的解决方案，从解决方案到较小的子问题

Techniques 技术

Binary choice: weighted interval scheduling. 二路选择：带权活动安排

Multiway choice: segmented least squares. 多路选择：分段最小平方

Adding a new variable: knapsack problem. 添加一个新变量：背包问题

Intervals: RNA secondary structure. 间隔：RNA二级结构

Top-down vs. bottom-up dynamic programming 自上而下与自下而上的动态规划

Opinions differ. 观点不同