算法设计第三章 动态规划ppt课件.ppt

《算法设计第三章 动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一节主要内容动态规划的原理多阶段决策过程、特点及实例动态规划的术语最优值函数最优值基本方程最优性定理和基本方程最优性定理两种方式的动态规划动态规划求解的基本步骤动态规划实例计算动态规划特点、条件和步骤动态规划特点、适用条件和实例逆序、正序递推法的可归纳为以下四个步骤1教学目标动态规划的原理理解多阶段决策过程及特点理解动态规划的术语熟悉最优值函数、最优值基本方程最优性定理和基本方程充分理解最优性定理熟记、理解两种动态规划的基本方程掌握动态规划求解的基本步骤动态规划特点、条件和步骤熟记动态规划的适用条件熟记逆序、正序递推法的可归纳为以下四个步骤2动态规划的原理(多阶段决策问题)多阶

2、段决策过程多阶段决策过程是活动过程可按时间或空间顺序分解成若干相互独立、相互联系的阶段，在每个阶段的状态下做出决策，整个过程的决策构成一个决策序列，则称多阶段决策过程为序贯决策过程。称问题为多阶段决策问题。状态1状态2状态3状态4状态5决策2决策3决策4决策1多阶段决策问题的特点过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。3动态规划的原理(单源最短路径)第1阶段第2阶段第3阶段第4阶段状态1状态2状态4状态5状态3决策1决策2决策4决策3动态规划把多阶段过程的问题转化为一系列单阶段的问题，逐个阶段

3、求解的最优化数学方法。4动态规划的原理动态规划的术语阶段：将过程划分为k个阶段，1kn。状态：第k个阶段的状态变量为。为初态，为终态。状态集合：允许的取值范围，记为。决策：表示第k阶段状态的决策变量，简记为。允许决策集合：允许的取值范围。策略：一个按顺序排列的决策序列，记。状态转移方程：从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，记为。子策略：称决策序列为k子过程策略。简称子策略，记为5动态规划的原理当k=1时，成为全过程的一个策略，简称策略，简记为。阶段指标函数：指第k阶段从状态出发，采取决策时的效益，用表示。过程指标函数：从第k阶段的状态出发，采取子策略获得

4、最佳效益记为。最优性函数：若采用最优子策略，从第k阶段的出发获得最佳效益6动态规划的原理其中opt可根据具体情况取max或min。是可分函数，具有可加性或可乘性最优性基本方程7最优性定理和基本方程两种方式的动态规划初始状态出发到终止状态的正序寻优；从终止状态出发到初始状态逆序寻优。动态规划求解的基本步骤1.划分阶段2.定义决策变量，确定决策集合是最优策略的充要条件是：对任一k(1kn),当初状态为s1时,有即在最优策略，必然包含最优子策略。换句话说，问题的最优解必包含子问题的最优解。最优性定理8最优性定理和基本方程式中opt可根据题意取max或min。正序基本方程：此为逐段递

5、推计算的依据，一般为：式中opt可根据题意取max或min。逆序基本方程：此为逐段递推计算的依据，一般为：3.确定阶段指标函数4.建立状态转移方程5.确定过程指标函数6.建立递归方程9动态规划实例计算逆序递推计算方法(单源最短路径)用表示在第k阶段由初始状态到下一阶段的状态的距离。用表示从第k阶段的状态到终点E的最短距离。1．阶段k=4第4阶段有两个初始状态和。若全过程最短路径经过状态，则有=4；若全过程最短路径经过状态，则有=3。2．阶段k=3假设全过程最短路径在第3阶段经过状态，若由，则有。3．，及其它阶段的计算类似。，最短路径为。10动态规划特点、条件和步骤动态规划的适用条

6、件适用动态规划的问题必须满足以下三个条件最优化原理无后效性子问题的重叠性动态规划特点优点离散性问题：使解析数学无用武之地；建模：可用计算机计算；缺点无统一处理方法：需要数学技巧与解题经验；组合爆炸：只能解决中小规模的问题11动态规划特点、条件和步骤最优性定理（最优子结构性质）  一个最优性策略具有这样的性质：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优性原理又称其具有最优子结构性质。无后向性  将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，只能通过当前给定的状态，直

7、接影响未来的决策，而与以前各阶段的状态无关，这就是无后向性，又称为无后效性。换句话说，每个状态都是过去历史的一个完整总结。12动态规划特点、条件和步骤子问题的重叠性  动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度可能要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。举例1：求二项式系