文档介绍：第十章 动态规划（DP） Dynamic Programming
§1 多阶段决策过程最优化问题（掌握）
§2 基本概念、基本方程与最优化原理
（掌握）
§3 动态规划应用（掌握）
动态规划是用来解决多阶段决策过程最此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。也就是说最优策略的任一个子策略也是最优的。
小结:
方程 :状态转移方程
概念 : 阶段变量k﹑状态变量sk﹑决策变量uk;
指标:
动态规划本质上是多阶段决策过程;
效益
指标函数形式:
和、
积
无后效性
可递推
解多阶段决策过程问题，求出
最优策略，即最优决策序列
f1(s1)
最优路线，即执行最优策略时的状态序列
最优目标函数值
从 k 到终点最优策略
子策略的最优目标函数值
§3 动态规划的应用
动态规划求解步骤：
1、确定问题的阶段和编号
2、确定状态变量 sk
3、确定决策变量 xk（用 xk*表示该阶段的最优决策）
4、确定状态转移方程
5、确定指标函数
例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
二、最短路径问题
解：整个计算过程分三个阶段，从最后一个阶段开始。
第三阶段（C →D）： C 有三条路线到终点D 。
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
显然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4
r( B1,C1 ) + f1 (C1 ) 3+1
f2 ( B1 ) = min r( B1,C2 ) + f1 (C2 ) = min 3+3
r( B1,C3 ) + f1 (C3 ) 1+4
4
= min 6 = 4
5
第二阶段（B →C）： B 到C 有六条路线。
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
B1
B2
(最短路线为B1→C1 →D)
r( B2,C1 ) + f1 (C1 ) 2+1
f2 ( B2 ) = min r( B2,C2 ) + f1 (C2 ) = min 3+3
r( B2,C3 ) + f1 (C3 ) 1+4
3
= min 6 = 3
5
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
B1
B2
(最短路线为B2→C1 →D)
第一阶段（ A → B ）： A 到B 有二条路线。
f1(A)1 = r(A, B1 )＋ f2 ( B1 ) ＝2＋4＝6
f1 (A)2 = r(A, B2 )＋ f2 ( B2 ) ＝4＋3＝7
∴ f1 (A) = min = min｛6,7｝=6
r(A, B1 )＋ f2 ( B1 )
r(A, B2 )＋ f2 ( B2 )
(最短路线为A→B1→C1 →D)
A
B1
B2
C1