文档介绍：动态规划算法
Dynamic Programming
主要内容
动态规划的基本概念
动态规划的基本原理
动态规划的基本方法
动态规划的实例分析
基本概念
动态规划是解决多阶段决策的过程的最优化问题的一种方法。它把比较复杂的问题划分成若干阶段,通过逐段求解,最终求得全局最优解。
多阶段决策问题:可以分为若干个相互联系的阶段,在每一个阶段上都需要作出决策,而一个阶段的决策确定后,将会影响以后各阶段的活动及其策略。
动态规划的术语
阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,。在多数情况下,阶段变量是离散的,用表示。
动态规划的术语
状态:把一个阶段的过程在开始时所面临的状况,称为这个阶段过程的状态。状态的取值都有一个范围,称为状态集合。状态和状态集合都依赖于阶段,分别记为
和
动态规划的术语
动态规划的术语
决策:指一个阶段的状态确定以后,从该状态演变到下一阶段的,某一状态的一种选择。用来描述这种选择的变量称为决策变量。每一阶段的决策都依赖于该阶段的状态,用来表示第阶段的决策变量,则。决策变量允许选择的范围,称为允许决策集合,记为
动态规划的术语
动态规划的术语
策略:由各个阶段的决策组成的决策序列,称为一个全过程策略,简称策略。
状态转移方程:在确定性决策过程中,可以把状态,决策及下一段的状态对应关系表示为
动态规划的术语
动态规划的术语
指标函数:用以衡量、评价所选取的策略或子策略或决策的优劣程度或效果的数量函数。用表示第k阶段处于状态且所作决策为时的指标,简记为
目标函数:用表示的最优值,即
动态规划的术语
基本原理
适用的条件
最优化原理:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。
基本原理
基本思想
动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。
把一个多阶段决策问题转化为依次求解多个单阶段决策问题,从而简化计算过程。