第三章 动态规划
动态规划是多阶段决策问题，相对地，线性规划、非线性规划问题称为静态规划问题。
§1 最优化原理
全局最优，则局部最优。（如何理解）
最短路问题
B E A F
22
b
2
① 1 3 2 7 3 4 6
e
c
② 7 a
5 ③ 1 ⑤ 3 ⑦ 6 f
d
8 ⑥ 2
u0 4 ④
g
4
货郎问题
设f(vi,V)表示从vi出发，经过V中的所有点恰一次后回到v0的最佳路线总长度，则所求的就是f(v0,{v1,v2,?,vn})。
?d01?f(v1,{v2,v3,?,vn}),??d?f(v2,{v1,v3,?,vn}),?f(v0,{v1,v2,?,vn})?min?02? ?,?d?f(v,{v,v,?,v})?n12n?1?0n??d12?f(v2,{v3,v4,?,vn}),??d?f(v3,{v2,v4,?,vn}),?f(v1,{v2,v3,?,vn})?min?13? ?,?d?f(v,{v,v,?,v})?n23n?1?1n?f(vi,V)?min?dij?f(vj,V?vj)?
vj?V例：
v0 v1 v3 v2
??d01?f(v1,{v2,v3}),??f(v0,{v1,v2,v3})?min?d02?f(v2,{v1,v3}),?
??d03?f(v3,{v1,v2})????d12?f(v2,{v3}),??f(v1,{v2,v3})?min??
??d13?f(v3,{v2})??
§2 用最优化原理解非线性规划问题
就下面的非线性规划问题，讨论最优化原理解题思想，并具
23
体求解该题
22?maxF?4x12?x2?2x3?12?t3x1?2x2?x3?9 ?s..?x1,x2,x3?0?f3(9)?max{2x32?12?f2(9?x3)}
0?x3?9f2(y)?max{?x22?f1(y?2x2)}
0?2x2?yf1(z)?max{4x12}
0?3x1?z
z2解得：f1(z)?4，故
9(y?2x2)2f2(y)?max{?x2?4}0?2x2?y927164?max{x22?yx2?y2}0?2x2?y999784?max{(x2?y)2???y2}0?2x2?y979?42y9
f3(9)?max{2x32?12?f2(9?x3)}0?x3?94?max{2x32?12?(9?x3)2}0?x3?99?max{0?x3?9222x3?8x3?12?36}92218(x3?)2??}911
?max{0?x3?9?17424
25
§3 动态规划算法设计
填表的思想及优势
fn=fn-1+fn-2 f100 f1=1 f2=1 1 1 2 3 5 8 13 21 ……..
1．博弈论中的一个问题
甲乙两人对弈，胜算概率相同，求“甲再胜i盘胜利，乙再胜j盘胜利”时甲胜利的概率。
i?0,j?0?1,?f(i,j)??0,i?0,j?0
?1[f(i-1,j)?f(i,j-1)],i?0,j?0?2 0 1 2 i
2．划分问题
用动态规划思想，设计填表法，求解下面的划分问题 在集合A＝｛a1，a2，?，an｝上定义正整数函数s，令
0 / 0 0 0 1 1 1/2 1/4 2 1 3/4 1/2 ? j 1 26