动态规划.ppt.ppt

§ 动态规划
动态规划是一类多阶段决策过程的最优化方法。
基本方法是:按阶段把一个大问题化成一系列相互有联系的子问题,建立相应的递推公式,解一系列的子问题,最后求得整个问题的最优解。
例最短路问题
一、动态规划的基本概念和基本方法
7
11
7
8
4
6
3
4
0
11
1
2
3
4
阶段
从A到E的路有:
求A到E的最短路。
4
5
7
8
9
10
12
13
1. 概念
•阶段:
根据时间或空间划分。
•状态:
某阶段出发的位置。
既是某支路本阶段的起点,又是前一阶段的终点。
本例按空间分成4个阶段
本例4个阶段的状态集:
•状态变量 sk :
描述状态的变量。
#
•决策:
从给定状态到下一阶段某状态的选择。
•决策变量 xk=xk(sk):
描述决策的变量。
如:
有:
容许决策集合
•状态转移方程:描述状态转移规律的函数关系
•策略:决策序列
2
4
如:
本例共有18个策略,欲从中选出最优策略(路长最短者)。
• k 子策略:
策略中,从第k个决策开始到最后一个决策所成之子序列。
如:
•报酬函数: 一决策对应的“费用”,记为
如:
2
5
•目标(指标)函数:衡量策略好坏的函数。
从出发到终点的目标函数记为:
视为确定状态, 是变化的。
•从出发到终点的最优目标值:
例中:
为A 到E 的最短路程,
相应的策略为所求的最优策略—最短路。
对应的策略为到终点最优子策略。
2
6
2. 最优化原理
例中:有最优策略
即
—A到E的最短路,路长为
子策略:
— B2到E的最短路,路长为
— C1到E的最短路,路长为
……
2
7
#
最优策略有性质—最优化原理:
无论过去的状态和决策如何,对某确定的状态,余下的决策必须构成最优子策略。
或,对某状态而言,该状态到终点的最优策略只与后面的选择有关,与前面的选择无关。
或,已知现在,将来与过去无关。
即后部子问题的最优策略是父问题的最优子策略。
2
8
#
利用该原理得寻优方法:
问题:
子问题:
行进方向
寻优方向
先求出“最小子问题”中,各状态到E的最优子策略,
将问题化成一系列相互有联系的子问题,
再求出“次小子问题”中(第3阶段),各状态到 E的最优子策略,如此向前推进,而每次都利用后部子问题中已得到的最优子策略。
如:已得C1到E的最优子策略:
在求B2到E的最佳走法时,如果该阶段取
2
9
则后面的最佳走法是:
即得最优子策略:
在第1阶段,若取,则得A到E的最佳走法:
如果是,则利用B1到E的最佳走法得:
或
•减少了计算量,即不必再验证后面走法的最优性;
•丰富了结果,即得从任何一点出发到终点的最短路。
2
10