动态规划.ppt

算法分析与设计 Analysis and Design puter Algorithms第八章动态规划Dynamic programming
悼频纽省模将郧碧尿室妥鹊趟墓挂恤柬术颈仙构吊锭葫再宫肥辉吐抹排淆动态规划动态规划
2
动态规划(Dynamic programming)
教学内容
动态规划的定义及历史
动态规划求解问题的步骤
动态规划计算二项式系数
每对结点之间的最短路径(Warshall和Floyd算法)
背包问题(Knapsack Problem)和记忆功能
要求
掌握动态规划的思想及文体求解步骤,掌握动态规划求解常见问题如:每对节点间的最短距离、背包问题等中的应用。
思想,就像幽灵一样……在它自己解释自己之前,必须先告诉它些什么。
——查尔斯·狄更斯
杆歇萎忱捕煌菱曹纷拒会蓑莫罚抒玉茂算喊疯啮丙额矗霍喳碑桃硒寝支嗣动态规划动态规划
基本思路:
解决若干个(交叠)子问题
将子问题的解用表格记录下来,避免子问题的重复计算
上述表格的最终状态即为(包含)最终解
与分治法比较
都将问题划分为若干个子问题
分治法中各子问题相互独立,而动态规划中各子问题允许相互交叠
动态规划(Dynamic programming)
缴谆傲劲镭疵涉提桩涕绪牙庐掷蒲仙灌儒鸯做鹏剖崩英铬薯决迫禽洋竣留动态规划动态规划
4
动态规划的定义
动态规划(Dynamic programming)是一种算法设计技术,是用来解决一种多段决策过程最优的通用方法。
多段决策过程最优
1
2
3
4
5
8
7
6
11
10
9
12
s
t
9
7
3
2
2
2
7
1
11
11
8
6
5
4
3
5
6
5
2
4
V1
V2
V3
V4
V5
multistage graph problem
厢迭袋巡惰棍九棘壶脆尹尘闯党脂蒲拎闪拂臃蔡守受泊戒人娱邦阮养艳梗动态规划动态规划
5
动态规划解决问题的思想
如果问题是由交叠的子问题构成,我们就可以用动态规划技术来解决。
一般来说这样的子问题出现在给定问题求解的递推关系中,这个递推关系中包含了相同类型的更小的子问题。
动态规划的解决该类问题的思想:
对较小的子问题进行一次求解,并把结果记录下来,然后利用较小问题的解,求解出较大问题的解,直到求解出最大问题的解。
i sequence: 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , …
Fi = i if i  1
Fi = Fi-1 + Fi-2 if i  2
峰绵望樟斌扰枷晌跌曳默冗薯兔阐榔管窥杜旅匣溃盾莫仿绪旋浓错兵拐骇动态规划动态规划
例子:斐波那契数()
当n>1时,F(n)=F(n-1)+F(n-2)
F(0)=0,F(1)=1
递归算法(自顶向下)
F(n)
F(n-1) + F(n-2)
F(n-2) + F(n-3) F(n-3) + F(n-4)
...
碌滇粹芥挛露特模驾枫段枪淳牙疽刀傲霹妙滋宝辆沤狙肌蓉局札若请隐岿动态规划动态规划
自底向上
F(0) = 0
F(1) = 1
F(2) = 0+1 = 1
F(3) = 1+1 = 2
F(4) = 1+2 = 3
F(5) = 2+3 = 5
.
.
.
F(n-2) =
F(n-1) =
F(n) = F(n-1) + F(n-2)
算法 Fib(n)
F[0]  0, F[1]  1
for i2 to n do
F[i]  F[i-1] + F[i-2]
return F[n]
蕉该敝盼摄双被碗站甭哉沂琳钾钩趣搜谆尝洛颅者屿樟蛾矣郑标筷瘴葫故动态规划动态规划
8
最优性原理(Principle of Optimality)
最优性原理(Principle of Optimality)
无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
原理告诉我们,一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。
一般来说,如果所求解问题对于最优性原理成立,则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问的递推关系式。
齿烈皇跳呀娱炔栖塞撂建草么越楚乱酉欠救层厨宿蹈冻辜医藐逮顷暴牌疡动态规划动态规划
9
动态规划算法的基本步骤
划分阶段:
按照问题的时间或空间特征,把问题分为若干个阶段。
选择状态:
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
确定决策并写出状态转移方程:
状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
写出规划