Dynamic Programming 101

Algorithm


本文记录一下自己了解Dynamic Programming的过程, 大部分资源来自科研人员的主页以及Wikipedia

Dynamic Programming 动态规划

动态规划[1]的概念大家应该都有所了解. 我最初知道动态规划的时候是老看到有人在博客中提到DP算法DP算法神马的, 后来才搞清楚这个DP算法就是值得动态规划算法. 比较经典的例子就是背包问题[2],

我们有\(n\)种物品,物品j的重量为\(w_j\),价格为\(p_j\)。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为\(W\)。如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题。

$$ maximize~ \sum_{j=1}^n p_j x_j $$
$$subject~to~ \sum_{j=1}^n w_j x_j \leq W, x_j \in \{0,1\} $$

首先需要注意的是背包问题是一个NP完全问题[3], 也就是说无法有多项式时间内的解法. 但是利用动态规划,背包问题存在一个伪多项式时间算法

算法描述 我们设\(w\)当前可用的重量空间, 前\(i\)种物品的总价格能达到的最高值为\(m(i, w)\). 则有如下关系

  • \(m(0, w) = 0\)
  • \(m(i, 0) = 0\)
  • \(m(i,w) = m(i-1,w)\), if \(w_i > w \)
  • \(m(i,w) = max (m(i-1,w),m(i-1,w-w_i)+v_i\), if \(w_i \leq w \)

通过计算\(m(n,W)\)来求解,这个解法时间空间复杂度都是\(O(nW)\). 如果用一个一维向量\(m[W]\)每次重写, 可以有\(O(W)\)的空间复杂度.

Stochastic Dynamic Programming (SDP)

随机动态规划就是在DP的基础上有一些变化, 在确定的动态规划中, 给定一个状态和决策, 那么下一个状态以及收益就已经是确定的了. 如果这些中有的是概率函数, 那么这个动态规划就是随机动态规划.

Uncertain Payoffs

需要通过计算收入的期望来做决策, 如果使用期望值, 则看起来就是一个确定性的动态规划问题了. 这种情况比较好理解一些. 比如一个店铺卖出产品A一份的概率是60%,40%的概率卖出2份,则卖出期望值是1.4份.

Uncertain States

如果状态是未知的, 也比较有意思. [4]中给出了这么一个例子. 丢四次硬币来赌钱. 每次你可以压$0,$1,$2.假设你以压$1开始,目标是最大化你拥有$5的概率. 在这个问题中你有0.5的概率赢钱. 但是这个硬币的状态你是不知道的.于是就有这么一个在状态i的时候押注$k拥有$x, 也就是说我们有0.5的概率损失到 x-k $. 先看最终状态, 用\(f_i(x)\)来表示我们的目标:第i次抛硬币之前有$x的概率,则

$$ f_i(x) = \max_{k \leq x, k \leq 2} 0.5 f_{i+1} (x+k) + 0.5 f_{i+1} (x-k) $$

约束是 \( f_5(5)=1 f_5(x)=0 \) for \( x \leq 4 \) 我们可以从 \( f_5 \) \( f_4 \) 直到 \( f_1(1) \) 其实这个实际上也是算收益期望.

参考

  1. http://en.wikipedia.org/wiki/Dynamic_programming
  2. http://en.wikipedia.org/wiki/Knapsack_problem
  3. http://en.wikipedia.org/wiki/NP-complete
  4. http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html