动态规划课件.ppt

D D ynamic ynamic P P rogramming rogramming DP DP 动动态态规规划划 2 引言 基本概念 离散确定型典例 其他典例动态规划 3… S’ k+1 …… S 2 . . 1 1多阶段决策问题多阶段决策问题阶段、决策、策略 . . 2 2动态规划的动态规划的基本特性基本特性一、多阶段决策问题的基本特性基本特性 引言 S kS k+1 S nTS’ n Q=S 1反证法反证法容易得证。若{S 2 ,…,S k, S k+1 ,…,S n,T}全程最优则{S k+1 ,…,S n,T}子程最优 4 引言二、动态规划方法方法的基本思路基本思路例1最短路问题 1 12 23 34 4 34 0 476 11 78 11 阶段阶段 A 1243 746324415 146333 34 A 3B 1Q A 2B 2B 3T C 1C 2 ——标号法标号法 5三、决策是指人们对某一阶段活动中各种不同的行为或方案或途径等的一种选择选择。用x k表示第 k段的决策,称为第 k段决策变量。由于决策随状态而变,所以决策变量 x k是状态变量 s k的函数,记为 x k=x k (s k) 基本概念 . . 1 1动态规划的动态规划的基本概念基本概念一、阶段把所研究的问题恰当的划分成若干个相互联系的阶段。用 k = 1,2,…, n 表示阶段序号,称为阶段变量。二、状态状态表示某段的初始条件。用 s k表示第 k段的状态,称为第 k段状态变量。s k∈S k∈X k 6 基本概念四、状态转移方程 s k+1 与s k,x k之间必须能够建立一种明确的数量对应关系,记为 T k(s k,x k), 即有 s k +1 =T k(s k,x k) 这种明确的数量关系称为状态转移方程。五、策略由各阶段决策 x k构成的决策序列,称为全过程策略全过程策略,简称策略,记为 p 1(s 1),有p 1(s 1) = { x 1(s 1),x 2(s 2),…,x n(s n)} p k(s k) = { x k(s k),x k+1 (s k+1 ),…,x n(s n) } ∈P k 称为第第k k子过程策略子过程策略,简称子策略。∈P 1 而 7 基本概念六、指标函数(1 ) 阶段指标函数用v k(s k,x k)表示第 k段处于 s k状态且所作决策为 x k 时的指标,则它就是第k段指标函数,简记为 v k。∈P 1 (2 ) 过程指标函数用f k(s k,x k)表示第k子过程的指标函数。它是各 v k的累积效应。常用函数常用函数:f k (s k,x k ) = v i (s i,x i) n? i= kf k (s k,x k ) = v i (s i,x i) n? i= k 积函数积函数和函数和函数 8 七、最优解(1)最优指标函数 f f k k * *( (s s k k) )= opt { f k(s k,p k(s k))}, k=1,2,…,np k∈P k (2)最优策略能使上式成立的子策略 p p k k * *称为最优子策略最优子策略,记为 p p k k * *( (s s k k) )= { x k *(s k),…,x n *(s n)} 特别当 k=1 时,称为最优策略最优策略,记为 p p 1 1 * *( (s s 1 1) )= { x 1 *(s 1),…,x k *(s k),…,x n *(s n)} (3)最优决策构成最优策略的决策称为最优决策最优决策,记为x x k k * *。(4)最优值:最优策略对应的最优指标 f f * *1 1 基本概念 9 基本概念 . . 2 2动态规划的动态规划的基本方程基本方程一、最优化原理作为一个全过程最优策略具有这样的性质性质: 无论过去的状态和决策如何,对前面所形成的状态而言, 余下的诸决策必构成最优策略余下的诸决策必构成最优策略。。二、函数基本方程 f *n+1(s n+1)= 0 f *k(s k)= opt {v k(s k,x k)+f k+1 *(s k+1)} x x k k∈∈X X k kf * n+1 (s n+1 ) = 1 f *k(s k)= opt { v k(s k,x k)×f k+1 *(s k+1)} x x k k∈∈X X k k和和积积 k=n, n-1, …, 2, 1k=n, n-1, …, 2, 1 10 基本概念 . . 3 3 动态规