动态规划

flydreamforever

525人浏览 · 2016-12-19 20:43:03

flydreamforever · 2016-12-19 20:43:03 发布

1、概述(Overview)

动态规划(Dynamic Programming)是一种求解决策过程(Decision Process)最优化的数学方法。它将一个复杂的问题分成相对简单的一类子问题，然后再将子问题分解成更加简单的一类子问题。在动态规划中，我们可以将每类子问题看成是动态规划的一个阶段。而在动态规划每个阶段中，往往会有很多状态(这也是为什么会说将一个复杂问题分成一类子问题，这些子问题之间具有共性，每个子问题就相当于该阶段下的一个状态)，可以通过图1-1来加深理解这一概念。
1-1 动态规划状态图

图1-1 动态规划状态图
在图1-1中，Problem表示我们目前遇到的问题，

SPn−1m<script type="math/tex" id="MathJax-Element-20128">SP_m^{n-1}</script> 表示在阶段

n−1<script type="math/tex" id="MathJax-Element-20129">n-1</script> 下第

m<script type="math/tex" id="MathJax-Element-20130">m</script> 个子问题。一般情况下，使用动态规划分析问题的时候都是使用自顶而下的分析方式，而在解决问题的时候却使用的是自下而上的方式。造成这样的区别在于当分析问题的时候，我们发现该问题其是由一类子问题组成的，解决这类子问题就可以解决当前问题。紧接着分析这类子问题时候，我们发现该类子问题又可以分为另外一类子问题，最终我们将找到不可再分的子问题。这相当于从金字塔的顶端走到了塔底，金字塔的每一层就相当于动态规划的每一个阶段(一类子问题)。在找到不可再分的子问题时后我们会恍然大悟，原来只有彻底解决了这类子问题，我们才能解决最终的问题。再拿金字塔举列，只有在建好金字塔的底层后一步步往上建，才能建成金字塔，走到金子塔的塔顶。世界上不会存在空中楼阁，金字塔建造过程就是我所说动态规划自下而上的解决过程。

2、阶段与状态(Phases and States)

在学习新知识的时候，我总是喜欢先在整体上了解我所要学的东西，这就相当于站在一个上帝的视角俯瞰世界一样。当我已在自己的脑海里为这一世界建立了轮廓之后，下面就要开始抽丝剥缕般去完善这个的世界。
在前一节我们已经了解了动态规划就是需要自顶而下的去分析问题且自下而上的去解决问题。而在这过程中，我引入的两个术语阶段和状态可能会让你困惑，没关系，现在到我们去完善这两个概念的时候了。
相对于穷举法，动态规划的优势在于其将问题解决过程分成了阶段性的过程，且解决当前阶段的问题只需要获取之前某个阶段(一般情况下是上个阶段)解决问题的结果，更专业点的说法是获取当前阶段的状态只需要获取之前某个阶段的状态。而动态规划的难点主要就是去寻找阶段与阶段之间的联系。
拿Fibonacii数列举例：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

在生成Fibonacii数列的时候会发现，当前Fibonacci数是由前两个数相加获得。而生成新的Fibonacii数的过程就可以被认为是一个阶段，在每个阶段中，我们总需要获取上个阶段的结果，即该数的前两个数，因此我们可以认为每个阶段有两个状态。其实现过程如下

第0阶段
两个状态 s0<script type="math/tex" id="MathJax-Element-20105">s_0</script> = 0, s1<script type="math/tex" id="MathJax-Element-20106">s_1</script> = 1
第1阶段
产生新的输出 o<script type="math/tex" id="MathJax-Element-20107">o</script> = s0<script type="math/tex" id="MathJax-Element-20108">s_0</script> + s1<script type="math/tex" id="MathJax-Element-20109">s_1</script>= 0 + 1 = 1
两个状态 s0<script type="math/tex" id="MathJax-Element-20110">s_0</script> = s1<script type="math/tex" id="MathJax-Element-20111">s_1</script> = 1, s1<script type="math/tex" id="MathJax-Element-20112">s_1</script> = o<script type="math/tex" id="MathJax-Element-20113">o</script> = 1

第2阶段
产生新的输出 o<script type="math/tex" id="MathJax-Element-20114">o</script> = s0<script type="math/tex" id="MathJax-Element-20115">s_0</script> + s1<script type="math/tex" id="MathJax-Element-20116">s_1</script>= 1 + 1 = 2
两个状态 s0<script type="math/tex" id="MathJax-Element-20117">s_0</script> = s1<script type="math/tex" id="MathJax-Element-20118">s_1</script> = 1, s1<script type="math/tex" id="MathJax-Element-20119">s_1</script> = o<script type="math/tex" id="MathJax-Element-20120">o</script> = 2

第3阶段
产生新的输出 o<script type="math/tex" id="MathJax-Element-20121">o</script> = s0<script type="math/tex" id="MathJax-Element-20122">s_0</script> + s1<script type="math/tex" id="MathJax-Element-20123">s_1</script>= 1 + 2 = 3
两个状态 s0<script type="math/tex" id="MathJax-Element-20124">s_0</script> = s1<script type="math/tex" id="MathJax-Element-20125">s_1</script> = 2, s1<script type="math/tex" id="MathJax-Element-20126">s_1</script> = o<script type="math/tex" id="MathJax-Element-20127">o</script> = 3
…

通过该过程你应该能够稍微明白了动态规划中的阶段和状态的含义了。在每个阶段过程计算过程中，我们都保存了上个阶段的结果，动态规划比穷举法快的一部分原因是其用空间去换时间。

3、练习与巩固(Exercises and Consolidating)

经过上面一节对阶段和状态的描述之后，你也许还是有点困惑，但是没关系，在这一节里将通过两个可以使用动态规划解决的经典问题来加深对动态规划理解。本节主要侧重于使用动态规划分析问题的过程，所以如何编码去解决问题可以在之后独立完成，用来检验自己对动态规划的理解。

3.1、0-1背包问题

问题描述：

有N<script type="math/tex" id="MathJax-Element-20073">N</script>件物品和一个容量为V<script type="math/tex" id="MathJax-Element-20074">V</script>的背包。第i<script type="math/tex" id="MathJax-Element-20075">i</script>件物品的重量是wi<script type="math/tex" id="MathJax-Element-20076">w_i</script>，价值是vi<script type="math/tex" id="MathJax-Element-20077">v_i</script>。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

对于这一个问题，如果使用穷举法的话，因为有N<script type="math/tex" id="MathJax-Element-20078">N</script>个物品，每个物品存在放入背包和不放入背包两种状态，因此总共存在2N<script type="math/tex" id="MathJax-Element-20079">2^N</script>种组合，然后比较每种组合的价值选则价值最大的组合，该穷举法的时间复杂度是O(2N)<script type="math/tex" id="MathJax-Element-20080">O(2^N)</script> 指数级复杂度，显然穷举法不是该问题的最好的解决方式。
那该如何使用动态规划去解决该问题了？想想我们第一节概述说的动态规划的自顶而下的分析方式，解决该问题的关键就是我们怎么去定义该问题的阶段与状态。
首先，在考虑N件物品背包问题的时候，我们发现，N件物品背包问题可以分为两种情况，第一种情况是第1<script type="math/tex" id="MathJax-Element-20081">1</script>件物品放入背包，第二种情况是第1<script type="math/tex" id="MathJax-Element-20082">1</script>件物品不放入背包。
当第1<script type="math/tex" id="MathJax-Element-20083">1</script>件物品放入背包时候，N个背包问题可以描述成如下:

现有1<script type="math/tex" id="MathJax-Element-20084">1</script>件物品,该物品重量是w1<script type="math/tex" id="MathJax-Element-20085">w_1</script>,价值是v1<script type="math/tex" id="MathJax-Element-20086">v_1</script>。还剩下N−1<script type="math/tex" id="MathJax-Element-20087">N-1</script>件物品和一个容量为V−w1<script type="math/tex" id="MathJax-Element-20088">V-w_1</script>的背包。第i<script type="math/tex" id="MathJax-Element-20089">i</script>件物品的重量是wi<script type="math/tex" id="MathJax-Element-20090">w_i</script>，价值是vi<script type="math/tex" id="MathJax-Element-20091">v_i</script>, 2≤i≤N<script type="math/tex" id="MathJax-Element-20092">2 \leq i \leq N</script>。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和CV−w1N−1<script type="math/tex" id="MathJax-Element-20093">C_{N-1}^{V-w_1}</script>最大。

当第1<script type="math/tex" id="MathJax-Element-20094">1</script>件物品不放入背包的时候，N个背包的问题可以描述成如下:

现有N−1<script type="math/tex" id="MathJax-Element-20095">N-1</script>件物品和一个容量为V<script type="math/tex" id="MathJax-Element-20096">V</script>的背包。第i<script type="math/tex" id="MathJax-Element-20097">i</script>件物品的重量是wi<script type="math/tex" id="MathJax-Element-20098">w_i</script>，价值是vi<script type="math/tex" id="MathJax-Element-20099">v_i</script>, 2≤i≤N<script type="math/tex" id="MathJax-Element-20100">2 \leq i \leq N</script>。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和CVN−1<script type="math/tex" id="MathJax-Element-20101">C_{N-1}^{V}</script>最大。

所以N<script type="math/tex" id="MathJax-Element-20102">N</script>件物品的背包问题就变成了求出这两种情况中价值总和最大的情况，即N<script type="math/tex" id="MathJax-Element-20103">N</script>件物品背包问题最大的价值总和CVN<script type="math/tex" id="MathJax-Element-20104">C_N^V</script>是

$C V N = m a x (C V N - 1, C V - w 1 N - 1 + v 1) (1)$ <script type="math/tex; mode=display" id="MathJax-Element-17892"> C_N^V = max( C_{N-1}^{V}, C_{N-1}^{V-w_1}+v_1) \tag{1} </script>
从公式(1)可以看出N件物品的背包问题可以由N−1<script type="math/tex" id="MathJax-Element-17893">N-1</script>件物品的背包问题解决，而类似的N−1<script type="math/tex" id="MathJax-Element-17894">N-1</script>件物品又可以由N−2<script type="math/tex" id="MathJax-Element-17895">N-2</script>件物品解决,所以最终只要解决1件物品的背包问题就可以解决N的物品的背包问题。
在该问题分析中，可以很明显看出是一种自顶而下的分析方式，我们可以把每类背包问题看成是一个阶段，即N件背包问题有N个阶段。那阶段找到了，且每个阶段之间的关系也找到了，即公式(1)，那每个阶段里面的状态是什么？其实很简单，在公式(1)中，我们发现同样是处理N−1<script type="math/tex" id="MathJax-Element-17896">N-1</script>背包问题，但是两个背包问题的背包容量却不同，所以，我们就可以尝试将背包问题的背包容量作为状态，即背包容量1,2,3...V−1,V<script type="math/tex" id="MathJax-Element-17897">1,2,3...V-1,V</script>作为每个阶段的状态。
哈哈，现在有没有一种恍然大悟的感觉。你可能会问，自顶向下分析问题结束了，该怎么自下而上解决问题了？这个当然很简单，过程如下：

第1阶段: 1件物品背包问题
求出在j=1,2,3...V−1,V<script type="math/tex" id="MathJax-Element-17898">j = 1,2,3...V-1,V</script>背包容量下最大的价值和是Cj1<script type="math/tex" id="MathJax-Element-17899">C_{1}^{j}</script>

第2阶段: 2件物品背包问题
通过公式(1)求出
在j=1,2,3...V−1,V<script type="math/tex" id="MathJax-Element-17900">j = 1,2,3...V-1,V</script>背包容量下最大的价值和是Cj2<script type="math/tex" id="MathJax-Element-17901">C_{2}^{j}</script>

…

第N-1阶段: N-1件物品背包问题
通过公式(1)求出
在j=1,2,3...V−1,V<script type="math/tex" id="MathJax-Element-17902">j = 1,2,3...V-1,V</script>背包容量下最大的价值和是CjN−1<script type="math/tex" id="MathJax-Element-17903">C_{N-1}^{j}</script>

第N阶段: N件物品背包问题
通过公式(1)求出背包容量V<script type="math/tex" id="MathJax-Element-17904">V</script>下最大的价值和是CVN<script type="math/tex" id="MathJax-Element-17905">C_{N}^{V}</script>

让我们来分析下用动态规划算法求解该问题的时间复杂度。在每个阶段，分别要计算V<script type="math/tex" id="MathJax-Element-17906">V</script>次状态，共有N<script type="math/tex" id="MathJax-Element-17907">N</script>个阶段，所以总的时间复杂度是O(N∗V)<script type="math/tex" id="MathJax-Element-17908">O(N*V)</script>, 相比于穷举法的指数级复杂度O(2N)<script type="math/tex" id="MathJax-Element-17909">O(2^N)</script> ，是不是快了很多？

3.2、最长升序列问题

问题描述

有个不重复的乱序数组，如[3,1,4,8,2,10,6],求出其最长升序列的长度

和背包问题一样，先用穷举法来分析这个问题，假设该数组元素个数是n<script type="math/tex" id="MathJax-Element-20030">n</script>，则在最长生序列中，每个元素有在和不在两种状态,因此总共存在2n<script type="math/tex" id="MathJax-Element-20031">2^n</script>种组合，然后比较每种组合的长度，该穷举法的时间复杂度是O(2n)<script type="math/tex" id="MathJax-Element-20032">O(2^n)</script> 指数级复杂度。
在认识到穷举法的不足之后，这题该如何用动态规划方法去分析了？
在仔细观察数组之后，你会发现，不管什么升序列，其升序列中元素出现的先后顺序是固定的。对于问题中数组的元素1和8，如果一个升序列同时存在1，8，则必然1出现在8前面，所以我们就可以从数组的左边往数组的右边开始寻找升序列。每往右遇见一个新的元素，我们可以认为进入了一个新的阶段，因为每遇到一个新的元素，必然产生一个新的最长升序列，即以当前元素结尾的最长升序列。
这样，我们已经找到了动态规划求解该问题的阶段和阶段之间的关系了？那状态是什么？其实在仔细分析阶段之间的关系可以发现，每个阶段的状态就是以已出现过的元素结尾的最长升序列的长度。

假设一个长度为n<script type="math/tex" id="MathJax-Element-20033">n</script>的数组a<script type="math/tex" id="MathJax-Element-20034">a</script>,其各个元素用ai<script type="math/tex" id="MathJax-Element-20035">a_i</script>表示，则以元素ai<script type="math/tex" id="MathJax-Element-20036">a_i</script>结尾的最长升序列长度是fi<script type="math/tex" id="MathJax-Element-20037">f_i</script>，0≤i≤n−1<script type="math/tex" id="MathJax-Element-20038"> 0 \leq i \leq n-1</script> , 则 fi+1<script type="math/tex" id="MathJax-Element-20039">f_{i+1}</script>的求解过程是

$f i + 1 = m a x (f k + 1 | a i + 1 > a k, k \in 0, . . ., i) (2)$ <script type="math/tex; mode=display" id="MathJax-Element-20040"> f_{i+1} = max(f_{k} + 1 | a_{i+1} > a_k, k \in 0,...,i) \tag{2} </script>

所以我们只需要保存以已出现过元素结尾的最长升序列的长度。
这样，其每个阶段的过程如下：

第1阶段: 元素3
状态：以3结尾的升序列最长长度是1

第2阶段: 元素1
状态：以3结尾的升序列最长长度是1
状态： 1比3小，其中以1结尾的最长升序列最长长度是1

第3阶段: 元素4
状态：以3结尾的升序列最长长度是1
状态：以1结尾的升序列最长长度是1
状态： 4比1，3都大，其中以4结尾的最长升序列长度是2

第4阶段: 元素8
状态：以3结尾的升序列最长长度是1
状态：以1结尾的升序列最长长度是1
状态：以4结尾的升序列最长长度是2
状态： 8比1，3，4都大，其中以8结尾的最长升序列长度是3

…

第7阶段:元素6
状态：以3结尾的升序列最长长度是1
状态：以1结尾的升序列最长长度是1
状态：以4结尾的升序列最长长度是2
状态：以8结尾的升序列最长长度是3
状态：以2结尾的升序列最长长度是2
状态：以10结尾的升序列最长长度是4
状态： 6比3，1，4，2都大，其中以6结尾最长升序列长度是3

所以该数组中最长的升序列是以10结尾的升序列，长度为4。

4、总结

总的来说，使用动态规划需要记住自顶而下的去分析问题且自下而上的去解决问题,重点是要找到其各个阶段和每个阶段对应的状态。相对于穷举法，动态规划算法主要是通过空间去换时间来提高计算速度，它保留个之前阶段的结果已避免了重复计算。
最后一wikipedia上对动态规划的定义来结束本篇博客：

dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions