文档介绍：第 7 章
Dynamic Programming
DP
动态规划
冶戳埃状贝崔碴蚜距宫抛侩譬啸朴箍基狠担犬捣螟各迷腾防掐曰暇霄郭饰07-动态规划07-动态规划
1
第7章动态规划
引言
基本概念
离散确定型典例
其他典例
第7章动态规划
蛛粳某噶波缀此禽枪靳锦谓饼翼光圆掐秩颇毖筐煌鬃防铜键儒郸抱骋角绰07-动态规划07-动态规划
2
第7章动态规划
…
S’k+1
…
…
S2
. 1 多阶段决策问题
阶段、决策、策略
. 2 动态规划的基本特性
一、多阶段决策问题的基本特性
引言
Sk
Sk+1
Sn
T
S’n
Q = S1
反证法容易得证。
若{S2 , …, Sk , Sk+1 , …, Sn , T} 全程最优
则{Sk+1 , …, Sn , T} 子程最优
鹅太帽扯疙畔杉忌幸超窥丘阴肯谎俘枉汲鸳颜暴碗份铃无添烬壮跪贺县浙07-动态规划07-动态规划
3
第7章动态规划
引言
二、动态规划方法的基本思路
例1 最短路问题
1
2
3
4
3
4
0
4
7
6
11
7
8
11
阶段
A1
2
4
3
7
4
6
3
2
4
4
1
5
1
4
6
3
3
3
3
4
A3
B1
Q
A2
B2
B3
T
C1
C2
——标号法
烧豌转喷艘臣戈蚀罗洼忻书摘郑懈嗡顶钝凿娃贷奠葬笆弗喘一院狱昔迪丈07-动态规划07-动态规划
4
第7章动态规划
三、决策
是指人们对某一阶段活动中各种不同的行为或方案或途径等的
一种选择。
用xk表示第k段的决策,称为第k段决策变量。由于决策随状态
而变,所以决策变量xk是状态变量sk的函数,记为 xk= xk(sk)
基本概念
动态规划的基本概念
一、阶段
把所研究的问题恰当的划分成若干个相互联系的阶段。用
k = 1,2,…,n 表示阶段序号,称为阶段变量。
二、状态
状态表示某段的初始条件。用sk表示第k段的状态,称为第k段
状态变量。
sk∈Sk
∈Xk
诬蛋丧肩渊娘柜腋骋谚弟囚掉跳振能便焙起携湍戈桅堡囱馅时滑狈版寄夕07-动态规划07-动态规划
5
第7章动态规划
基本概念
四、状态转移方程
sk+1与sk,xk之间必须能够建立一种明确的数量对应关系,记为
Tk(sk,xk), 即有
sk+1 = Tk(sk,xk)
这种明确的数量关系称为状态转移方程。
五、策略
由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为
p1(s1),有
p1(s1) = { x1(s1),x2(s2),…,xn(sn)}
pk(sk) = { xk(sk),xk+1(sk+1),…,xn(sn)} ∈Pk
称为第k子过程策略,简称子策略。
∈P1
而
契醒胸烁踢拌漓胆厌猩蝉竹励咕学衙漂格貉秆言印队烁带榆泼斑整大灸擂07-动态规划07-动态规划
6
第7章动态规划
基本概念
六、指标函数
(1) 阶段指标函数
用vk(sk,xk)表示第k段处于sk状态且所作决策为xk
时的指标,则它就是第k段指标函数,简记为vk。
∈P1
(2) 过程指标函数
用fk(sk,xk)表示第k子过程的指标函数。
它是各vk的累积效应。
常用函数:
fk(sk,xk) = vi(si,xi)
n
i= k
fk(sk,xk) = vi(si,xi)
n
i= k
积函数
和函数
演饭呛芽陆刃苞梭过铬洞写墩占懒端蹈堆臼曙粗豆涡数憾逝兑蜜妖储接袁07-动态规划07-动态规划
7
第7章动态规划
七、最优解
(1) 最优指标函数
fk*(sk) = opt {fk(sk, pk(sk))}, k=1,2,…,n pk∈Pk
(2) 最优策略
能使上式成立的子策略pk*称为最优子策略,记为
pk* (sk) = { xk*(sk),…,xn*(sn)}
特别当k=1时,称为最优策略,记为
p1* (s1) = { x1*(s1),…,xk*(sk),…,xn*(sn)}
(3) 最优决策
构成最优策略的决策称为最优决策,记为xk*。
(4) 最优值:最优策略对应的最优指标 f *1
基本概念
弹捐媳烹济馅痹赁御辈碎悔卧四睫弥圣蹿吊珐蓑畴万腔潘灯匿聊诣椎茂罗07-动态规划07-动态规划
8
第7章动态规划
基本概念
动态规划的基本方程
一、最优化原理
作为一个全过程最优策略具有这样的性质: