算法笔记之动态规划
久违了各位,自数据结构的学习告一段落之后,接下来登场的是——算法!
让我们直接从动态规划开始吧!
ps:为什么出场就是王炸……
pps:因为分治和递归在数据结构部分都有提及,也许后续会再补充吧……
什么是动态规划?
小故事
在进入枯燥无味(误)的正文前,我们先通过一个小故事来理解动态规划。
假如你有三种面值的钞票:1、5、10。我们要如何用最少的钞票凑出面值为15的金额呢?
第一种想法是,既然要求用最少的钞票,那我每次选择面值最大的钞票不就好了?如果剩余金额要小于最大面值,那么就选择第二大的面值。这样,每次都把累加的金额设置的尽可能大,就可以达到减少钞票数量的目的。比如在这个例子中,我们可以依次选择面值为10和5的钞票,就成功用最少数量的钞票凑出了要求金额。
这种思想就是贪心法,即通过每一步都选择局部最优解的情况来达成整体最优。就比如往瓶子里装尽可能多的东西,先装体积比较大的石头,再装体积小的砂石,最后还可以往瓶子里注水。贪心法也是一种非常重要的算法思想,后续我们也会专门开文章来讲解。但是,在这一个例子的情况下,使用贪心法真的就是最优解了吗?
显然不是。假如一个奇葩国家的面值金额只有1、5、11,那我们再去凑出15时使用贪心算法就会出错。具体情况如下:
- 贪心算法:11*1+1*4,一共5张
- 最优解:5*3,一共3张
为什么会出现这种矛盾呢?因为贪心法很重要的一个缺点就是容易鼠目寸光。在有些情况下,局部最优并不一定指向全局最优。
我们把问题抽象成“需要凑出一个具体的金额w,需要用到尽可能少的钞票”。那么贪心法的策略就是让你还需要凑出的w尽快的变得小。很显然,“让w尽快变的小”并不意味着最终的开销一定是最小的。
如果用暴力枚举w的方式呢?这个选择就太多了,所带来的时间复杂度是不可接受的。
那么,接下来该怎么办呢?
我们把“凑出n所需要的最小钞票数量”用f(n)表示。
那么,如果我们取了11,最后的代价(用掉的钞票总数)是多少呢?
明显
,它的意义是:利用11来凑出15,付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
依次类推,马上可以知道:如果我们用5来凑出15,cost就是
也就是说,在做出决策,我们只需要在方案中,选择cost值最低的那个就行了。而用于表达cost的式子也很简单:
也就是说,我们要求出f(n),只需要求出几个更小的f值就行了;那么,我们可以从小到大把所有的f值都求出来,并储存在表中,就可以求出f(n)时的情况了。
我们成功以O(n)的时间复杂度解决了这个问题,接下来我们再来分析一下这道个式子的原理:
- f(n)只与f(n-1)、f(n-5)、f(n-11)的值相关。
- 我们只关心f(w)的值,并不关心它是怎么求出来的。
这就是这个方法的优势所在。相对于贪心法,它会分别计算出各个决策的代价,并选择最小的那一个,而不是一昧的选择局部最优的决策。相对于暴力枚举法,它会舍弃枚举使用的硬币,因为这属于冗余信息,我们只关心f(w)的值,而不需要知道它是怎么凑出来的。
我们能这样干,取决于问题的性质:求出f(n),只需要知道几个更小的f©。我们将求解f©称作求解f(n)的“子问题”。
这就是动态规划,它的核心思想就是:将一个问题拆成几个子问题,分别求解并记录这些子问题,即可推断出大问题的解。
正文
动态规划的工作原理与**记忆(memorization)**相关。动态规划与分治法之间的主要区别在于,后者要求子问题是相互独立的,而在DP中允许存在子问题的重叠。通过使用记忆(维护一张存储已求解子问题的解的表格),动态规划将求解许多问题的指数复杂度降低到多项式复杂度(O(n2)、O(n3)等)。DP的主要组成部分是:
- 递归:递归的求解子问题
- 记忆:在表中存储已经求解的子问题的解(memorization代表缓存)
动态规划和简单递归的区别就在于递归调用的记忆,也就是能够储存每一个子决策的最优解。但是,如果子问题之间相互独立、没有重复,那么储存子决策的解就没有任何帮助。所以,动态规划并不是万能的,它有自己的局限性和要求。要判断一个问题是否满足动态规划的使用条件,可以参考以下两个概念:
无后效性
如果给定某一个阶段的状态,那么这一个阶段以后的发展就与这个阶段之前的发展无关。“未来与过去无关”,这就是无后效性。
参考之前的小故事,只要我们确定了f(n),那么“我们如何凑出f(n)”就再也用不着了。
最优子结构
大问题的最优解能够由小问题的最优解推出,这就叫最优子结构。
参考前面的小故事,我们定义的f(n)是“凑出某个w所需要的最少钞票数量”。这个定义已经包含了“最优”的意思。于是我们分别利用w=14,10,4的最优解,来推算出w=15时的最优解。
因此,要判断问题是否能用DP解决,我们只需要分析问题是否满足以下条件:
- 能将大问题拆分成几个小问题
- 满足无后效性
- 满足最优子结构
动态规划的方法
一般来说,有两种动态规划的方法:
- 自底向上的动态规划
- 自顶向下的动态规划
自底向上
在这种方法中,状态转移方程从最小可能的输入参数值开始,然后逐步通过可能的值,慢慢增加输入参数值。在计算时,我们将所有计算得到的值存储在一个表(内存)中在求解较大输入参数值的状态转移方程时,我们可以使用输入参数值较小时状态转移方程得到的解。
比如背包问题,就适用于自底向上方法。可以从0开始遍历到背包容量,将结果储存在表中。
自顶向下
在这种方法中,问题被分解为多个子问题;求解每个子问题并记住它们的解,以避免再次求解它们时的重复计算。此外,我们将保存每个计算值作为递归函数的最终操作并将判断预计算的值是否已存在作为递归函数的第一个操作。
具体选择哪种方法,应该根据具体环境来决定。在自底向上的动态规划中,程序员必须选择值来计算并决定计算顺序。在这种情况下,所有可能的子问题都被事先求解,然后用于求解更大的问题。在自顶向下的动态规划中,保留了原问题的递归结构,避免了求解不必要的子问题,同时也避免了需要求解的子问题中重复子问题的重复求解。原问题被分解为子问题,求解这些子问题并存储它们的解,以避免它们的重复求解。
具体的动态规划法多种多样,但都具有相同的填表形式。
一般来说,动态规划法的求解过程由以下三个阶段组成:
划分子问题:将原问题分解为若干个子问题,每个子问题对应一个决策阶段,并且子问题之间具有重叠关系。
确定动态规划函数:根据子问题之间的重叠关系找到子问题满足的递推关系式即动态规划函数,这是动态规划法的关键。一般来说,可以表示为问题解的代价=子问题的代价+选择带来的开销。
填写表格:设计表格,以自底向上或自顶向下的方式计算各个子问题的解并填表,实现动态规划过程。
上述动态规划过程可以求得问题的最优值即目标函数的极值,如果要求出具体的最优解,通常在动态规划过程中记录必要的信息,再根据最优决策序列构造最优解。
动态规划算法举例
DAG最短路
问题很简单:给定一个城市的地图,所有的道路都是单行道,而且不会构成环。每条道路都有过路费,问从S点到T点花费的最少费用。
有向无环图的最短路径问题是一个经典的问题,它的解法是拓扑排序的一个应用。
它满足无后效性和最优子结构性质,可以用动态规划的方法解决。
既然满足动态规划性质,则可以确定关系式f(P)=min{f®+W(R,P)},其中R是P的前驱结点,W(R,P)是边R->P的权值。
有向无环图的最短路径问题的算法如下:
- 对有向无环图进行拓扑排序,得到拓扑序列。
- 初始化源点的最短路径长度为0,其他点的最短路径长度为无穷大。
- 依次对拓扑序列中的每个点P进行如下操作:如果f(P)+W(P,R)<f®,则f®=f(P)+W(P,R)。
- 最后返回终点到起点的距离f(n)。
这里我整理出了一份C++代码仅供参考,不过需要注意的是我并没有采用传统的方式开表来保存最优解,而是选择用维护distance属性来代替开表,其底层的核心思路是一样的。其实,只要有诸如f(R)=f(P)+W(P,R)
的式子来判断并储存最优解,都可视为借鉴了动态规划的思想。如果要用更加熟悉传统的动态规划算法解决最短路问题,可以参考Floyd算法_百度百科 (baidu.com)。
代码如下。
/* |
想说的话
其实这点内容远不足以学习到动态规划的精髓,但由于时间关系,我目前只写了这么多。其实对于算法的学习而言,多刷题永远是最有效的方法。多实践,把抽象的思想转化为具体的solution,从而对算法的思想有更深入的了解,避免纸上谈兵。
目前只更新了DAG最短路问题,其实涉及到动态规划算法的经典问题还有很多,诸如矩阵连乘、最长公共子序列等问题我都还没来得及更新,希望日后刷题时会补上才不会鸽了呢。