目录

动态规划

动态规划介绍

运筹学中的动态规划

动态规划(Dynamic Programming,简称DP)是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。把多阶段问题变换为一系列相互联系的的单阶段问题,然后逐个加以解决

这里提到动态规划其实是一种数学方法,是求解某类问题的一种方法, 而不是一种特殊的算法,没有一个标准的数学表达式或明确定义的一种规则。

比如我们接触过的”排序算法“,”二叉树遍历算法“等,这些算法都是有固定范式的,遇到此类问题我们只需要照搬算法即可。但动态规划却不是,它告诉你的是解决某类问题的一种思路,或者是一种更高意义上的算法,是一种道,而不是术。所以动态规划难就难在我们即使学会了这种思想,遇到具体问题也需要具体分析,很可能因为我们构造不出动态规划所需要的形式而无法解决,甚至根本想不到这是一个动态规划问题。

如下图。我们在解决某些最优问题时,可将解决问题的过程按照一定次序分为若干个互相联系的阶段(1, 2,…,N),从而将一个大问题化成一系列子问题,然后逐个求解。 https://gitee.com/lienhui68/picStore/raw/master/null/20200702142510.png 在每一个阶段都需要作出决策,从而使整个过程达到最优。各个阶段决策的选取仅依赖当前状态(这里的当前状态指的是当前阶段的输入状态),从而确定输出状态。当各个阶段决策确定后,就组成了一个决策序列,这个决策序列就决定了问题的最终解决方案。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程

前面说到”仅需要依赖当前状态“,指的是问题的历史状态不影响未来的发展,只能通过当前的状态去影响未来,当前的状态是以往历史的一个总结。这个性质称为无后效性(即马尔科夫性)。 上图中,在阶段2时所做出的决策,仅依赖于阶段2的输入状态,与阶段1的输入状态无关。

动态规划定义中提到按照一定次序分成互相联系的子阶段,这里面的关键是互相联系。如果是独立的子问题,那是分治法,分而治之的意思。动态规划将一个大问题化成一族互相联系、同类型的子问题。既然是同类型,我们在逐个解决子问题的时候,就可以利用相同的决策,从而更容易的解决问题。互相联系利用前面已经解决的子问题的最优化结果来依次进行计算接下来的子问题,当最后一个子问题得到最优解时,就是整个问题的最优解。

这里面包括两个关键点:

  1. 每一个阶段可能包括很多状态,前后阶段的状态通过决策联系在一起。如果要利用前阶段子问题的结果解决现阶段的子问题,必须要能够建立前后阶段状态的转移关系,最好可以通过方程表示。用专业术语我们又叫做状态转移方程

  2. 我们在衡量最优解的时候需要有一个指标函数,最优解就是让这个指标函数达到最优值,比如最大或者最小。如果我们可以将问题拆分成子问题,那么这个指标函数也必须具有分离性,也就是必须能够利用子问题的最优递推的求出整体最优

可以看到,上面两个关键点无论是状态转移方程还是指标函数分离,其实都是需要列出递推关系式,如果恰当的选取状态,让每个子问题的状态能够表示出子问题的最优解,那我们就可以用状态转移方程递推求出指标函数的最优解。

动态规划举例

上面的描述如果觉得有些抽象,可以看完下面的栗子再回过头看一遍,可能理解会更加深刻。如下图,要求出从A点到F点的最短路径。我们来分析一下如何用动态规划的思想来解决这个问题。 https://gitee.com/lienhui68/picStore/raw/master/null/20200702143427.png

第一步,我们将这个问题拆分成多阶段子问题,然后选择状态变量,使其满足无后效性。如下图,我们分为3个阶段。阶段1有1个输入状态A,输出状态B, C,阶段1的输出状态就是阶段2的输入状态,所以阶段2有2个输入状态{B, C},阶段3有2个输入状态{D, E},输出状态F。 https://gitee.com/lienhui68/picStore/raw/master/null/20200702145703.png 以状态D为例,从状态D做决策选择最短路径的时候,我们只关心如何从D到F,不关心从前一阶段是从B还是C到达的D,满足无后效性。

第二步,确定决策集合。假设当前处在状态B,此时的允许决策集合就是{D,E},不同的决策会使得状态转移的路径不同,从而影响到下一个状态。当选择决策D时,对应的决策变量$u_2{(B)} = D$。

第三步,确定状态转移方程、分离指标函数。 把从A到F的路径看成一个指标函数,这个指标函数的最小值就是最短路径。我们接着分离指标函数,找到递推关系。

我们用$f_k{(S)}$表示从初始节点到第k阶段节点s的最短路径,当我们这样拆成子问题时,它既是整个问题的最优子结构(因为当k为N时,就是原问题本身),又可以定义成状态。如果我们可以列出状态转移方程,也就可以递推求出最优解。 $f_1(B) = 2, f_1(C) = 4$ 接下来就是如何利用最短路径$f_1$推导出$f_2$ ,从而构造出递推方程。我们有 $f_2(D)=min(f_1(B) + L_{bd}, f_1(C) + L_{cd}) = min(2+2, 4+1) = 4$ 同理有 $f_2(E)=min(f_1(B) + L_{be}, f_1(C) + L_{ce}) = min(2+3, 4+2) = 5$

有了上面这个状态转移方程,我们可以容易的求出 同理有 $f_3(F)=min(f_1(D) + L_{df}, f_2(E) + L_{ef}) = min(4+4, 5+2) = 7$

于是,上述问题的最短路径就是7。

《算法导论》中的动态规划

动态规划的思想最初是由美国数学家贝尔曼在1951提出,前面我们也是从数学的角度去理解动态规划,它背后的思想是最优化定理。

在《算法导论》中也讲到了”动态规划“,我在前面提到,动态规划难就难在它不是一成不变的,是一种更高意义上的算法思想;它不是一种特殊的招式,而是无招胜有招,需要见招拆招

从算法的角度来看,什么时候可以使用动态规范方法解决问题呢?这其中包括了两个要素,分别是”重叠子结构“和”最优子结构“。下面我们就借鉴《算法导论》,从算法的维度再来剖析一遍动态规划,看看和运筹学中的”动态规划“能不能找到什么共性?

重叠子结构 前面我们说动态规划是将一个多阶段问题分成几个相互联系的单阶段问题。而这几个相互联系的单阶段问题一定要是一族同类型的子问题,这样分成多阶段决策才是有意义的,否则我们每次面对的决策都是不同的问题,也就失去了分成单阶段的意义。

在算法上,我们把这种同类型的子问题又叫做”重叠子结构“。重叠不是相同,而是同类型,我们必须得利用前面子结构计算出的结果,用递推不断地调用同一个问题。

所以说,《算法导论》中的重叠子结构其实就是对应了数学中将多阶段问题分成单阶段问题的过程,只不过强调了这个单阶段问题必须是”重叠的“,这样才能够用同一种算法递推地解决问题

最优子结构

大问题的最优解可以由子问题的最优解推出

利用前面已经解决的子问题最优解来构造并解决后面的子问题。能够构造的前提就是要满足指标函数的分离性,也就是全局最优解一定能够拆成子问题的最优解,从而递推解决。

对应到算法中,就是按照自底向上的策略,首先找到子问题的最优解,解决子问题,然后逐步向上找到问题的一个最优解。也就是说,整体问题的最优解包括了子问题的最优解。我们又叫做”最优子结构“。

这么分析来,《算法导论》中的最优子结构其实就是对应了数学中指标函数的分离性。两者只是从不同的维度描述而已。

所以动态规划在数学上和算法上的描述归根到底都是相同的,只是使用数学语言和算法语言的区别。

于是我们按照定义看看如何辨别DP问题。

先来看看必须提到的斐波那契数列,它的递推表达式为 $f(n) = f(n-1) + f(n-2) (n\ge1), f(1) = 1, f(2) = 1$

  • 从数学上来看,这个问题本身不是一个最优化问题,也就是没有一个指标函数去衡量最优值;而且需要依赖当前状态和前一个状态,不满足无后效性。所以从数学上来说它不是一个动态规划问题。

  • 从算法上看,它虽然具有重叠子结构,但本身不是一个最优化问题,没有最优子结构,不是动态规划问题。虽然不满足无后效性,但是依赖有限个状态,同样可以列出状态转移方程。

虽然不是DP问题,但我们也没有必要那么教条,毕竟动态规划是用来一系列比较复杂的最优化问题,当然也可以利用动态规划当中的一些思想去解决类似的问题,因为相对于动态规划问题,斐波那契数列这种问题算是太小儿科了。

无后效性

一旦f(n)的值确定,那么之后直接调用它的值即可,不用再去担心f(n)的计算过程

动态规划分类

动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。对应的dp分别称之为一维dp和二维db。

哪些题目适合用DP解决

满足最优子结构

大问题可以由小问题推出,大问题与小问题的求解思路一致

满足无后效性

一旦f(n)确定,后续我们直接调用它的值就可以,而不用关心它是怎样过来的

动态规划类问题解决步骤

  1. 状态定义,想办法把当前局面表达出来也即f(x)或者f(x,y)… 的含义要定义出来
  2. 状态转移方程,可以从两个方面考虑,我从哪里来,我倒哪里去
  3. 初始化
  4. 代码
  5. 复杂度分析
  6. 思考状态压缩

刷题

补充

基础算法领域里的规划强调的是:在求解的过程中,记住结果,以后要用到的时候,直接使用而不必重复计算,即「空间换时间」。「背包问题」、「最长回文子串」、「最长公共子序列」、「编辑距离」这些问题的求解我们都会看到程序其实就是在填写一张表格。

如果没有学习「动态规划」,我们还有「递归」,然后发现重复子问题,使用「缓存」记住结果是非常自然的,这叫「记忆化递归」(或者「记忆化搜索」)。而「动态规划」还告诉了我们一种思路,可以从一个问题最初的样子去考虑它是如何一步一步得到最终的规模。 「动态规划」的两个思考方向:

  1. 自顶向下求解,称之为「记忆化递归」:初学的时候,建议先写「记忆化递归」的代码,然后把代码改成「自底向上」的「递推」求解;
  2. 自底向上求解,称之为「递推」或者就叫「动态规划」:在基础的「动态规划」问题里,绝大多数都可以从这个角度入手,做多了以后建议先从这个角度先思考,实在难以解决再考虑「记忆化递归」。

一旦涉及子问题,可以用自顶向下的递归和自底向上的动态规划

这里的约束只有鸡蛋的个数,因此,为了消除鸡蛋的个数对递推的过程中造成的影响,我们在设置状态的时候要在后面加上一个维度,这种做法叫消除「后效性」,是常见的套路。在「打家劫舍」问题一、问题三还有「股票」的 6 道问题用的就是这个技巧。一般而言,一个约束对应一个维度的状态。约束越多,状态的维数就越多(这里限于我的水平和经验,没有严格论证)。

参考

什么是动态规划(Dynamic Programming)?动态规划的意义是什么?