算法分析与设计第4章ppt课件.ppt

《算法分析与设计第4章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、适用条件多阶段决策过程实际问题中,常有这样一类活动,它们的活动过程可以分为若干个阶段，而且在任一阶段i后的行为都依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。当各个阶段决策确定后，就组成了一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联的具有链状结构的多阶段过程被称为多阶段决策过程.满足最优性原理第四章动态规划4．1方法概述状态0决策1决策2……决策n状态n状态1状态n-1状态2最优性原理：过程的最优决策序列具有如下性质：无论过程的初始状态和

2、初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果所求解问题的最优性原理成立，则说明用动态规划方法有可能解决该问题。因为只有满足最优性原理，才能使用各阶段的递推公式求解。二、最优性原理在多阶段决策过程的每一阶段，都可能有多种可供选择的决策，但必须从中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一个决策序列，决策序列不同，所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。三、动态规划

3、方法的关键关键在于获取各阶段间的递推关系式。四、可解决的问题最短路径问题、设备更新问题、资源分配问题、货物装运排序、生产计划等。五、应用实例分析例4.1[多段图问题]多段图G=（V，E）是一个有向图。它具有如下特性：图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k，其中V1和Vk分别有一个结点s（源点）和t（汇点）。图中所有的边(u,v)均具有如下性质：若u∈Vi，则v∈Vi+1，1≤i＜k-1,且每条边(u,v)均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求由s

4、到t的最小成本路径。每个集合Vi定义图中的一段。由于E的约束，每条从s到t的路径都是从第1段开始，在第k段终止。图4.1所示的就是一个5段图。123456789101112ts97322271111815435642546对于每一条由s到t的路径，可以把它看成在k-2个阶段中作出的某个决策序列的相应结果。第i次决策就是确定Vi+1中的哪个结点在这条路径上，1≤i≤k-2。下面证明最优性原理对多段图成立。假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径，还假定从源点s（初始状态）开始，已作出了到结

5、点v2的决策（初始决策），因此v2就是初始决策所产生的状态。如果把v2看成是原问题的一个子问题的初始状态，解这个子问题就是找出一条由v2到t的最短路径。这条最短路径显然是v2,v3,…,vk-1,t，如若不然，设v2,q3,…,qk-1,t是一条由v2到t的更短路径，则s,v2,q3,…,qk-1,t是一条比路径s,v2,v3,…,vk-1,t更短的由s到t的路径。与假设矛盾，故最优性原理成立。因此它为使用动态规划方法来解决多段图问题提供了可能。六、动态规划方法的形式化描述能用动态规划求解的问题的最优化决策

6、序列可表示如下。设S0是问题的初始状态。假定需要作n次决策xi,1≤i≤n。设X1={r1,1,r1,2,…,r1,p1}是X1的可能决策值的集合，而S1,1是在选取决策值r1,j1以后所产生的状态,1≤j1≤p1。又设是相应于状态S1,j1的最优决策序列。那末，相应于S0的最优决策序列就是{

7、1≤j1≤p1}中最优的序列，记为OPT{}=。如果已作了k-1次决策，1≤k-1＜n。设x1,…,xk-1的最优决策值是r1,…,rk-1，它们所产生的状态为S1,…,Sk-1。又设是xk的可能值的集合。是选取决策

8、值后所产生的状态，1≤jk≤pk。是相应于的最优决策序列。因此，相应于Sk-1的最优决策序列是。于是相应于S0的最优决策序列为r1,…,rk-1，rk，。七、两种求解方法（1）向前处理法：从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策序列来列出求取xi决策值的关系式，即：xi=f(xi+1,xi+2,…,xn)例子：在k段图问题中，设又设是由到t的最短路径，则s到t的最短路径是中最短的那条路径。若设是s到t的一条最短路径，是路径上的中间结点，则就

9、应分别是由s到vi和由vi到t的最短路径。（2）向后处理法：根据x1,…,xi-1的那些最优决策序列列出求xi的递推关系式。即：xi=f(x1,x2,…,xi-1).下例是说明向前处理法在多段图中的使用见黑板小结：无论是使用向前处理法还是使用向后处理法，都将所有子问题的最优解保存下来。这样做的目的是为了便于逐步递推得到原问题的最优解并避免对它们的重复计算。由枚举法可知，不同决策序列的总数就其所取决策值而言是指数级