文档介绍：动态规划动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)解。若存在多个最优解的话,它只取其中的一个。动态规划的基本概念动态规划的基本概念动态规划所处理的问题是一个“多阶段决策问题”目的是得到一个最优解(方案)大概思想如下图所示:动态规划的基本概念1、阶段用动态规划求解一个问题时,需要将问题的全过程恰当地划分成若干个相互联系的阶段,以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的,一般要便于把问题转化成多阶段决策的过程。2、状态状态表示的是事物某一阶段的性质,状态通过一个变量来描述,这个变量称为状态变量。各个状态之间是可以相互转换的。动态规划的基本概念4、策略和最优策略所有阶段按照约定的决策方法,依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中,从决策允许集合中找出最优效果的策略称为最优策略。5、状态转移方程前一阶段的终点就是后一阶段的起点,这种关系描述了由K阶段到K+1阶段状态的演变规律,是关于两个相邻阶段状态的方程,称为状态转移方程,是动态规划的核心。3、决策对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策,在每一个阶段中都需要有一次决策。一次决策就会从一个阶段进入另一个阶段,状态也就发生了转移。运用动态规划的条件1、最优化原理 子问题的局部最优将导致整个问题的全局最优,即问题具有最优子结构的性质。也就是说一个问题的最优解只取决于其子问题的最优解,非最优解对问题的求解没有影响。比如数字三角形问题,如果我们想求走到某一位置的最优路径,我们只需要知道其左上方或正上方两个位置之一的最优值,而不用考虑其它的路径,因为其它的非最优路径肯定对当前位置的结果没有影响。运用动态规划的条件2、无后效性原则1、最优化原理所谓无后效性原则,指的是这样一种性质:某一阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说“未来与过去无关”。当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变。动态规划简介拦截导弹(NOIP1999)问题描述:某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹的枚数和导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,每个数据之间有一个空格),计算这套系统最多能拦截多少导弹?如果要拦截所有导弹最少要配备多少套这种导弹拦截系统?样例输入:8 389 207 155 300 299 170 158 65 样例输出:6(最多能拦截的导弹数)2(要拦截所有导弹最少要配备的系统数)“拦截导弹”问题分析先讨论第一问:假设a[i]表示拦截的最后一枚导弹是第i枚时,系统能拦得的最大导弹数。例如,样例中的a[5]=3,表示:如果系统拦截的最后一枚导弹是高度为299的话,最多可以拦截第1枚(389)、第4枚(300)、第5枚(299)三枚导弹。显然,a[1]~a[8]中的最大值就是第一问的答案。关键是怎样求得a[1]~a[8]?我们换一个角度,假设现在已经求得a[1]~a[7](注:在动态规划中,这样的假设往往是很必要的),那么怎样求a[8]呢?a[8]要求系统拦截的最后1枚导弹必须是65,也就意味着倒数第2枚被拦截的导弹高度必须不小于65,则符合要求的导弹有389、207、155、300、299、170、158。假如拦截的倒数第2枚导弹是300,则a[8]=a[4]+1;假如拦截的倒数第2枚导弹是299,则a[8]=a[5]+1;类似地,a[8]还可能是a[1]+1、a[2]+1、……。当然,我们现在要求得是以65结尾的最多导弹数目,因此a[8]要取所有可能值的最大值,即:a[8] = max{ a[1]+1,a[2]+1,……,a[7]+1} = max{a[i]} + 1 (i=1..7)。类似地,我们可以假设a[1]~a[6]为已知,来求得a[7]。同样,a[6]、a[5]、a[4]、a[3]、a[2]也是类似求法,而a[1]就是1,即如果系统拦截的最后1枚导弹是389,则只能拦截第1枚。“拦截导弹”问题分析