第3章动态规划1.ppt
第三章 动态规划 Dynamic Programming,1,2023年2月2日星期四,第3章 动态规划,掌握设计动态规划算法的步骤,掌握动态规划算法的基本要素,通过应用范例学习动态规划算法设计策略,20世纪50年代,美国数学家R.E.Bellman等人,最优化原理,动态规划,2,2023年2月2日星期四,第3章 动态规划,3,2023年2月2日星期四,第3章 动态规划,动态规划(dynamic programming)属运筹学中的规划论分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。多阶段决策问题：指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。,4,2023年2月2日星期四,第3章 动态规划,虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应用广泛：经济管理、生产调度、工程技术和最优控制。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。,动态规划的基本要素,1)最优子结构性质,最优化原理：一个最优化策略的子策略总是最优的。,一个问题满足最优化原理又称其具有最优子结构性质。,2)子问题重叠性质,5,2023年2月2日星期四,第3章 动态规划,A,B,C,I,J,如图，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。,*最优化原理是动态规划的基础。,2023年2月2日星期四,6,第3章 动态规划,一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优化原理），则可以考虑用动态规划解决。,7,2023年2月2日星期四,第3章 动态规划,动态规划的基本思想,与分治法类似，其基本思想也是将待求解问题 分解成若干个子问题，先求解子问题，然后 从这些子问题的解得到原问题的解。,与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是相互独立的。,8,2023年2月2日星期四,第3章 动态规划,T(n),避免大重复计算,9,2023年2月2日星期四,第3章 动态规划,动态规划的实质,动态规划的实质是分治思想和解决冗余。,1)一种将问题实例分解为更小的、相似的子问题。,2)存储子问题的解而避免计算重复的子问题。,10,2023年2月2日星期四,第3章 动态规划,主要特点:问题分解；采用表格技术，用多项式算法代替指数算法；空间换取时间,动态规划的特点,动态规划法用于最优化问题，这类问题会有多种可能的解，而动态规划找出其中最优值的解。若存在若干个取最优值的解的话，它只取其中的一个。,对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解。,11,2023年2月2日星期四,第3章 动态规划,动态规划算法设计步骤,分析最优解的性质，并刻划其结构特征；,递归地定义最优值；,以自底向上的方式计算出最优值；,根据计算最优值时得到的信息，构造最优解。,12,2023年2月2日星期四,第3章 动态规划,步骤(1)-(3)是基本步骤。在只需要求出最优值的情形，步骤(4)可以省略。若需要求出问题的一个最优解，则必须执行步骤(4)。此时，需要利用在步骤(3)中计算最优值时记录的相关信息。,两个矩阵相乘,计算C需要多少次数乘？,3.1 矩阵连乘问题,13,2023年2月2日星期四,第3章 动态规划,三个矩阵连乘,=7500,2023年2月2日星期四,14,第3章 动态规划,矩阵连乘问题,?,2023年2月2日星期四,15,第3章 动态规划,例如，矩阵连乘积A1A2A3 A4可以有以下5种不同的完全加括号方式：(A1(A2(A3A4)，(A1(A2A3)A4),(A1A2)(A3A4),(A1(A2A3)A4),(A1A2)A3)A4)。每一种完全加括号方式对应于一种矩阵连乘积的计算次序，而这种计算次序与计算矩阵连乘积的计算量有着密切的关系。,2023年2月2日星期四,16,第3章 动态规划,为方便起见，定义下列的符号：,矩阵连乘积,最少数乘次数,2023年2月2日星期四,17,第3章 动态规划,1.分析最优解的结构,最优子结构,设,为最优计算次序，,反证法,若存在一个计算次序,其需要的计算量更少,令,矛盾,矩阵连乘积计算次序问题具有最优子结构性质，即最优解包含着子问题的最优解。,18,2023年2月2日星期四,第3章 动态规划,2.建立递归关系,1),单一矩阵,2),19,2023年2月2日星期四,第3章 动态规划,2.建立递归关系,单一矩阵,20,2023年2月2日星期四,第3章 动态规划,3.计算最优值,用动态规划算法解问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。,2023年2月2日星期四,21,第3章 动态规划,例1.计算矩阵连乘积A1:6，其中各矩阵的维数分别为：,2023年2月2日星期四,22,第3章 动态规划,1,2,3,4,5,6,0,0,0,0,0,0,5000,1000,1,2,3,4,5,6,0,0,0,0,0,0,5,3500,4,5,15750,7875,9375,11875,15125,2625,4375,7125,10500,750,2500,5375,1,1,3,3,3,3,3,3,2,3,3,3,Sij,23,2023年2月2日星期四,第3章 动态规划,2023年2月2日星期四,24,第3章 动态规划,A1,A2,A3,A4,A5,A6,(,),4.构造最优解,25,2023年2月2日星期四,第3章 动态规划,练习：设n=5和 p=(10,5,1,10,2,10)，求矩阵连乘积问题最优值。,
