noip普及讲座动态规划从搜索到动态规划.pptx

NOIP普及讲座动态规划从搜索到动态规划 NOIP普及讲座动态规划从搜索到动态规划 第1页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 引例（数塔问题） 设有一个三角形数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，能够向左走或向右走，从根结点13出发向左、向右路径长度能够是： 13－11－7－14－7，其和为52 13－11－12－14－13，其和为63 若要求从根结点开始， 请找出一条路径，使 路径之和最大,输出路 径长度。 NOIP普及讲座动态规划从搜索到动态规划 第2页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 引例（数塔问题） 【问题分析】 （1）贪心法 NOIP普及讲座动态规划从搜索到动态规划 第3页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 引例（数塔问题） 【问题分析】 （2）搜索： NOIP普及讲座动态规划从搜索到动态规划 第4页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 引例（数塔问题） 【问题分析】 （3）动态规划： NOIP普及讲座动态规划从搜索到动态规划 第5页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 引例（数塔问题） NOIP普及讲座动态规划从搜索到动态规划 第6页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 动态规划基础概念 （1）阶段：把所给问题过程，恰当地分为若干个相互联络阶段，方便能按一定次序去求解。 （2）状态：状态表示每个阶段开始所处自然情况和客观条件，它描述了研究问题过程中情况。 （3）决议：决议表示当过程处于某一阶段某个状态时，能够作出不一样决定（或选择），从而确定下一阶段状态，这种决定称为决议。 NOIP普及讲座动态规划从搜索到动态规划 第7页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 动态规划基础概念 （4）策略和最优策略：由全部阶段决议组成决议序列称为全过程策略，简称策略。 在实际问题中，从决议允许集合中找出最优效果策略称为最优策略。 （5）状态转移方程：状态转移方程是确定两个相邻阶段状态演变过程。 NOIP普及讲座动态规划从搜索到动态规划 第8页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 利用动态规划条件 （1）最优化 子问题局部最优将造成整个问题全局最优，即问题含有最优子结构性质。也就是说问题一个最优解中包含着子问题一个最优解。 （2）无后效性 当前阶段中状态只能由上一个阶段中状态转移方程得来，与其它阶段状态没相关系，尤其是与未发生阶段状态没相关系，这就是无后效性。 NOIP普及讲座动态规划从搜索到动态规划 第9页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 动态规划算法普通模式 （1）划分阶段：按照问题时间或空间特征，把问题分为若干个阶段； （2）确定状态和状态变量：将问题发展到各个阶段时所处各种情况用不一样状态表示出来； （3）确定决议并写出状态转移方程：普通是依据相邻两个阶段各状态之间关系来确定决议； （4）寻找边界条件：给出状态转移方程是一个递推式，必须有一个递推边界条件； （5）编写程序。 NOIP普及讲座动态规划从搜索到动态规划 第10页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 经典例题讲解 【例题1】拦截导弹（noi openjudge 8780） 问题描述： 某国为了防御敌国导弹攻击，发展出一个导弹拦截系统。不过这种导弹拦截系统有一个缺点：即使它第一发炮弹能够抵达任意高度，不过以后每一发炮弹都不能高于前一发高度。某天，雷达捕捉到敌国导弹来袭。因为该系统还在试用阶段，所以只有一套系统，所以有可能不能拦截全部导弹。 输入导弹依次飞来高度（雷达给出高度数据是小于30000正整数），计算这套系统最多能拦截多少导弹。 NOIP普及讲座动态规划从搜索到动态规划 第11页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 经典例题讲解 输入 第一行是一个整数N（不超出15），表示导弹数。 第二行包含N个整数，为导弹依次飞来高度（雷达给出高度数据是小于30000正整数）。 输出 一个整数，表示最多能拦截导弹数。 样例输入 8 389 207 155 300 299 170 158 65 样例输出 6 NOIP普及讲座动态规划从搜索到动态规划 第12页 点击添加文本 点击添加文本 点击添加文本 点击添加文本 经典例题讲解 【问题分析】 状态： f[i]代表打下第i颗导弹最多能打多少颗导弹 方程： f[i]=max(f[j])+1(1=ji)且第i颗导弹高度要高于第j颗导弹高度 NOIP普及讲座动态规划从搜索到动态规划 第13页 点击添