《(牛x)动态规划入门篇》由会员分享，可在线阅读，更多相关《(牛x)动态规划入门篇（60页珍藏版）》请在金锄头文库上搜索。
1、动态规划入门篇,成都大学第二期ACM暑期集训 李明金 2009/08/12,2009-8-12,成都大学ACM暑期集训DP篇李明金,1,前言,纵观ACM届，大到每年的全球总决赛，小到TC的SRM抑或各个OJ的月赛，我们很轻易的发现一个共同的规律动态规划在其中稳稳的占据了一个重要的地位。 可以说，掌握了动态规划，不一定会成为大牛，但是一只大牛，是肯定精通动态规划的。,2009-8-12,成都大学ACM暑期集训DP篇李明金,2,动态规划，和分治法一样，是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题，递归求解各子问题，然后合并子问题的解而得到原问题的解。于此不同，动态
2、规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。动态规划对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。 动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值，而我们希望找到一个具有最优（最大或最小）值的解。称这样的问题为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优解的值。总结：自从有了动态规划，这个世界变得好美妙！,2009-8-12,成都大学ACM暑期集训DP篇李明金,3,目录,0.动态规划的基本步骤 1.一个例题 2.什么时候需要动态规划 3.最优子结构 4.重叠子问题 5.动
3、态规划的两个重要元素状态&状态转移方程 6.备忘录介绍 7.例题 数字三角形 花束摆放 最大数字子串 积木游戏 Subsquence 炮兵阵地(状态压缩动态规划) 8.练习 : NOJ 江苏省赛回放 C D E（三角形演变题） H,2009-8-12,成都大学ACM暑期集训DP篇李明金,4,0.动态规划的基本步骤,1）描述最优解的结构 2）递归定义最优解的值 3）按自底向上的方式计算最优解的值 4）由计算出的结果构造一个最优解 第1-3步构成问题的动态规划解的基础。第四步只要求计算最优解的值时可以略去。如果的确做了第四步，则有时要在第三步的计算中记录一些附加信息，使构造一个最优解变得容易。,2
4、009-8-12,成都大学ACM暑期集训DP篇李明金,5,1.一个例题,例一：装配线调度问题 描述：某汽车工厂有2个装配线，每个装配线有n 个装配站（按顺序编号1n ），两个装配线对应的装配站执行相同的功能，但所用的时间可能不同。经过第i条流水线（i=1，2）的第j 个装配站所花的时间为Aij。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略，而移到另外一个流水线的下一个装配站则需要一定的时间Tij。汽车进入流水线不需要花时间，出流水线时需要花时间Tin。汽车的装配需要按顺序经过所有装配站。现在已知装配时间Aij 和转移时间Tij，要求输出装配一辆汽车所需要的最短时间。,200
5、9-8-12,成都大学ACM暑期集训DP篇李明金,6,方案一：暴力搜索，穷举所有装配可能，然后选择极小。 显然这个方案是不可行的，因为我们分析可知，装配方式共有2N种（将所使用装配站一内的站看做一个集合，全集是1.N，子集就有2N），这时时间复杂度到达O（2N），显然N太大的时候是一定会TE的。,2009-8-12,成都大学ACM暑期集训DP篇李明金,7,方案二：动态规划。 步骤一：描述最优解的结构 在这里就是通过工厂最快路线的结构 其实这里就是描述问题是否具有一个最优子结构，即可以利用子问题的最优解构造原问题的一个最优解。 在这道题中，观察一条通过S1，j的最快路线，我们发现，它必然是通过S
6、1，j-1或S2，j-1中的一个的最快路线（如果不是最快，则自我矛盾，S1，j就不是最快了） 为了解决这个问题，即寻找通过人一条装配线上的装配站J的最快路线，我们解决它的子问题，即寻找通过两条装配线上的装配站J-1的最快路线。 所以，对于这个问题，我们可以求子问题的最优解，从而得到原问题的最优解。 PS：状态，状态转移方程的概念将会在理脱出，后面会提到，只要找好了状态方程（加元等手段），就能轻松使用动态规划。,2009-8-12,成都大学ACM暑期集训DP篇李明金,8,步骤二：一个递归的解 利用子问题的最优解来递归定义一个最优解的值。 在这个问题中，我们选择在两条装备线上通过装配站j的最快路线
7、的问题作为子问题（j=1，2，3.，n）。令fij表示一个底盘从起点到装配站Si，j的最快可能时间。 我们的最终目标是确定底盘通过工厂的所有路线的最快时间，记做f*。 f* = min(f1n + x1,f2n + x2) 下面的问题就是确定f11和f21,2009-8-12,成都大学ACM暑期集训DP篇李明金,9,显然，不管是从那条线路开始装配的，底盘肯定是直接到达装配站1的，也就是说之前是不用计算转移到装配站1的时间的。 则f11 = e1 + a1,1 f21 = e2 + a2,1 现在计算fij，显然简单递推可知： fi1 = ei + ai,1; fij = min(fij-1 +
8、 ai,j , fij-1 + ti,j-1 + a2,j) fij的值就是子问题的最优解的值。 注意：这里，我们不需要知道最优解到底是什么，我们只需要求出最优解是多少即可，所以对构造过程可以不进行跟踪。,2009-8-12,成都大学ACM暑期集训DP篇李明金,10,现在，写出一个递归算法计算通过工厂的最快路线是一件很简单的事情了。只需基于以下几个公式即可： f* = min(f1n + x1,f2n + x2) fi1 = ei + ai,1; fij = min(fij-1 + ai,j , fij-1 + ti,j-1 + a2,j) 现在我们来看这种算法的时间复杂度，发现它有一个问题:
9、它的执行时间是关于n的指数形式即O（2n），这是一个时间复杂度很高的算法。我们来考虑是否能进一步提高它的效率。,2009-8-12,成都大学ACM暑期集训DP篇李明金,11,2009-8-12,成都大学ACM暑期集训DP篇李明金,12,现在考虑这样一种方式 FASTEST-WAY(a , t , e , x , n) f11 = e1+a1,1 f21 = e2 + a2,1 /这两行计算f11和f21的值 For j=2 to n /这个循环用来计算fij的值do if f1j-1+a1,j=f2j-1+t2,j-1+a1,jthen f1j = f1j-1+a1,jelse f1j=f2j
10、-1+t2,j-1+a2,jif f2j-1+a2,j=f1j-1+t1,j-1+a2,jthen f2j = f2j-1+a2,j if f1n+x1=f2n+x2 /计算f*的值then f* = f1n+x1else f* = f2n+x2 问题，这样计算比直接递归的优势是什么？,解答：减少了重复计算，因为每次计算是试用了上次计算时得出的值，相当于在一个表格里做了记录，使得后面的再次计算时不需要重复计算。这就是后面要讲到的“备忘录”的基本思想。 此题A毕总结：这是一道动态规划的典型题目，经典的由重复的子问题的最优解得到原问题的最优解。,2009-8-12,成都大学ACM暑期集训DP篇李明
11、金,13,2.什么时候需要动态规划,动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值，而我们希望找到一个具有最优（最大或最小）值的解。称这样的问题为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优解的值。 动态规划主要用于组合优化问题，即求一个离散问题在某种意义下的最优解，有时也用于组合计数问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,14,动态规划使用的基本条件就是： 1)最优子结构性质一个问题可用动态规划有效求解的基本要求是该问题具有最优子结构性质，通俗地讲即问题的最优解包含其子问题的最优解。 (2)子问题重叠性质 动态规
12、划所针对的问题还有另外一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复，称为子问题重叠性质。在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时加以求解，并把答案保存起来，以便以后再遇到时直接引用，不必重新求解，从而大大地提高解题的效率。 相比之下，一般的搜索技术，对于某个子问题，不管是否已经求解过，只要遇上，就会再次对它求解，因而影响了解题的效率。,2009-8-12,成都大学ACM暑期集训DP篇李明金,15,3.最优子结构,用动态规划求最优化问题的第一步是描述最优解的结构。回顾一下，如果问题的一个最优解中包含子问题的最优解，则该问题具有最优子结构。当一个问题具有最优子结构
13、时，提示我们动态规划可能会适用（注意，在这种情况下，贪心策略可能也是适用的）在动态规划中，我们利用子问题的最优解来构造问题的一个最优解。因此，必须小心以确保在我们所考虑的子问题的范围中，包含了用于一个最优解中的那些子问题。 在前面的装配线的例子中，可以看到在任何一条装配线上，通过装配站j的最快路线包含了在其中一条装配线上通过装配站j-1的最快路线。,2009-8-12,成都大学ACM暑期集训DP篇李明金,16,在寻找最优子结构时，可以遵循一种共同的模式： 1）问题的一个解可以是做一个选择。例如，选择一个前一个装配线装配站。做这种选择会得到一个可以导致最优解的选择。 2）假设对一个给定的问题，已
14、知的是一个可以导致最优解的选择。不必关心如何确定这个选择，尽管假定它是已知的。 3）在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好的描述所得到的子问题空间 4）利用一种“剪贴”技术，来证明在问题的一个最优解中，使用的子问题的本身必须也是最优的，通过假设每一个子问题的解都不是最优解，然后导出矛盾，即可做到这一点。如果有多于一个子问题的话，由于他们通常非常类似，所以只要对其中一个子问题的“剪贴”稍加修饰，计科很容易的用于其它子问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,17,为了描述子问题空间，可以遵循这样一条有效的经验规则，就是尽量保持这个空间简单，然后在需要的时
15、候再扩充它。例如，在装配线问题中，我们所考虑的子问题空间（其实就是后面要讲的“状态方程”）就是从工厂入口通过装配站S1，j和S2，j的最快路线。这个子问题空间很合适，因为没必要研究其他。但是往往在很多问题中，这个空间不是这么明显的，这个时候，就需要扩展子问题，得到合适的子问题空间（在后面的数字三角形中会出现这种情况，请大家注意）,2009-8-12,成都大学ACM暑期集训DP篇李明金,18,最优子结构在问题域中以两种方式变化： 1）有多少个子问题被使用在与原问题的一个最优解中 2）在决定一个最优解中使用哪些子问题时有多少个选择。 在装配线调度问题中，一个最优解只使用了一个子问题，但是，为确定一
16、个最优解，我们必须考虑两种选择。为找出通过装配站Sij的最快路线，我们使用通过S1，j-1或S2，j-1的最快路线；不管采用了哪一种，它都代表了必须最优解决的子问题。,2009-8-12,成都大学ACM暑期集训DP篇李明金,19,非正式的，一个动态规划算法的运行时间依赖于两个因素的成绩：子问题的总个数和没一个子问题中有多少种选择。在装配线调度中，总共有O（n）个子问题，并且只有两个选择来检查每个子问题，所以执行时间为O（n）。 动态规划是采用自底向上的方式利用最优子结构。也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。寻找问题的一个最优解需要在子问题中做出选择，即选择将用哪一个来求解问题。,2009-8-12,
