文档介绍：第四章动态规划
一般方法
1. 多阶段决策问题
多阶段决策过程:问题的活动过程分为若干相互联系的阶段,任一阶段i以后的行为仅依赖于i阶段的过程状态,而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策,这一系列的决策称为多阶段决策过程(multistep decision process) 。
最优化问题:问题的每一阶段可能有多种可供选择的决策,必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同,所导致的问题的结果可能不同。
多阶段决策的最优化问题就是:求能够获得问题最优解的决策序列——最优决策序列。
本章教学要求及重点难点
理解动态规划的基本思想;
掌握动态规划的一般方法求最优二分检索树;
掌握0/1背包问题的求解方法;
掌握货郎担问题的求解方法。
重点:最优二分检索树和0/1背包问题的求解方法;
难点:用动态规划法求解货郎担问题并分析其时间复杂度。
2. 多阶段决策过程的求解策略
1)枚举法
穷举可能的决策序列,从中选取可以获得最优解的决策序列
2)动态规划
,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,创立了解决这类过程优化问题的新方法——动态规划。
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
应用领域:动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。
3. 最优性原理(Principle of Optimality)
过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
利用动态规划求解问题的前提
1) 证明问题满足最优性原理
如果对所求解问题证明满足最优性原理,则说明用动态规划方法有可能解决该问题
2) 获得问题状态的递推关系式
获得各阶段间的递推关系式是解决问题的关键。
[多段图问题]多段图G=(V,E)是一个有向图,且具有特性:
结点:结点集V被分成k≥2个不相交的集合Vi,1≤i≤k,
其中V1和Vk分别只有一个结点s(源点)和t(汇点)。
· 每一集合Vi定义图中的一段。
边: 所有的边(u,v)均具有如下性质: 若<u,v>∈E,则
该边将是从某段i指向i+1段,即若u∈Vi,则v∈Vi+1,
1≤i≤k-1。
· 每条边(u,v)均附有成本c(u,v)。
s到t的路径:从第1段开始,至第2段、第3段、…、最后
在第k段终止。路径的成本是这条路径上边的成本
和。
多段图问题:求由s到t的最小成本路径。
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1
V2
V3
V4
V5
5段图
多段图问题的多阶段决策过程:生成从s到t的最小成本路径是在k-2个阶段(除s和t外)进行某种决策的过程:从s开始,第i次决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。
最优性原理对多段图问题成立
假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径。
●初始状态:s
●初始决策:(s,v2), v2∈V2
●初始决策产生的状态:v2
则,其余的决策:v3,...,vk-1相对于v2将构成一个最优决策序列——最优性原理成立。
反证:若不然,设v2,q3,…,qk-1,t是一条由v2到t的更短的路径,则s, v2,q3,…,qk-1,t将是比s,v2,v3,…,vk-1,t更短的从s到t的路径。与假设矛盾。
故,最优性原理成立
[0/1背包问题] KNAP(l,j,X)
目标函数:
约束条件:
0/1背包问题:KNAP(1,n,M)
最优性原理对0/1背包问题成立:
设y1,y2,…,yn是x1,x2,…,xn的0/1值最优序列。
若y1=0, KNAP(2,n,M)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M)将构成一个最优序列。否则,y1,y2,…,yn将不是KNAP(1,n,M)的最优解
若y1=1, KNAP(2,n,M-w1)是初始决策产生的状态。则y2,…