文档介绍：动态规划算法及算法思路的分析
石家庄二中贾志豪
[关键字]
动态规划状态表示状态转移最优化原理无后效性
[摘要]
在信息学竞赛中,我们经常遇到求最优解的问题。这些问题的特点是,只需要求出最优解,而不要求写出最优解的具体情况。为了解决这类问题,我们经常会用到一种有效的算法——动态规划。使得我们可以在有限的时间内,求出问题的解。本文首先介绍一些关于动态规划的理论知识,然后将介绍向动态规划的思路上靠拢的方法——即如何思考,最后再介绍一些经典例题。希望大家能互相促进。
我的邮箱是: dugushuiyi@
QQ:396511873
[目录]
一动态规划的理论知识
动态规划的基本思想
二解题时的思路——如何向动态规划上靠拢
分析问题是否符合动态规划的原则
确定使用动态规划时的状态和状态转移
2. 3 估计程序的时间、空间复杂度及编程的难易程度
三一些经典例题
四****题
[正文]
一动态规划的理论知识
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。(本段文字摘自国家集训队论文)
动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质和子问题重叠性质。
1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。
2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。
符合最优化原理和无后效性原则是使用动态规划的原则。
1、最优化原理:最优化原理一概念在刘汝佳的《算法艺术与信息学竞赛》一书中是这样解释的——再把原问题转换成规模更小的字问题时,原问题最优当且仅当子问题最优,这就是最优化原理。
可以通俗地理解为子问题的局部最优将导致整个问题的全局最优,即问题具有最优子结构的性质,也就是说一个问题的最优解只取决于其子问题的最优解,非最优解对问题的求解没有影响。
2、无后效性原则:所谓无后效性原则,指的是这样一种性质:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说,“未来与过去无关”,当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变。具体地说,如果一个问题被划分各个阶段之后,阶段 I 中的状态只能由之前的有限步状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就是无后效性。
在这里,特别要注意的是:对于某些不满足无后效性原则的状态表示,可以通过更改状态表示的维数(一般为增加数组维数),使得状态表示满足无后效性(这一点在后面的例题中会具体介绍)。但不可避免的,在增加维数的同时,会增加问题的时间、空间复杂度。这就是在动态规划算法中的一个弊端。在这里,笔者要说的是,
在某些情况下,动态规划并不一定是最好的算法,甚至不能算是一个较好的算法。希望读者在后面的问题中能用心体会。
二解题时的思路——如何向动态规划上靠拢
很自然的,大家在思考某一道题,会先考虑它能不能用动态规划解题,动态规划在这道题中是不是一个较优的算法。而一部分人思考的过程是:这一道题如果我能想出状态表示和状态转移方程,那么它就可以使用动态规划,否则就不能。读到这里大家可能会笑,但大部分初学动态规划的人在思考问题时都会是这种思路。其实,动态规划在一道题中的价值有无、价值大小是有规律可循的。下面笔者就介绍一种较为行之有效的解题思路。
1、分析问题是否符合动态规划的原则
2、确定使用动态规划时的状态和转态转移
3、估计程序的时间、空间复杂度及编程的难易程度
首先:分析问题是否符合动态规划的