【算法】动态规划
2022-11-03 15:34:55

1.何为动态规划?

书接上文,可以把分治法看作是:把一个问题分成若干个独立的子问题。如果子问题不独立呢?

拿$Fibonacci$数列问题来说,每一个子问题都和其他子问题有关系。这个时候用分治法就不是很合理了,比如说,求解$Fib(5)$就必然要求$Fib(4),Fib(3)$,而求$Fib(4)$还要求一次$Fib(3)$,这就导致,有的子问题要被多次求解,专业点的说法就是子问题重叠

这时候George说了,“那我们不妨从小问题开始求,把结果都记下来,最后一步步求解到原问题吧”。

这就是动态规划:把原始问题划分成若干个子问题,求解每个子问题仅一次,并将其结果保存,以后用到时直接存取,不重复计算,节省计算时间。

什么样的问题适用于动态规划呢?

优化问题:问题可能有很多解,每个可能的解都对应有一个值,这个值通常称为代价。优化问题是要在该问题所有可能的解中找到代价最大/最小的解,即问题的一个优化解(最优解)。

重叠问题:在问题的求解过程中,很多子问题的解将被多次使用。

动态规划求解的步骤大致为:简化原问题-建立递归方程-求解子问题-求解原问题。

2.矩阵乘法链

输入:表达式:$A_1\times A_2\times \cdots\times A_n$,其中$A_i$是$p_{i-1}\times p_i$矩阵。

输出:乘法的最小代价方法,代价为乘法运算次数。

最小代价?代价从哪里来?根据矩阵的乘法原理,$A_{10\times 100}\times B_{100\times 5}\times C_{5\times 50}=(A\times B)\times C=A\times (B\times C)$。对于$(A\times B)\times C$来说,$A\times B$的代价是$10\times 100\times 5=5000$,而产出一个$10\times 5$矩阵,与$C$相乘,代价为$10\times 5\times 50=2500$,相加得$7500$。同理,$A\times(B\times C)$代价为$75000$。

引入概念:

最优子结构:问题最优解由子问题最优解组成。

讨论下图中所有的乘法方案最优性:

设$C[i,j]$为计算$A_i\times A_{i+1}\times\cdots\times A_j$的最小代价,可以作出代价的递归方程:
$$
C[i,j]=min_{i\leq k< j}{C[i,k]+C[k+1,j]+(i-1)kj},i<j\
C[i,j]=0,i=j
$$
递归得到两个括号内的最优乘法方案,合并就是最优乘法方案了。但是:

不难看出有子问题重叠。

那么根据动态规划的思想,计算$C[i,j]$需要计算出每一个$C[a,b],i\leq a\leq j,a\leq b\leq j$,可作出下图:

每个红线上的矩阵链长度相同。从最长的对角线一直求到目标长度。

时间复杂度为$O(n^3)$,空间复杂度为$O(n^2)$。

3.最长公共子序列

输入:$X=(x_1,x_2,x_3,\cdots,x_m),Y=(y_1,y_2,y_3,\cdots,y_n)$

输出:$Z=(z_1,z_2,z_3,\cdots)$为$X,Y$最长的公共子序列。

由此推得,子问题有重叠性:

对于$X,Y$的所有子串,可以列出公共子序列长度方程:
$$
C[i,j] = 0\ \ \ \ ij=0\
C[i,j]=C[i-1,j-1]+1\ \ \ \ i,j>0,x_i=y_j\
C[i,j]=Max(C[i,j-1],C[i-1,j])\ \ \ \ i,j>0,x_i\neq y_j
$$
对于每一个$x_i,y_j$,都依靠上式计算,自底向上求解,即在求$C[i,j]$之前,先求出$C[i-1,j-1],C[i-1,j],C[i,j-1]$,并记录下此时对应的子问题,作出下表:

每一个格子,里面的箭头表示其对应的子问题,比如如果对某个格子来说,$x_i=y_j$,箭头就指向$C[i-1,j-1]$;里面的数字代表公共子序列的长度。

时间复杂度为$O(mn)$,因为要讨论$mn$个元素,而每个元素讨论的时候复杂度是$O(1)$;构造子序列,即查看子序列的具体内容,复杂度是$O(m+n)$,因为可以看作从右下角走到边界。合并起来时间复杂度是$O(mn)$

空间复杂度是$O(mn)$。

4.0-1背包问题

问题概述:给定$n$种物品和一个背包,物品$i$的重量是$w_i$,价值$v_i$, 背包承重为$C$, 问如何选择装入背包的物品,使装入背包中的物品的总价值最大?对于每种物品只能选择完全装入或不装入,一个物品至多装入一次。

抽象成一个问题:

输入:给定$C>0,w_i>0,v_i>0,1\leq i \leq n$

输出:$(x_1,x_2,\cdots,x_n),x_i\in {0,1},Q=\sum_{1\leq i\leq n}w_ix_i\leq C$,求满足条件的最大$Q$。

原问题,记作:$(x_1,x_2,x_3,\cdots,x_n),C$,意思是把$(x_1,x_2,x_3,\cdots,x_n)$装入容量为$C$的背包中,根据是否装第一个物品,可划归成两个子问题:

  1. $(x_2,x_3,\cdots,x_n),C-w_1$
  2. $(x_2,x_3,\cdots,x_n),C$

那么,可以分析出子问题重叠:

作递归方程,设$C[i,j]$是可选物品为$i,i+1,\cdots,n$,背包容量为$j$时的最大价值:
$$
C[i,j]=C[i+1,j],0\leq j \leq w_i\
C[i,j]=Max(C[i+1,j],C[i+1,j-w_i]+v_i),j>w_i
$$
第一个式子的意思是,装不下,只好讨论下一个物品。第二个式子则是讨论装与不装哪个更划算一些。

根据上面的这个表达式,参考最长公共子序列的计算方式,可以求解。

时间复杂度是$O(Cn)$,空间复杂度是$O(Cn)$。