6. Dynamic Programming

6. Dynamic Programming

动态规划是一种功能十分强大的计算模式,其解决问题的方式是首先定义它的一组子问题,然后按照由小到大,以小问题的解答支持大问题求解的模式,一次求解所有的子问题。

I. Recursion without repetition

II. Generalize the problem to a family of subproblems:
a) Subproblems quickly formed
b) Solution to subproblems can be computed from solution to smaller      subproblems
c)Number of subproblems is small

Shortest path in DAGs

DAG 的特点是可以被线性化,即所有节点可以排列在一条直线上。考虑源点S到点D的距离,到达D的仅有方式是通过其前驱B或C,因此S到D的最短路径为: $$dist(D)=min\{dist(B)+1,dist(C)+3\}$$

按照此方法,一遍即可算出所有距离值:

 

最长递归子序列

Find the increasing subsequence of greatest length, e.g :

由于对于建立的每条边 \((i, j)\), 有 \(i < j\), 所以图 \(G = (V,E)\) 是DAG,最长子序列等同于DAG中的最长路径

 

最坏情况为序列已经排序好,复杂度为\(O(n^{2})\).

要得到最长子序列本身,而非它的长度:在计算L(j)的的同时,将pre(j)也记录下来

背包问题

在一次打劫中,盗贼发现他的战利品太多,以至于无法全部带走,于是他必须决定将哪些放入自己的背包。假设背包最多能装\(W\)磅。一共有n件物品,分别重\(w_{1}..w_{n}\),价值\(v_{1}..v_{n}\),怎样的组合才会使总价值最高?

(1) Knapsack with repetition

定义 \(K(w)\)为容量w可以容纳的最高价值,如果 \(K(w)\)的最优解中包含了物品 i,将其从背包中移走,则会留下\(K(w-w_{i})\)的最优解。换句话说,对于某些 i ,\(K(w)= K(w-w_{i})+v_{i}\),我们并不知道究竟是哪些i,因此要尝试所有的可能 \(K(w)=max\{K(w-w_{i})+v_{i}\}\ (i: w_{i}<w)\)。

这个算法从左至右填写一个长度为\(W+1\)的表格,填写每个表格的时间为\(O(n)\),于是总复杂度为\(O(nW)\)

(2) Knapsack without repetition

定义 \(K(w,j)(0\geq j \geq n)\)为基于背包容量w和物品\(1..j\)的最高价值,目标求解\(k(W,n)\)。如何将\(k(w,j)\)用更小的子问题表示呢:要么选择物品j以获得最高价值,要么不需要:\(k(w,j)=max\{k(w-w_{i},j-1)+v_{i},k(w,j-1)\}\)

算法填写一个二维的表格,其中有\(W+1\)行和\(n+1\)列,由于填写每个单元格仅需常数时间,因此复杂度为\(O(nW)\)

矩阵链式相乘

假设我们要求四个矩阵的乘积\(A\times B\times C\times D\),其中每个矩阵的维度为\(50\times 20,20\times 1,1\times 10,10\times 100\)。矩阵的乘法不满足交换率但满足结合律,在公式的不同位置加上括号可以得到不同的计算方式,那种为最优?

一个\(m\times n\)的矩阵和\(n\times p\)的矩阵相乘,约要进行\(m\times n\times p\)次乘法

定义\(C(i,j)\)为计算 \(A_{i}\times A_{i+1}\times … \times A_{j}\)的最少代价,考虑将乘积分成两个片段\(A_{i}\times ..\times A_{k}\)和\(A_{k+1}\times ..\times A_{j}\),这样一来总代价为两个片段的代价加上将它们组合到一起的代价,即\(C(i,k)+C(k+1,j)+m_{i-1}m_{k}m_{j}\)。我们需要做的就是找的相应的分割点k,使得以下的值最小:$$C(i,j)=min\{C(i,k)+C(k+1,j)+m_{i-1}m_{k}m_{j}\}(i\leq k < j)$$