文档介绍：Yunchouxue
第七章动态规划
1
以最短路问题为例,来说明动态规划的概念
B1
B2
A
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
5
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
A
B
C
D
E
F
2
一、动态规划基本概念:
1、阶段:
将所要研究的问题,“阶段”。
阶段就是作出决策的若干轮次。描述阶段的变量叫阶段变量,=1,2,3,4,5。
3
2、状态及性质
,常用sk表示第k阶段的状态变量, sk的取值集合称为状态集合,用Sk表示。
阶段的出发位置,即阶段的起点。
上例中,第二阶段有两个状态,即Sk= {B1,B2}
动态规划中状态具有以下性质:某阶段状态一旦确定,以后过程的状态变化不受这个状态以前的影响,也就是说某状态以后的过程和以前无关,只与当前状态有关,我们称这种特性为“无后效性.”(即马尔科夫性。)P194
4
3、决策和策略
指从一个阶段某状态演变到下一阶段某状态的选择(决定)称为决策。
表示决策的变量叫做决策变量,常用uk(sk).
在实际问题中决策变量的取值往往限制在一定的范围内,我们称此范围为允许决策集,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集,因此有uk(sk) ∈Dk(sk).
在例1中D2(B1)={C1,C2,C3} .
5
策略
在例1中 D2(B1)={C1,C2,C3}.表示什么?
表示从第二阶段的状态B1出发,可选择下一阶段的{C1 ,C2,C3}。即允许决策集是D2(B1).如果我们决策选择了C3,则u2(B1)=C3.
全过程中各个阶段的决策组成的有序总体称为策略。
上例中每一条路线都被称为一个策略。
,路最短的策略就是最优策略。
6
状态转移方程
,本阶段的决策就为uk(sk),则第k+1段的状态uk+1也就完全确定了,它们的关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到k+1段的状态转移规律,所以称为状态转移方程.
即前一阶段的终点(决策)是后一阶段的起点(状态)。
例1的转移方程为:sk+1 =Tk(sk,uk) =uk(sk).
7
指标函数
用于衡量所选定策略优劣的数量指标称为指标函数.
一个n段决策过程,从1到n叫作问题的全过程,对于任意一个给定的k ,从第k 。常用Vk,n表示,
即Vk,n= Vk,n(sk, uk, sk+1,… sn+1),k=1,2,…n
指标函数的最优值称为最优指标函数,记为fk(sk),它表示从第k阶段状态sk开始到第n阶段的终止状态的过程,采取最优策略所得到的指标函数值。即fk(sk)=optVk,n(sk,pk,n), fk(sk)可能是最大值,也可能是最小值,依题意而定。
当k=1时F1(s1)就是从初始状态到全过程的整体最优函数.
8
指标函数的常见形式:
(1)过程和它的任一子过程的指标是它所包含的各阶段的指标的和。
(2)过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。
指标函数应具有可分离性,并满足递推关系。vj(sj,uj)表示第j阶段的指标,则1,2式分别写为:
Vk,n(sk, uk, sk+1,… sn+1)= vk(sk,uk)+ Vk+1,n(sk+1, uk+1, sk+2,… sn+1)
Vk,n(sk, uk, sk+1,… sn+1)= vk(sk,uk) Vk+1,n(sk+1, uk+1, sk+2,… sn+1)
Vk,n(sk, uk, sk+1,… sn+1)=
Vk,n(sk, uk, sk+1,… sn+1)=
1
2
1`
2`
9
回到例1
,状态为B1时,V2,5(B1)表示从B1到F的距离,而f2(B1)则表示从B1到 F的最短距离.
该问题总目标是求f1(A),即从A到终点F的最短距离.
B1
B2
A
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
5
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2