第七章 动态规划.ppt

第七章动态规划
动态规划简介
届鸭仗项幕惫涵陛耕蹲膊绒宠遵怔畸闽藻名掩渤唤壶唯鸥梧摸劝钒繁敏又第七章动态规划第七章动态规划
多阶段决策过程最优化
多阶段决策过程,是指一类特殊的过程,它们可以按时间顺序分解成若干个相互联系的阶段,称为“时段”,在每个时段都要做决策,全部过程的决策是一个决策序列。多阶段决策问题也称为序贯决策问题。
多阶段决策问题的目标是要达到整个活动过程的总体最优。在每个阶段进行决策时不应仅考虑本阶段最优,尤其应考虑对最终目标的影响,从而做出对全局来说最优的决策。
动态规划是符合这种要求的一种决策方法。
哀瘟菇豆翟鸟跃堪尊距汾孪兼啪无床笺即肚曳诚批描后悉坟诺九然蔽勿猛第七章动态规划第七章动态规划
第 1 阶段
第 2 阶段
第 n阶段
决策
决策
决策
多阶段决策过程图示
晾挪氨柏爆氢惭坝绵佩靡嫂谨囚久酶皑寞抚亿必迫舌僵盒癌奸尊颂雪谦惯第七章动态规划第七章动态规划
动态规划的基本概念
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
阶段: k=1,2,3,4,5
1
2
3
4
5
衫她嘴角绪唆椎逻窍锐酒斩驰络龟镑爵霞至慈顿慌勃运氨茅拿挤捞用孔发第七章动态规划第七章动态规划
基本概念(续一)
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
状态:各阶段开始时的客观条件。表示状态的变量称为状态变量,常用sk表示第k阶段的状态变量,第k阶段所有状态变量的集合记为Sk。
躁末掳烁坎碎从洱挞违圾俐怯有铃必篮眉穷帮酶司擞刁槛拭循忘疽镊徊羞第七章动态规划第七章动态规划
基本概念(续二)
决策:当一个阶段的状态取定了后,就可以作出不同决定(或选择),从而确定下一阶段的状态,这种决定称为决策。
表示决策的变量称为决策变量,uk(sk)就表示第k阶段当状态为sk时的决策变量。
决策变量的取值常常限制在一定的范围内,这一范围称为允许决策集合,常用记号Dk(sk)表示第k阶段状态为sk时的允许状态集合。
订斤彬荔镑皮躬讥馈芬策渭叛豫绩偶粒顿芳咽碾决柒秃竿幕坠俏鸡灰章气第七章动态规划第七章动态规划
基本概念(续三)
各阶段的决策确定后,整个过程各阶段的决策就构成一个决策序列,称为策略,用p1,n{u1(s1), u2(s2), …, un(sn)}表示。
有时还需要考虑后部子策略pk,n{uk(sk), …, un(sn)}。
动态规划要求的就是使整个问题达到最优的策略。
竞谴浙耀风盎捡宛陷佯坪急拎画谆茂干偶匆窖绕撤嚎短绞徒佩惊智瞎厘大第七章动态规划第七章动态规划
基本概念(续四)
状态转移方程:动态规划中一个阶段的状态常常是上一阶段的状态和决策的结果。如果给定了第k阶段的状态sk,和第k阶段的决策uk(sk),则第k+1阶段的状态sk+1也就完全确定了,这一关系可用下面的方程表示
sk+1=Tk(sk, uk)
称之为状态转移方程,它表示了由第k阶段到第k+1阶段状态转移的规律
候掺忌凸季拱阀垣念显瞥认彩解通臭淮酌杭吊涛状貌怎绵钨照溅拐畜偿牡第七章动态规划第七章动态规划
基本概念(续五)
指标函数:用于衡量决策或策略优劣的数量指标称为指标函数。
阶段指标函数:它通常是指在第k阶段,从状态sk出发,采用决策uk时的效益,记为d(sk, uk)。
过程指标函数:它通常表示在第k阶段时的状态为sk时,采用后部子策略pk,n的效益值,记为Vk,n(sk, pk,n)。最优指标函数记为fk(sk),表示第k阶段的状态为sk时,采用了最优后部子策略p*k,n的指标函数值, Vk,n(sk, pk,n)与fk(sk)的关系是
噶欲骋训缩学钙绑纳法较皱喻点鹿修族隘见悬延眨坦荫迄具疑渝刊朝凯颓第七章动态规划第七章动态规划
f1(s1)就是从初始状态s1到全过程结束的整体最优函数。
对最短路线问题阶段指标函数就是两点间的距离。后部子过程pk,n的指标函数Vk,n(sk, pk,n)就是在第k阶段位于点sk时到终点的距离,而fk(sk)就是到终点的最短距离。
最短路线问题,就是要求f1(A)以及相应的路线。
吵成筐普榷闺气佰布狄原性踊委愚氢涎找度裸眷臂藩短端畅壮柠吭偏橙他第七章动态规划第七章动态规划