聊聊动态规划(2) -- 特征

内容简介：聊聊动态规划(2) -- 特征

书接前文，上回咱们说到要如何鉴别动态规划可解问题。我预告说要从计算机工作原理开始讲起……呃……貌似跟原本要讲的东西差的有点儿远呢……那么为啥非要从这么底层的问题开始讲起呢？怎么说呢……就好比我要讲西游记，如果只说一句“唐僧师徒四人去西天取经然后都修成正果了”，对于没看过西游记的人来说，唐僧是谁、师徒四人又是谁、为啥非得跑西天去取经等等一系列问题，不去翻翻原著搜搜资料是肯定不知道怎么回事的。所以还是尽量揉碎了讲吧，不然看完了还得一通翻查资料，怪麻烦的……

尽管计算机技术自20世纪40年代第一部电子通用计算机诞生以来一直飞速的发展，但是，现代计算机仍然采用冯诺依曼结构来实现。冯诺依曼结构将计算机描述为五部分：输入设备、控制器、运算器、存储器和输出设备。工作流程大概就是，输入设备传入数据，控制器发出指令，运算器根据指令做算数逻辑运算，最后存储或者输出结果。如果咱们只关注计算机的理论原理，在抽象一点的看计算机工作的整个过程，你会发现，刚才我们描述的工作过程可以用数学理论来概括。存储器可以看做一个列举了计算机存在的所有可能状态的 集合 ，控制器指令可以看做一组 状态转换函数 ，运算器使用状态转换函数，从输入的状态和集合的状态，推导出输出的状态。所以计算机的工作原理，可以简单的概括为，利用当前的状态计算出下一个状态（美错儿，我就是在说状态机……）。

我们平时编写程序，是在使用计算机帮我们解决问题。从计算机的本质是状态机这个角度来看，你思考如何编写程序来解决问题，其实就是在思考如何将这个问题表达成状态（用哪些变量，存储哪些数据）以及如何在状态之间中转换（怎样根据一些变量计算出另一些变量）。我们在看算法分析文章时，经常能看到的平时能看到的所谓 空间复杂度 ，就是为了支持你的转换状态所必需存储的状态最多有多少；所谓 时间复杂度 ，就是从初始状态到达最终状态中间需要做多少次状态转换。

还拿我们上一次说的斐波拉契数列做:chestnut: ：

我要计算第100项，之前的每一项就是这个问题的一个状态。每求新一项（新的一个状态）只需要之前的两个项（之前的两个状态）。所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数；每求一个新状态，所需要的时间是常数，而之前的状态是线性递增的，所以时间复杂度就是线性的。

上面这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行（a[i]=a[i-1]+a[i-2]），不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。

斐波拉契数列这个例子过于简单，以至于让人忽视了阶段的概念。所谓阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。斐波拉契数列中，每一步会计算得到一个新数字，所以每个阶段只有一个状态。咱们来想象另外一个情景：假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。

现在问题来了，有了阶段之后，计算新状态可能会遇到各种奇葩的情况，针对不同的情况，就需要不同的算法，下面就分情况来说明一下：

假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。

好消息是，有时候我们并不需要真的计算所有状态。

比如拿这样一个的棋盘问题举例：

从棋盘的左上角到达右下角最短需要几步。答案很显然，用这样一个简单的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态，正如这个问题中走n步可以走到很多位置一样。但是同样n步中，有哪些位置可以让我们在第n+1步中走的最远呢？没错，正是第n步中走的最远的位置。换成一句熟悉话叫做“ 下一步最优是从当前最优得到的 ”。所以为了计算最终的最优值，只需要存储每一步的最优值即可，解决符合这种性质的问题的算法就叫贪心算法。如果只看最优状态之间的计算过程是不是和斐波拉契数列的计算很像？所以计算的方法也是递推。

既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题：一个阶段的最优可以由前一个阶段的最优得到。

如果一个阶段的最优无法用前一个阶段的最优得到呢？（需要前两个阶段得到当前最优，跟只用前一个阶段并没有本质区别）

最麻烦的情况在于你需要之前所有的情况才行。再举一个探索迷宫的:chestnut: ：

现在有一个迷宫，我们要计算从起点到终点的最短路线。这时你就不能只保存当前阶段的状态了，因为要求你计算最短路径，所以你必须知道之前走过的所有位置。因为即便你当前在的位置不变，之前的路线不同也会影响你之后走的路线。这时你需要保存的是之前每个阶段所经历的状态，根据之前所有的状态你才能计算出下一个状态！每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，这种记录所有状态计算下一个状态的算法就叫搜索。所以搜索的空间复杂度就是指数级的，时间复杂度也是指数的。

刚才提到的那种令人不开心的情况，就叫做有后效性。

刚刚的情况实在太普遍，我们刚刚说到的解决方法也实在太暴力。那么，有没有哪些情况可以避免如此的暴力呢？契机就在于后效性。

有这么一类问题，看似需要之前所有的状态，其实不用。比如求 最长上升子序列（LIS） 长度问题：

在一个无序的数组里，找出一组尽可能长的由低到高排列的数，这组数就叫最长上升子序列。

比如，给出[5,4,1,2,3]，LIS 就是 [1,2,3]，长度是3；给出[4,2,4,5,3,7]，LIS 是 [2,4,5,7]，长度是 4。

看到这个问题，第一反应就是用遍历去解决。从头到尾依次枚举是否选择当前的数字，每选定一个数字就要去看看是不是满足“上升”的性质，这里第i个阶段就是去思考是否要选择第i个数，第i个阶段有两个状态，分别是选和不选。哈哈，依稀出现了刚刚搜索迷宫的影子！

但是当我们仔细思考之后会发现，每次当我决定要选择当前数字的时候，只需要和之前选定的一个数字比较，就能做出判断了！这是和之前迷宫问题的本质不同。这样我们就不需要记录之前所有的状态了。因为最后要求的是序列长度，所以我们只需要记录以某个元素结尾的LIS长度就好。

这种“每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到”的性质就叫做最优子结构；而“不管状态之前是如何得到的”的性质就叫做无后效性。

那么，终于可以说出动态规划问题的两个特点了，这两个特点就是 最优子结构 和 无后效性 ！只要有这两个特点的问题，就可以用动态规划的方法来解决了。

通过之前的一系列描述我们也能看到，一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间的状态转移方式决定的！

• 每个阶段只有一个状态 —— 用递推。
• 每个阶段的最优状态都是由上一个阶段的最优状态得到 —— 用贪心。
• 每个阶段的最优状态是由之前所有阶段的状态的组合得到 —— 用搜索。
• 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的 —— 用动态规划。

另外需要注意的是，一个问题从不同的角度分析，各阶段状态的定义和状态转移方式可能都不相同，存在一个有后效性的定义，并不代表该问题不适用动态规划的方法来解。就像我最早说过的一样：寻找看问题的角度，才是动态规划的核心~

好的那么由于时间不足本次的博客就到这里，如果不出意外的话，大概可能maybe也许下周五会更新吧~！能不能准时更新，就全看米娜桑点赞打赏转发安利发评论的热情啦~！

白了个白~！

相关资料

• 什么是动态规划？动态规划的意义是什？

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 特征工程：特征获取、特征规范和特征存储
• 特征工程之特征缩放 & 特征编码
• 特征工程：特征设计、特征可用性评估
• [译] 为什么要做特征缩放，怎么做特征缩放，什么时候做特征缩放？特征缩放三连了解一下
• 特征金字塔特征用于目标检测
• 数据挖掘篇——特征工程之特征降维

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。