动态规划 #

动态规划(Dynamic programming, 简称DP) 是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的, 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法. 在解决多阶段决策优化问题时, 动态规划是一种常见的方法.

本文主要介绍运筹学中的动态规划的一些例子.

最短路问题 #

给定起点和终点, 每天都能通过一些城市进行中转, 找出一条最短的路径.

假设:

• 阶段 $0$ 为起点
• 阶段 $1\leq n\leq N$ 的城市集合为 $S_n$
• 阶段 $N + 1$ 为终点
• $a_{i, j}^n$ 为阶段 $n$ 从城市 $i\in S_n$ 出发到达城市 $j\in S_{n + 1}$ 的路程; 如果不存在路径, 则记距离为 $+∞$ .

定义 $J_n(i)$ 为第 $n$ 天从 $i$ 城市出发, 到达终点的最短路径. 有:

• $J_N(i) = a_{i, t}^N$ , $i\in S_{N}$
• $J_n(i) = \underset{j\in S_{n + 1}}{min}[a_{i, j}^n + J_{n + 1}(j)]$ , $i\in S_n, 0\leq n\leq N$

最长公共子序列 #

有序列 $X$ 和序列 $Y$ , 计算它们的最长公共子序列.

记 $LCS(X[1…m], Y[1…n])$ 为 $X$ 前 $m$ 位和 $Y$ 前 $n$ 位的最长公共子序列. 有: $$ LCS(X[1…m], Y[1…n])=\begin{cases} 1 + LCS(X[1…m - 1], Y[1…n - 1])\ max(LCS(X[1…m - 1], Y[1…n]), LCS(X[1…m], Y[1…n - 1])) \end{cases} $$

旅行商问题 #

给定完全图 $G=(V, E)$ , 寻找从源点 $S$ 出发经过每个城市一次且最终回到 $S$ 的最短路径.

设:

• 阶段 $0$ 为起点 $S$
• 阶段 $1\leq n<\vert V\vert$ 为已访问的节点序列
• 阶段 $\vert V\vert$ 为 $S'$
• $c_{i, j}$ 为城市 $i$ 与城市 $j$ 之间的距离

记 $J_n(X)$ 为阶段 $n$ 从节点序列 $X$ 的末尾城市 $i$ 出发到达 $S’$ 的最短路径. 有:

• $J_{\vert V\vert}(S’) = 0$
• $J_{n}(X) =\underset{Y=(X, j), j\not\in X}{min}[c_{i, j} + J_{n + 1}(Y)]$

矩阵链乘法 #

有 $n$ 个矩阵连乘, 计算最少的乘法次数. (假设矩阵相乘使用最朴素的做法, $a\times b$ 的矩阵与 $b\times c$ 的矩阵相乘需要 $a\times b\times c$ 次乘法. )

记 $f(A_i…A_j)$ 为矩阵序列 $A_i…A_j$ 相乘需要的最少乘法次数, $c(X, Y)$ 为矩阵序列 $X$ 的计算结果与 $Y$ 的计算结果相乘需要的乘法次数. 有:

• $f(A_i) = 0, \forall 1\leq i\leq n$
• $f(A_i…A_j)=\underset{i\leq k< j}{min}[f(A_i…A_k) + f(A_{k + 1}…A_j) + c(A_i…A_k, A_{k + 1}…A_j)]$

资源分配问题 #

现有 $w$ 的初始资金, 同时有 $m$ 种投资项目, 向项目 $t$ 投入 $x_t$ 资金后会得到 $r_t(x_t)$ 的收入. 求能够得到的最大收入.

记 $f_t(d_t)$ 为初始资金为 $d_t$ , 投资项目 $t, …, m$ 的最大收入. 有:

• $f_{m + 1}(d_t) = 0, \forall d_t\geq 0$
• $f_t(d_t) = \underset{0\leq x_t\leq d_t}{max}[r_t(x_t) + f_{t + 1}(d_t - x_t))], 1\leq t\leq m$

最优停止问题 #

一个人想要在 $N$ 个阶段内出售一件物品, 在阶段 $1, 2, …, N$ , 他分别会收到 $w_1, w_2, …, w_N$ 的报价, $w_i\ i.i.d$ 且服从 $U[0, 1]$ . 在出售物品之后, 他可以把钱存进银行, 利率为 $r > 0$ . 求 $N$ 阶段可以获得的最大利润.

记 $x_k$ 为阶段 $k$ 的状态, 这里的状态在报价之外还有已接受报价的状态 (记为 $T$) . 其表达式如下:

• $x_k=\begin{cases}T,\ if\ x_{k - 1} = T\ w_k,\ o.w.\end{cases}$

记 $J_k(x_k)$ 为阶段 $k$ 在状态 $x_k$ 时能够得到的最大收入. 有:

• $J_N(x_N) = \begin{cases}0,\ if\ x_N = T\ x_N,\ o.w.\end{cases}$
• $J_k(x_k) = \begin{cases}0,\ if\ x_N = T\ max[(1 + r)^{N-k}x_k, E[J_{k + 1}(w)]],\ o.w.\end{cases}, 1\leq k<N$

记 $a_k=E[\frac{J_{k + 1}(w_{k+ 1})}{(1+r)^{N-k}}]$ , 那么在 $x_k\geq a_k$ 时应当接受报价, 在 $x_k<a_k$ 时应当拒绝报价.

考虑 $J_k(x_k)$ 的现值 $V_k(x_k)$ , 有 $V_k(x_k) = \frac{J_k(x_k)}{(1 + r)^{N-k}}$ , 有递推公式:

• $V_k(x_k) = max[x_k, (1 + r)^{-1}E[V_{k + 1}(w)]]$

可以证明 $V_k(x)\geq V_{k + 1}(x), a_k \geq a_{k + 1}$ , 以及 $a_k =\frac{1}{1+r}\int_{0}^{a_{k + 1}}a_{k+1}dU(w)+\int_{a_{k+1}^{1}}wdU(w)$ .

任务调度问题 #

有 $N$ 个任务, 每个任务需要先经过 $A$ 处理, 再经过 $B$ 处理, 耗时分别为 $a_i$ 和 $b_i$ . $A, B$ 一次最多处理一个任务. 求完成所有的任务所需的最少时间.

定义状态: $k$ 阶段剩余的需要 $A$ 处理的任务集合为 $X_k$ , $B$ 处理完当前任务需要的时间为 $\tau_k$ . 记 $J_k(X_k, \tau_k)$ 为当前状态完成所有任务所需的最少时间. 有:

• $J_k(\emptyset, \tau_k) = \tau_k$
• $J_k(X_k, \tau_k) = \underset{i\in X_k}{min[a_i + J_{k + 1}(X_k-{i}, max[0, \tau_k - a_i] + b_i)]}$