第3章动态规划1

《第3章动态规划1》由会员分享，可在线阅读，更多相关《第3章动态规划1（25页珍藏版）》请在装配图网上搜索。

1、第三章第三章 动态规划动态规划 Dynamic Programming12022年1月3日星期一第3章 动态规划 掌握设计动态规划算法的步骤掌握设计动态规划算法的步骤 掌握动态规划算法的基本要素掌握动态规划算法的基本要素 通过应用范例学习动态规划算法设计策略通过应用范例学习动态规划算法设计策略0. .max:xbAxtsxcLPT2020世纪世纪5050年代年代美国数学家美国数学家R. E. Bellman等人等人最优化原理最优化原理动态规划动态规划22022年1月3日星期一第3章 动态规划32022年1月3日星期一第3章 动态规划 动态规划动态规划(dynamic programming)(

2、dynamic programming)属运筹学中的规划论分支，属运筹学中的规划论分支，是求解决策过程最优化的数学方法。是求解决策过程最优化的数学方法。2020世纪世纪5050年代初美国年代初美国数学家数学家R.E.BellmanR.E.Bellman等人在研究多阶段决策过程的优化问题等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理时，提出了著名的最优化原理(principle of optimality)(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新

3、方法了解决这类过程优化问题的新方法动态规划。动态规划。 多阶段决策问题：多阶段决策问题：指这样的一类特殊的活动过程，问题可指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。个活动的总体效果达到最优的问题，称为多阶段决策问题。42022年1月3日星期一第3章 动态规划 虽然动态规划主要用于求解以时间划分阶段的动虽然动态规划主要用于求解以时间划分阶段的动态过程的优化

4、问题，但是一些与时间无关的静态态过程的优化问题，但是一些与时间无关的静态规划规划( (如线性规划、非线性规划如线性规划、非线性规划) )，只要人为地引，只要人为地引进时间因素，把它视为多阶段决策过程，也可以进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。用动态规划方法方便地求解。 应用广泛：应用广泛：经济管理、生产调度、工程技术和最经济管理、生产调度、工程技术和最优控制。例如最短路线、库存管理、资源分配、优控制。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。比用其它方法求解更为

5、方便。动态规划的基本要素动态规划的基本要素 1)最优子结构性质最优子结构性质最优化原理：一个最优化策略的子策略总是最优的。最优化原理：一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有一个问题满足最优化原理又称其具有最优子结构性质最优子结构性质。2)2)子问题重叠性质子问题重叠性质52022年1月3日星期一第3章 动态规划ABCJIJ如图，若路线如图，若路线I和和J是是A到到C的最优的最优路径，则根据最优化原理，路线路径，则根据最优化原理，路线J J必是从必是从B到到C的最优路线。的最优路线。*最优化原理是动态规划的基础。最优化原理是动态规划的基础。2022年1月3日星期一6第

6、3章 动态规划一般来说，只要该问题可以划分成规模更小一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优化原理），则问题的最优解（即满足最优化原理），则可以考虑用动态规划解决。可以考虑用动态规划解决。 72022年1月3日星期一第3章 动态规划动态规划的基本思想动态规划的基本思想与分治法类似，其基本思想也是将待求解问题与分治法类似，其基本思想也是将待求解问题 分解成若干个子问题，先求解子问题，然后分解成若干个子问题，先求解子问题，然后 从这些子问题的解得到原问题的解。从这些子问题的解得到原问题的解。 与分治法

7、不同的是，与分治法不同的是，适合用动态规划求解的问题，适合用动态规划求解的问题， 经分解得到的子问题往往不是相互独立的。经分解得到的子问题往往不是相互独立的。82022年1月3日星期一第3章 动态规划n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)92022年1月3日星期一第3章 动态规划动态规划的实质动态规划的实质动态规划的实质是分治思想和解决冗余。动态规划的实质是分治思想和解决冗余。1) 一种将问题实例分解为更小的、相似的子问题。一种将问题实例分解为更小的、相似的子问题

8、。2) 存储子问题的解而避免计算重复的子问题。存储子问题的解而避免计算重复的子问题。102022年1月3日星期一第3章 动态规划主要特点主要特点: : 问题分解；采用表格技术，用多项式问题分解；采用表格技术，用多项式算法代替指数算法；空间换取时间算法代替指数算法；空间换取时间动态规划的特点动态规划的特点 动态规划法用于最优化问题，这类问题会有多动态规划法用于最优化问题，这类问题会有多种可能的解，而动态规划找出其中最优值的解。种可能的解，而动态规划找出其中最优值的解。若存在若干个取最优值的解的话，它只取其中若存在若干个取最优值的解的话，它只取其中的一个。的一个。 对于重复出现的子问题，只在第一次

9、遇到时加对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不以求解，并把答案保存起来，以后再遇到时不必重新求解。必重新求解。112022年1月3日星期一第3章 动态规划动态规划算法设计步骤动态规划算法设计步骤分析最优解的性质，并刻划其结构特征；分析最优解的性质，并刻划其结构特征； 递归地定义最优值；递归地定义最优值；以自底向上的方式计算出最优值；以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。122022年1月3日星期一第3章 动态规划步骤(1)-(3)是基本步骤。在只需要求出最优值的情形，步骤(4)可

10、以省略。若需要求出问题的一个最优解，则必须执行步骤(4)。此时，需要利用在步骤(3)中计算最优值时记录的相关信息。两个矩阵相乘两个矩阵相乘rjpiBACqkkjikij1 ,11计算计算C需要多少次数乘？需要多少次数乘？ pqrq3.1 矩阵连乘问题矩阵连乘问题132022年1月3日星期一第3章 动态规划三个矩阵连乘三个矩阵连乘750005010010505100321)(AAA51001050510=7500)(321AAA2022年1月3日星期一14第3章 动态规划矩阵连乘问题矩阵连乘问题? ?2022年1月3日星期一15第3章 动态规划例如，矩阵连乘积例如，矩阵连乘积A1A2A3 A4可

11、以有以下可以有以下5种不同的种不同的完全加括号方式：完全加括号方式： (A1(A2(A3A4)， (A1(A2A3)A4), (A1A2)(A3A4), (A1(A2A3)A4), (A1A2)A3)A4)。 每一种完全加括号方式对应于一种矩阵连乘积的每一种完全加括号方式对应于一种矩阵连乘积的计算次序，而这种计算次序与计算矩阵连乘积的计算次序，而这种计算次序与计算矩阵连乘积的计算量有着密切的关系。计算量有着密切的关系。2022年1月3日星期一16第3章 动态规划为方便起见，定义下列的符号：为方便起见，定义下列的符号：jiiAAA1:jiA矩阵连乘积矩阵连乘积 jim最少数乘次数最少数乘次数 :

12、jiA:1 nA1 nm2022年1月3日星期一17第3章 动态规划1.分析最优解的结构分析最优解的结构最优子结构最优子结构:1:1 :1 nkAkAnA设设为最优计算次序，为最优计算次序，反证法反证法若存在一个计算次序若存在一个计算次序 :1 kA其需要的计算量更少其需要的计算量更少 :1:1 :1 nkAkAnA令令矛盾矩阵连乘积计算次序问题具有矩阵连乘积计算次序问题具有最优子结构性质最优子结构性质，即最优解包含着子问题的最优解。即最优解包含着子问题的最优解。182022年1月3日星期一第3章 动态规划2.建立递归关系建立递归关系:jiA1)ji 0iim单一矩单一矩阵阵ji 2)jjii

13、iAAAAA121jkipppjkmkim11)(ij 192022年1月3日星期一第3章 动态规划2.建立递归关系建立递归关系jipppjkmkimjijimjkijki1min01单一单一矩阵矩阵202022年1月3日星期一第3章 动态规划3.计算最优值计算最优值用动态规划算法解问题，可依据其递归式用动态规划算法解问题，可依据其递归式以自底向上以自底向上的方式进行计算。的方式进行计算。在计算过程中，保存已解决的子问题答案。在计算过程中，保存已解决的子问题答案。2022年1月3日星期一21第3章 动态规划ji123456123456例例1.计算矩阵连乘积计算矩阵连乘积A1:6，其中各矩阵的维

14、数分别为：，其中各矩阵的维数分别为：2520201010551515353530654321AAAAAA2022年1月3日星期一22第3章 动态规划可以表示为：可以表示为：n=6，p=(30, 35, 15, 5, 10, 20, 25)123456000000500010001234560000005)()(654654AAAAAA62502510525201035002520520105350045157507875 9375 118751512526254375712510500750 25005375113333332333Sij232022年1月3日星期一第3章 动态规划1137520103504375 55 4271252053510002625 54 321300020153525000 53 22min 52541531521pppmmpppmmpppmmm35003500,6250min25001000066541250500006544min64653643pppmmpppmmm2022年1月3日星期一24第3章 动态规划A1A2 A3A4 A5 A6() ()()4.构造构造最优解最优解252022年1月3日星期一第3章 动态规划练习：设练习：设n=5和和 p=(10, 5, 1, 10, 2, 10)，求矩阵，求矩阵连乘积问题最优值。连乘积问题最优值。