.第六章动态规划.ppt

文档介绍：§ 一般方法
多阶段决策过程:这样一类问题,它们的活动过程可以分为若干个阶段,而且在任意一阶段i,过程在阶段i以后的行为,仅依赖于i阶段的过程状态,而与i之前过程如何达到这种状态的方式无关,这样的过程就构成一个多阶段决策过程。
第六章动态规划
8/2/2018
1
在多阶段决策过程的每一阶段,都可能有多种可供选择的决策,必须从中选取一种决策。
各个阶段的决策选定之后,就构成了解决这一问题的一个决策序列。
决策序列不同,所导致的问题的结果也不同。

目标:在选择的决策序列中选取一个获得问题最优解的决策序列,即最优决策序列。
8/2/2018
2
选取最优决策序列的方法:
1. 枚举法
2. 动态规划方法:
在50年代,贝尔曼(Richard Bellman)根据这类问题的多阶段决策的特性,提出了解决这类问题的“最优性原理”(Principle of Optimality) ,从而创建了最优化问题的一种新的算法设计方法——动态规划。
利用最优性原理以及所获得的递推关系式去求取最优决策序列,可以使枚举量大大下降。
8/2/2018
3
最优性原理
过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么,其余的决策必须相对于初始决策所产生的状态构成一个最优决策序列。
用动态规划方法求解问题:
1. 判断对于所求解的问题最优性原理是否成立,如果成立则可能用动态规划方法来解决。
2. 获取个阶段间的递推关系式,这是解决问题的关键。
8/2/2018
4
多段图问题: 有向图G = (V, E)
8/2/2018
5
多段图是一个有向图G = (V, E), 具有如下性质:
V被划分为k  2个不相交的集合Vi, n Vi 1, 其中V1和Vk只有一个结点s (源点)和一个结点t (汇点);
每个集合Vi定义图中的一段;
边<u,v>具有如下性质,若uVi , 则v Vi1
每条边附有成本c(u,v).
4. 从s到t的一条路径成本是这条路上边的成本和
问题:求从s到t的最小成本路径
8/2/2018
6
证明最优性原理对多段图成立
证明:假设s,v2,v3,…,vk-1, t是一条由s到t的最短路径,并且假定从源点s(初始状态)开始,已作出了到结点v2的决策(初始决策),因此v2就是初始决策所产生的状态。
若把v2看成是原问题的一个子问题的初始状态,解这个子问题就是找出一条由v2到t的最短路径。这条最短路径显然是v2,v3,…,vk-1, t .
8/2/2018
7
(如若不然,设v2,q3,…,qk-1, t是一条由v2到t的更短路径,则s,v2,q3,…,qk-1, t是一条比路径s,v2,v3,…,vk-1, t更短的由s到t的路径,与假设矛盾)
因此,最优性原理对多段图成立。▌
可能考虑使用动态规划方法来解多段图问题。
8/2/2018
8
证明最优性原理对一个问题成立:
先设出最优决策序列;
找初始决策,初始决策所产生的状态;
证明其余决策针对于初始决策所产生的状态构成一个最优决策序列。
8/2/2018
9
0/,xi必须取0或1值,而条件及目标函数类同,则得到0/1背包问题。用KNAP(l, j, X)来表示:
极大化

约束条件

xi=0或1,l≤i≤j。
0/1背包问题就是KNAP(1, n, M)
8/2/2018
10