(牛X)动态规划入门篇.ppt

动态规划入门篇成都大学第二期ACM暑期集训李明金2009/08/122009-8-?纵观ACM届,大到每年的全球总决赛,小到TC的SRM抑或各个OJ的月赛,我们很轻易的发现一个共同的规律——动态规划在其中稳稳的占据了一个重要的地位。?可以说,掌握了动态规划,不一定会成为大牛,但是一只大牛,是肯定精通动态规划的。2009-8-?动态规划,和分治法一样,是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题,递归求解各子问题,然后合并子问题的解而得到原问题的解。于此不同,动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。动态规划对每个子子问题只求解一次,将其结果保存在一张表中,从而避免每次遇到各个子问题时重新计算答案。?动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值,而我们希望找到一个具有最优(最大或最小)值的解。称这样的问题为该问题的“一个”最优解(而不是“确定的”最优解),因为可能存在多个取最优解的值。?总结:自从有了动态规划,这个世界变得好美妙!2009-8-??????—状态&状态转移方程???数字三角形?花束摆放最大数字子串?积木游戏Subsquence?炮兵阵地(状态压缩动态规划)?: NOJ江苏省赛回放 C D E(三角形演变题) H 2009-8-?1)描述最优解的结构?2)递归定义最优解的值?3)按自底向上的方式计算最优解的值?4)由计算出的结果构造一个最优解?第1-3步构成问题的动态规划解的基础。第四步只要求计算最优解的值时可以略去。如果的确做了第四步,则有时要在第三步的计算中记录一些附加信息,使构造一个最优解变得容易。2009-8-?例一:装配线调度问题?描述:某汽车工厂有2个装配线,每个装配线有n 个装配站(按顺序编号1~n ),两个装配线对应的装配站执行相同的功能,但所用的时间可能不同。经过第i条流水线(i=1,2)的第j 个装配站所花的时间为Aij。从第i条流水线的第j 个装配站移到第j+1个装配站的时间可以忽略,而移到另外一个流水线的下一个装配站则需要一定的时间Tij。? 汽车进入流水线不需要花时间,出流水线时需要花时间Tin。? 汽车的装配需要按顺序经过所有装配站。? 现在已知装配时间Aij 和转移时间Tij,要求输出装配一辆汽车所需要的最短时间。2009-8-?方案一:暴力搜索,穷举所有装配可能,然后选择极小。?显然这个方案是不可行的,因为我们分析可知,装配方式共有2^N种(将所使用装配站一内的站看做一个集合,全集是1….N,子集就有2^N),这时时间复杂度到达O(2^N),显然N太大的时候是一定会TE的。2009-8-?方案二:动态规划。?步骤一:描述最优解的结构?在这里就是通过工厂最快路线的结构?其实这里就是描述问题是否具有一个最优子结构,即可以利用子问题的最优解构造原问题的一个最优解。?在这道题中,观察一条通过S1,j的最快路线,我们发现,它必然是通过S1,j-1或S2,j-1中的一个的最快路线(如果不是最快,则自我矛盾,S1,j就不是最快了)?为了解决这个问题,即寻找通过人一条装配线上的装配站J的最快路线,我们解决它的子问题,即寻找通过两条装配线上的装配站J-1的最快路线。?所以,对于这个问题,我们可以求子问题的最优解,从而得到原问题的最优解。?PS:状态,状态转移方程的概念将会在理脱出,后面会提到,只要找好了状态方程(加元等手段),就能轻松使用动态规划。2009-8-?步骤二:一个递归的解?利用子问题的最优解来递归定义一个最优解的值。?在这个问题中,我们选择在两条装备线上通过装配站j的最快路线的问题作为子问题(j=1,2,3….,n)。令fi[j]表示一个底盘从起点到装配站Si,j的最快可能时间。?我们的最终目标是确定底盘通过工厂的所有路线的最快时间,记做f*。?f* = min(f1[n] + x1,f2[n] + x2)下面的问题就是确定f1[1]和f2[1]2009-8-?显然,不管是从那条线路开始装配的,底盘肯定是直接到达装配站1的,也就是说之前是不用计算转移到装配站1的时间的。?则f1[1] = e1 + a1,1f2[1] = e2 + a2,1?现在计算fi[j],显然简单递推可知:?fi[1] = ei + ai,1;?fi[j] = min(fi[j-1] + ai,j , fi[j-1] + ti,j-1 + a2,j)