我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

动态规划专题-除了递推之外需要了解的思想

归档日期:06-04       文本归类:动态规划      文章编辑:爱尚语录

  动态规划基本会出现在信息学比赛的各类考试中,理解动态规划,学会动态规划的思想对于信息学的同学们来说至关重要!

  递推说白了就是在知道前i-1项的值的前提下,计算第i项的值,而记忆化搜索则是另外一种思路。它是直接计算第i项,需要用到第 j 项的值( j i)时去查表,如果表里已经有第 j 项的话,则直接取出来用,否则递归计算第 j 项,并且在计算完毕后把值记录在表中。记忆化搜索在求解多维的情况下比递推更加方便,【例题3】是我遇到的第一个记忆化搜索的问题,记忆犹新。

  乍看下只要将伪代码翻译成实际代码,然后直接对于给定的a, b, c,调用函数w(a, b, c)就能得到值了。但是只要稍加分析就能看出这个函数的时间复杂度是指数级的(尽管这个三元组的最大元素只有20,这是个陷阱)。对于任意一个三元组(a, b, c),w(a, b, c)可能被计算多次,而对于固定的(a, b, c),w(a, b, c)其实是个固定的值,没必要多次计算,所以只要将计算过的值保存在f[a][b][c]中,整个计算就只有一次了,总的时间复杂度就是O(n^3),这个问题的n只有20。

  在介绍递推和记忆化搜索的时候,都会涉及到一个词---状态,它表示了解决某一问题的中间结果,这是一个比较抽象的概念,例如【例题1】中的f[i][j],【例题2】中的FA[i]、FB[i],【例题3】中的f[a][b][c],无论是递推还是记忆化搜索,首先要设计出合适的状态,然后通过状态的特征建立状态转移方程(f[i] = f[i-1] + f[i-2] 就是一个简单的状态转移方程)。

  在介如果问题的最优解包含的子问题的解也是最优的,就称该问题具有最有子结构,即满足最优化原理。这里我尽力减少理论化的概念,而改用一个简单的例题来加深对这句话的理解。

  【例题4】给定一个长度为n(1 = n = 1000)的整数序列a[i],求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列),满足如下条件:

  我想到的是万金油算法---枚举(DFS),即枚举a[i]这个元素取或不取,所有取的元素组成一个合法的子序列,枚举的时候需要满足单调递增这个限制,那么对于一个n个元素的序列,最坏时间复杂度自然就是O(2n),n等于30就已经很变态了更别说是1000。但是方向是对的,动态规划求解之前先试想一下搜索的正确性,这里搜索的正确性是很显然的,因为已经枚举了所有情况,总有一种情况是我们要求的解。我们尝试将搜索的算法进行一些改进,假设第i个数取的情况下已经搜索出的最大长度记录在数组d中,即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度,那么如果下次搜索得到的序列长度小于等于d[i],就不必往下搜索了(因为即便继续往后枚举,能够得到的解必定不会比之前更长);反之,则需要更新d[i]的值。如图一-4-1,红色路径表示第一次搜索得到的一个最长子序列1、2、3、5,蓝色路径表示第二次搜索,当枚举第3个元素取的情况时,发现以第3个数结尾的最长长度d[3] = 3,比本次枚举的长度要大(本次枚举的长度为2),所以放弃往下枚举,大大减少了搜索的状态空间。

  这时候,我们其实已经不经意间设计好了状态,就是上文中提到的那个d[i]数组,它表示的是以a[i]结尾的最长单调子序列的长度,那么对于任意的i,d[i] 一定等于 d[j] + 1 ( j i ),而且还得满足 a[j] a[i]。因为这里的d[i]表示的是最长长度,所以d[i]的表达式可以更加明确,即:

  这个表达式很好的阐释了最优化原理,其中d[j]作为d[i]的子问题,d[i]最长(优)当且仅当d[j]最长(优)。当然,这个方程就是这个问题的状态转移方程。状态总数量O(n), 每次转移需要用到前i项的结果,平摊下来也是O(n)的,所以该问题的时间复杂度是O(n^2),然而它并不是求解这类问题的最优解,下文会提到最长单调子序列的O(nlogn)的优化算法。

  一个状态演变到另一个状态,往往是通过“决策”来进行的。有了“决策”,就会有状态转移。而

  无后效性,就是一旦某个状态确定后,它之前的状态无法对它之后的状态产生“效应”(影响)。

  【例题5】老王想在未来的n年内每年都持有电脑,m(y, z)表示第y年到第z年的电脑维护费用,其中y的范围为[1, n],z的范围为[y, n],c表示买一台新的电脑的固定费用。 给定矩阵m,固定费用c,求在未来n年都有电脑的最少花费。

  考虑第 i 年是否要换电脑,换和不换是不一样的决策,那么我们定义一个二元组(a, b),其中 a b,它表示了第a年和第b年都要换电脑(第a年和第b年之间不再换电脑),如果假设我们到第a年为止换电脑的最优方案已经确定,那么第a年以前如何换电脑的一些列步骤变得不再重要,因为它并不会影响第b年的情况,这就是无后效性。

  更加具体得,令d[i]表示在第i年买了一台电脑的最小花费(由于这台电脑能用多久不确定,所以第i年的维护费用暂时不计在这里面),如果上一次更换电脑的时间在第j年,那么第j年更换电脑到第i年之前的总开销就是c + m(j, i-1),于是有状态转移方程:

  这里的d[i]并不是最后问题的解,因为它漏算了第i年到第n年的维护费用,所以最后问题的答案:

  我们发现两个方程看起来很类似,其实是可以合并的,我们可以假设第n+1年必须换电脑,并且第n+1年换电脑的费用为0,那么整个阶段的状态转移方程就是:

本文链接:http://quangdungfc.net/dongtaiguihua/230.html