第3章动态规划2016ppt课件.ppt

《第3章动态规划2016ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章动态规划动态规划算法的基本要素举例1矩阵连乘问题举例2凸多边形最优三角剖分举例3最长公共子序列举例4多段图的最短路径问题举例50-1背包问题举例6资源分配问题1多阶段决策问题多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程(multistepdecisionprocess)。最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。多阶段决策的

2、最优化问题：求能够获得问题最优解的决策序列——最优决策序列。21）枚举法穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法——动态规划。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的

3、应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。多阶段决策过程的求解策略10/7/20213多阶段决策问题多阶段决策过程多阶段决策过程是活动过程可按时间或空间顺序分解成若干相互独立、相互联系的阶段，在每个阶段的状态下做出决策，整个过程的决策构成一个决策序列，则称多阶段决策过程为序贯决策过程。称问题为多阶段决策问题。状态1状态2状态3状态4状态5决策2决策3决策4决策1多阶段决策问题的特点过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。10/7/20214

4、第1阶段第2阶段第3阶段第4阶段状态1状态2状态4状态5状态3决策1决策2决策4决策3动态规划把多阶段过程的问题转化为一系列单阶段的问题，逐个阶段求解的最优化数学方法。10/7/20215动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题。nn/4n/4n/4n/4区别：经分解得到的子问题往往不是互相独立的。问题：用分治法求解，有些子问题被重复计算多次。6保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算，从而得到多项式时间算法。这就是动态规划算法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免

5、了重复计算。解决方法7算法设计与分析8动态规划的基本要素最优子结构：问题的最优解是由其子问题的最优解所构成的。重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。找出最优解的性质，并描述其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。步骤1~3是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。动态规划算法的基本步骤9算法

6、设计与分析10动态规划的备忘录方法动态规划中采用自底向上的方式。但是在递归定义中往往是自上而下的描述。备忘录方法就采用与递归定义一致的自上而下的方式。备忘录方法同样用表格来保存已解子问题的信息。每个子问题初始化时都标记为尚未求解。在递归求解过程中，对每个待解子问题，先查看它是否已求解。若未求解，则计算其解并填表保存。若已求解，则查表取出相应的结果。备忘录方法同样避免了子问题的重复计算，因而和动态规划算法具有同样效率。动态规划算法举例1：矩阵连乘问题给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的。由于乘法满足结合律，故计算矩阵的连乘可以有不同的计算次序。其计算次序可以用加

7、括号的方式确定。假设有4个矩阵：A,B,C,D乘法：16000乘法：10500乘法：36000乘法：87500乘法：3450011算法设计与分析12不同计算顺序的差别设矩阵A1,A2和A3分别为10×100,100×5和5×50的矩阵，现要计算A1A2A3。若按((A1A2)A3)来计算，则需要的数乘次数为10×100×5+10×5×50=7500若按(A1(A2A3))来计算，则需要的数乘次数为100×5×