算法设计第六章动态规划概要PPT课件

1 算法设计及其应用 第六章 动态规划算法 国际大学生程序设计竞赛辅导教程 国际大学生程序设计竞赛例题解 三 2 动态规划概述 运筹学 OperationsResearch 是系统工程最重要的理论基础之一 运筹学所研究的问题可简单地归结为 依照给定条件和目标 从众多方案中选择最佳方案 而动态规划是运筹学的重要分支之一 它是解决多阶段决策过程最优化的一种方法 3 动态规划概述 动态规划简单的来说就是 采用分治的策略把求最优解问题分解为求若干个子问题的最优解 子问题也递归的分解为子问题的组合 通过递归递推等方法 把原问题最优解与局部子问题最优解联系起来 以求最后的解 这些局部子问题之间可能有重叠 就是某个子问题可能需要求解多次 因此需要将子问题及其解记录下来 这样对每个子问题只需求解一次 从而提高了效率 4 动态规划概述 一般来说 寻找最优解的算法都具有指数时间的复杂度 因此算法的优化显得十分重要 但是有一类特殊的最优化问题 我们通常可以找到具有多项式时间的复杂度的算法 这种方法就是我们下面要介绍的动态规划 5 动态规划的常用名词 1 状态 state 对于一个问题 所有可能到达的情况 包括初始情况和目标情况 都称为这个问题的一个状态 2 状态变量 sk 对每个状态k关联一个状态变量sk 它的值表示状态k所对应的问题的当前解值 3 决策 decision 决策是一种选择 对于每一个状态而言 你都可以选择某一种路线或方法 从而到达下一个状态 6 动态规划的常用名词 4 决策变量 dk 在状态k下的决策变量dk的值表示对状态k当前所做出的决策 5 策略策略是一个决策的集合 在我们解决问题的时候 我们将一系列决策记录下来 就是一个策略 其中满足某些最优条件的策略称之为最优策略 7 动态规划的常用名词 6 状态转移函数 t 从一个状态到另一个状态 可以依据一定的规则来前进 我们用一个函数t来描述这样的规则 它将状态i和决策变量di映射到另一个状态j 记为t i di j 7 状态转移方程 f 状态转移方程f描述了状态变量之间的数学关系 一般来说 与最优化问题相应 状态转移方程表示si的值最优化的条件 或者说是状态i所对应问题的最优解值的计算公式 用代数式表示就是 si f sj dj i t j dj 对决策变量dj所有可行的取值 8 1951年美国数学家R Bellman等人 根据一类多阶段问题的特点 把多阶段决策问题变换为一系列互相联系的单阶段问题 然后逐个加以解决 一些静态模型 只要人为地引进 时间 因素 分成时段 就可以转化成多阶段的动态模型 用动态规划方法去处理 最优化原理 9 最优化原理 解决这类问题的 最优化原理 Principleofoptimality 一个过程的最优决策具有这样的性质 即无论其初始状态和初始决策如何 其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言 必须构成最优策略 简言之 一个最优策略的子策略 对于它的初态和终态而言也必是最优的 10 最优化原理 这个 最优化原理 如果用数学化一点的语言来描述的话 就是 假设为了解决某一优化问题 需要依次作出n个决策D1 D2 Dn 如若这个决策序列是最优的 对于任何一个整数k 1 k n 不论前面k个决策是怎样的 以后的最优决策只取决于由前面决策所确定的当前状态 即以后的决策Dk 1 Dk 2 Dn也是最优的 最优化原理是动态规划的基础 任何一个问题 如果失去了这个最优化原理的支持 就不可能用动态规划方法计算 11 何为动态规划 动态规划是运筹学的一个分支 与其说动态规划是一种算法 不如说是一种思维方法来得更贴切 因为动态规划没有固定的框架 即便是应用到同一道题上 也可以建立多种形式的求解算法 许多隐式图上的算法 例如求单源最短路径的Dijkstra算法 广度优先搜索算法 都渗透着动态规划的思想 还有许多数学问题 表面上看起来与动态规划风马牛不相及 但是其求解思想与动态规划是完全一致的 12 动态规划适于解决何种问题 只适于解决一定条件的最优策略问题 所谓 满足一定条件 主要指 1 状态必须满足最优化原理 2 状态必须满足无后效性 所谓的无后效性是指 过去的决策只能通过当前状态影响未来的发展 当前的状态是对以往决策的总结 这个特征说明什么呢 它说明动态规划适于解决当前决策和过去状态无关的问题 状态 出现在策略的任何一个位置 它的地位都是相同的 都可以实施同样的决策 这就是无后效性的内涵 13 动态规划适于解决何种问题 这个特征说明什么呢 它说明动态规划适于解决当前决策和过去状态无关的问题 状态 出现在策略的任何一个位置 它的地位都是相同的 都可以实施同样的决策 这就是无后效性的内涵 14 采用动态规划解题的优点 动态规划的最大优势在于它具有极高的效率 可获一系列解 算法清晰简便 程序易编易调等 15 动态规划的逆向思维法 逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法 如果原问题可以分解成几个本质相同 规模较小的问题 很自然就会联想到从逆向思维的角度寻求问题的解决 动态规划不是分治法 关键在于分解出来的各个子问题的性质不同 16 动态规划的逆向思维法 分治法要求各个子问题是独立的 即不包含公共的子子问题 因此一旦递归地求出各个子问题的解后 便可自下而上地将子问题的解合并成原问题的解 如果各子问题是不独立的 那么分治法就要做许多不必要的工作 重复地解公共的子子问题 动态规划与分治法的不同之处在于动态规划允许这些子问题不独立 即各子问题可包含公共的子子问题 它对每个子问题只解一次 并将结果保存起来 避免每次碰到时都要重复计算 这就是动态规划高效的一个原因 17 动态规划的逆向思维法 动态规划的逆向思维法的要点可归纳为以下三个步骤 1 分析最优值的结构 刻划其结构特征 2 递归地定义最优值 3 按自底向上或自顶向下记忆化的方式计算最优值 18 递归编程 动态规划算法经常使用递归编程来实现 所以理解好递归编程对掌握动态规划算法非常重要 我们先从一个例子讲起 例6 1 1 一个楼梯有20级 每次走1级或2级 从底走到顶一共有多少种走法 分析 假设从底走到第n级的走法有f n 种 走到第n级有两个方法 一个是从第 n 1 级走1步 另一个是从第 n 2 级走2步 前者有f n 1 种方法 后者有f n 2 种方法 所以f n f n 1 f n 2 另外f 0 1 f 1 1 编写递归程序如下 19 递归编程 includeintf intn if n 0 n 1 return1 elsereturnf n 1 f n 2 voidmain cout f 20 endl 20 递归编程 这个程序把计算f n 归结为f n 1 和f n 2 的计算 对简单的情况 即n为0或1的时候直接给出结果 但要理解好这个程序还必须了解程序变量的类型 简单的来分 变量分为局部变量和全局变量 局部变量在定义的时候分配在内存 在离开作用域的时候被撤销 而全局变量在程序的整个运行过程中都有效 在递归程序中尤其要注意局部变量和全局变量的区别 前者在每次递归调用的时候都会在内存分配不停的内存单元 并赋以不同的值 在递归函数调用结束后撤销该内存单元 后者在递归调用过程中始终只有一个内存单元 例如 以上程序中的n就是一个局部变量 每次递归调用f n 的时候 都会在内存分配n的新的内存单元 21 递归编程 把 程序6 1 1 改写为 includeintf intn intresult if n 0 n 1 result 1 inttemp1 f n 1 inttemp2 f n 2 result temp1 temp2 returnresult 22 递归编程 voidmain cout f 20 endl n result temp1 temp2都是局部变量 每次递归调用的时候都会在内存分配新的内存单元 计算f 20 和计算f 19 有不同的内存单元 赋以不同的值 互不影响 23 递归编程 在递归程序中使用全局变量的一个例子 includeintn intresult 计算给定的n值的函数值f n 并把结果存放在result变量里 调用函数前后n 值保持不变voidf if n 0 n 1 result 1 return 24 递归编程 inttemp n 计算f n 1 f temp result n 计算f n 2 f temp result 回复n值n 2 把结果存放到result变量 25 递归编程 下面再给出若干个递归程序 以增加对递归编程的理解 例6 1 2 输入n 输出前n个自然数的所有排列 例如输入3 则输出123132213231321312其实现见程序6 1 4 26 递归编程 includevoidswap int 27 递归编程 voidsolve intt if t n 输出一个排列for inti 1 i n i cout data i cout endl return 28 递归编程 voidmain cin n for inti 1 i n i data i i solve 1 29 递归编程 result temp voidmain n 20 cout result endl 30 递归编程 例6 1 3 计算两个自然数的最大公约数 其实现见程序6 1 5 includeintgcd intx inty returny 0 x gcd y x y voidmain intx y cin x y cout gcd x y endl 31 递归编程 例6 1 4 求若干个数的最大数 最简单的方法就是通过循环比较找出最大值 但我们也可以用递归的方法来求出最大值 其实现见程序6 1 6 32 递归编程 includeintdata 100 intgetMax intleft intright if left right returndata left intt1 getMax left left right 2 intt2 getMax left right 2 1 right returnt1 t2 t1 t2 33 递归编程 voidmain intn cin n for inti 1 i data i cout getMax 1 n endl 34 动态规划基本原理 动态规划的关键是发现子问题和怎么记录子问题 下面以 例6 1 1 为例加以说明 例6 1 1 的子问题就是 从底走到第n级的走法有多少种 即f n 原问题就是求f 20 我们来分析一下这些子问题 35 动态规划基本原理 对这些子问题可递归的求解 即当n 1时 f n f n 1 f n 2 否则 f 0 1 f 1 1 这些子问题是有重叠的 即求解某个问题的时候 某些子问题可能需求求解多次 例如 我们在求解f 5 的时候 其问题求解树为 36 动态规划基本原理 图6 2 1例6 1 1的求解树 37 动态规划基本原理 很多子问题被重复的求解 例如f 2 被求解了3次 当某个问题符合以上两点 我们就可以考虑用动态规划的方式来高效地求解 就是把子问题及其解记录下来 这样每个子问题只需求解一次 从而提高了效率 下面我们直接给出两个用动态规划方法求解 例6 1 1 的程序 38 动态规划基本原理 include 用于保存f n 的结果intresult 100 求解f n intf intn 如果问题已经被求解 那么之间返回结果if result n 0 returnresult n 39 动态规划基本原理 计算解并把结果保存到result n 里intres if n 0 n 1 res 1 elseres f n 1 f n 2 result n res returnres 40 动态规划基本原理 include 用于保存f n 的结果intf 100 voidmain 先置初始解f 0 1 f 1 1 41 动态规划基本原理 递推的求解各个子问题for inti 2 i 20 i f i f i 1 f i 2 输出解cout f 20 endl 42 动态规划基本原理 程序6 2 1 采用递归的结构 每当遇到一个子问题 先判断该子问题是否已经被求解过 如果是 则直接返回已经记录下来的结果 否则才递归的求解下去 最后把结果保存起来 这样下次就不用再求解了 程序6 2 2