【教学课件】第3章动态规划.ppt

《【教学课件】第3章动态规划.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第3章动态规划.ppt（136页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 动态规划3.1 3.1 动态规划法的基本概念动态规划法的基本概念3.2 3.2 动态规划法的应用专题动态规划法的应用专题算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 2 动态规划|动态规划（动态规划（Dynamic Programming）20世纪世纪50年代美国数学家贝尔曼（年代美国数学家贝尔曼（Richard Bellman)为研究最优控制问题而提出的。为研究最优控制问题而提出的。动态规划是运筹学的一个分支，是求解决策过程动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。最优化的数学方法。应用：应用：n动态

2、规划问世以来，在经济管理、生产调度、动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。工程技术和最优控制等方面得到了广泛的应用。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 3 3.1 动态规划的基本概念3.1.1 什么是动态规划什么是动态规划n例例1：计算斐波那契数：计算斐波那契数3.1.2 动态规划的求解方法动态规划的求解方法n例例2：多段图的最短路径问题：多段图的最短路径问题n例例3：街道问题：街道问题n例例4：数字三角形问题：数字三角形问题3.1.3 动态规划小结动态规划小结3.1.4 矩

3、阵连乘问题矩阵连乘问题算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 4 3.1.1 什么是动态规划|动态规划是求解包含动态规划是求解包含重叠子问题重叠子问题的最优化方法的最优化方法基本思想：基本思想：n将原问题分解为相似的子问题，在求解的过程中通过子将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解（注意：不是简单问题的解求出原问题的解（注意：不是简单分而治之分而治之）。）。原问题的解原问题的解原问题原问题填填表表子问题子问题1子问题子问题2子问题子问题n算法设计与分析算法设计与分析动态规划动态规划 四川师范

4、大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 5 例1：计算斐波那契数|方法一：分治法方法一：分治法long fib(int n)long p;if(n=0|n=1)return n;else p=fib(n-1)+fib(n-2);return p;算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 6 法1：分治法|计算斐波那契数的过程（计算斐波那契数的过程（n=5）冗余计算f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010算法设计与

5、分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 7 法2：动态规划法|分析：分析：计算计算f(n)是以计算它的两个重叠子问题是以计算它的两个重叠子问题 f(n1)和和f(n2)的形式来表达的，所以，可以设计一张表填的形式来表达的，所以，可以设计一张表填入入n1个个f(n)的值。的值。动态规划法求解斐波那契数动态规划法求解斐波那契数f(9)的填表过程的填表过程01234567890112358132134算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 8 3.1.1 什么是动态规

6、划|动态规划法的设计思想：动态规划法的设计思想：将待求解问题分解成若干个将待求解问题分解成若干个相互重叠相互重叠的子问题，每个的子问题，每个子问子问题题对应决策过程的对应决策过程的一个阶段一个阶段。一般来说，子问题的重叠关系表现在对给定问题求解的递一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中。推关系（也就是动态规划函数）中。将子问题的解求解一次并将子问题的解求解一次并填入表填入表中，当需要再次求解此子中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，问题时，可以通过查表获得该子问题的解而不用再次求解，从而从而避免了大量重复计算避免了大

7、量重复计算。S0P1P2Pn多阶段决策过程多阶段决策过程S1S2Sn-1Sn算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 9 动态规划与分治法的异同点|相同点：相同点：动态规划算法与分治法类似，其基本思想也是将待求解问动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题或分为若干级（阶段），然后顺序题分解成若干个子问题或分为若干级（阶段），然后顺序求出各个子问题。求出各个子问题。|区别：区别：动态规划法：动态规划法：n经分解得到的子问题往往不是互相独立的。不同子问题经分解得到的子问题往往不是互相独立的。不同子问

8、题的数目常常只有多项式量级。的数目常常只有多项式量级。分治法：分治法：n经分解得到的子问题往往是互相独立的，在用分治法求经分解得到的子问题往往是互相独立的，在用分治法求解时，有些子问题被重复计算了许多次。解时，有些子问题被重复计算了许多次。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 10 3.1.1 什么是动态规划|动态规划的基本要素动态规划的基本要素重叠子问题性质重叠子问题性质n能够分解为相互重叠的若干子问题；能够分解为相互重叠的若干子问题；n在用分治算法自顶向下对问题进行求解时，每次产生的在用分治算法自顶向下对问题进行求解

9、时，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多子问题并不总是新问题，有些子问题可能被重复计算多次。次。动态规划算法利用此性质，对每个子问题只计算一动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用次，然后将其结果保存起来以便高效重用。最优化子结构性质最优化子结构性质n若问题的最优解所包含的子问题的解也是最优的，则称若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）该问题具有最优子结构性质（即满足最优化原理）算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院

10、刘芳刘芳 11 3.1.2 动态规划的求解方法|求解方法求解方法1.把问题分成许多个子问题（一般地每个子问题把问题分成许多个子问题（一般地每个子问题是互相关联和影响的）是互相关联和影响的）2.依次研究逐个问题的决策。依次研究逐个问题的决策。n常见的处理方法：常见的处理方法：u向前处理法向前处理法(forward approach)：u向后处理法向后处理法(backward approach)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 12 例2：多段图的最短路径|多段图多段图1 12 23 35 54 46 67 78 89

11、9101012 242 23 33 32 24 41 12 24 43 35 56 6 阶段阶段1 1阶段阶段2 2阶段阶段3 3阶段阶段4 4阶段阶段5 5算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 13 例2：多段图的最短路径|多段图多段图多段图多段图G(V,E)是一个有向图。是一个有向图。它有如下特点：它有如下特点：n图中结点被分成图中结点被分成 k 2个不相交的集合个不相交的集合Vi（1 i k）；n其中：其中：V1和和Vk 分别只有一个结点分别只有一个结点s(源点源点)和和t(终点终点)。n图中的边图中的边(u,v)

12、有如下性质：若有如下性质：若u Vi,则则v Vi+1,（1 i k-1）。|多段图问题多段图问题求多段图中由求多段图中由s（源点）源点）到到t（终点）的最小成本路径。终点）的最小成本路径。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 14 例2：多段图的最短路径|例如：例如：1 12 23 35 54 46 67 78 89 9101012 242 23 33 32 24 41 12 24 43 35 56 6 阶段阶段1 1阶段阶段2 2阶段阶段3 3阶段阶段4 4阶段阶段5 5算法设计与分析算法设计与分析动态规划动态规划

13、四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 15 例2:多段图的最短路径|1.分解最优解的结构分解最优解的结构不难说明多段图问题具有最优子结构性质。不难说明多段图问题具有最优子结构性质。|2.建立递归关系建立递归关系(1)向前处理法向前处理法n设设c为图的代价矩阵为图的代价矩阵n设设p(i,j)是一条从集合是一条从集合Vi中的结点中的结点j到终点到终点t的最小的最小成本路径；成本路径；ncost(i,j)是这条路径的成本。是这条路径的成本。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 16 例2:多段图的最

14、短路径显然有：显然有：初始时，初始时，算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 17 例2:多段图的最短路径|3.计算最优值计算最优值V1 V2 V3 V4 V51 12 23 35 54 46 67 78 89 910101 12 24 42 23 33 32 24 41 12 24 43 35 56 6算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 18 例2:多段图的最短路径|4.根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优

15、解。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 19 例2:多段图的最短路径当然也可以采用：向后处理法当然也可以采用：向后处理法n设设BP(i,j)是一条从是一条从源点源点s到到集合集合Vi中的结点中的结点j的最的最小成本路径小成本路径;nBcost(i,j)是这条路径的成本。是这条路径的成本。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 20 例2:多段图的最短路径显然有：显然有：初始时，初始时，算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师

16、范大学 计算机科学学院计算机科学学院 刘芳刘芳 21 例2:多段图的最短路径V1 V2 V3 V4 V51 12 23 35 54 46 67 78 89 910101 12 24 42 23 33 32 24 41 12 24 43 35 56 6算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 22 练习2120345678949387684756866537 一个多段图一个多段图最短路径：最短路径：03589，长度为，长度为16。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学

17、院 刘芳刘芳 23 应用实例|路径规划路径规划车辆卫星定位系统车辆卫星定位系统路径规划：路径规划：n基于具有拓扑结构的道路网络，在车辆驶前或基于具有拓扑结构的道路网络，在车辆驶前或行驶过程中寻找车辆从起始点到目的地的最佳行驶过程中寻找车辆从起始点到目的地的最佳行驶路线的过程，它是多段图最短路径问题。行驶路线的过程，它是多段图最短路径问题。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 24 例3：街道问题|问题描述：问题描述：在一个如下图所示的正方形组成的矩形地图中中在一个如下图所示的正方形组成的矩形地图中中找出从左下角到右上角的

18、最短路径，每步只能向找出从左下角到右上角的最短路径，每步只能向右方或上方走。右方或上方走。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 25 状态转移方程（动态规划函数）：状态转移方程（动态规划函数）：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 26 例4:数字三角形问题|数字三角形（数字三角形（P90）问题描述问题描述分析分析n穷举法穷举法n动态规划法动态规划法13118267121415671312118241311872612141567131211824

19、算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 27|动态规划函数动态规划函数算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 28 3.1.3 动态规划小结|1.动态规划基本步骤动态规划基本步骤找出最优解的性质，并刻划其结构特征找出最优解的性质，并刻划其结构特征递归地定义最优值递归地定义最优值计算最优值计算最优值根据计算最优值时得到的信息，构造最优解根据计算最优值时得到的信息，构造最优解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学

20、学院计算机科学学院 刘芳刘芳 29 3.1.3 动态规划小结|2.应用动态规划法要注意：应用动态规划法要注意：阶段的划分是关键阶段的划分是关键最优化原理应在子问题求解中体现最优化原理应在子问题求解中体现 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 30 3.1.3 动态规划小结|动态规划与分治法动态规划与分治法 相同点相同点不同点不同点|动态规划较之于穷举法的优势动态规划较之于穷举法的优势大大减少了计算量大大减少了计算量丰富了计算结果丰富了计算结果 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机

21、科学学院计算机科学学院 刘芳刘芳 31 矩阵连乘问题|两个矩阵相乘两个矩阵相乘若若A是是pq矩阵，矩阵，B是是qr矩阵矩阵,则矩阵相乘运算共要：则矩阵相乘运算共要：pqr次乘法次乘法.|矩阵连乘矩阵连乘给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是可是可乘的，乘的，考察这考察这n个矩阵的连乘积个矩阵的连乘积 A1 A2 An问题：问题：n如何确定最优计算顺序？如何确定最优计算顺序？算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 32 3.1.4 矩阵连乘问题|例例1：设有三个矩阵设有三个矩阵A1,A2,A3，

22、它们的维数分别是它们的维数分别是n A1 10100，A2 1005，A3 550，则：则：则：则：（1）计算）计算(A1A2)A3)共需要共需要：n10*100*5+10*5*507500 乘法乘法（2）计算）计算(A1(A2A3)共需要共需要n100*5*50+10*100*5075000 乘法乘法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 33 3.1.4 矩阵连乘问题|例例2：设有四个矩阵设有四个矩阵ABCD，它们的维数分别是：它们的维数分别是：16000 1050036000 8750034500算法设计与分析算法设

23、计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 34 3.1.4 矩阵连乘问题|因此：因此：由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用多不同的计算次序。这种计算次序可以用加括号的方式加括号的方式来来确定。确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已积已完全加括号完全加括号，则可以依此次序反复调用，则可以依此次序反复调用2个矩阵相乘个矩阵相乘的标准算法计算出矩阵连乘积。的标准算法计算出矩阵连乘积

24、。|完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；单个矩阵是完全加括号的；矩阵连乘积矩阵连乘积 A是完全加括号的，则是完全加括号的，则A可表示为可表示为2个完全加括个完全加括号的矩阵连乘积号的矩阵连乘积 B和和C 的乘积并加括号，即的乘积并加括号，即A（B C）。）。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 35 矩阵连乘问题|问题提出：问题提出：给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是可乘是可乘的，的，考察这考察这n个矩阵的连乘积个矩阵的连乘

25、积A1 A2 An如何确定计算矩阵连乘积的计算次序（即确定矩如何确定计算矩阵连乘积的计算次序（即确定矩阵的完全加括号方式），使得依此次序计算矩阵阵的完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少？连乘积需要的数乘次数最少？算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 36 方法1：穷举法|穷举法穷举法基本思想基本思想n列举出所有可能的计算次序，并计算出每一种列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。数乘次数最少的

26、计算次序。特点：特点：n计算量大计算量大算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 37 方法1：穷举法分析分析n对于对于n个矩阵的连乘积，设其不同的计算次序个矩阵的连乘积，设其不同的计算次序为为P(n)。n由于每种加括号方式都可以分解为两个子矩阵由于每种加括号方式都可以分解为两个子矩阵的加括号问题：的加括号问题：(A1.Ak)(Ak+1An)可以得到关可以得到关于于P(n)的递推式如下：的递推式如下：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 38 方法2：

27、动态规划法|1.分析最优解的结构分析最优解的结构引入记号：引入记号：n将矩阵连乘积将矩阵连乘积Ai Ai+1 Aj 记为记为Ai:j 。特征：特征：n计算计算A1:n的最优次序所包含的计算矩阵子链的最优次序所包含的计算矩阵子链 A1:k和和Ak+1:n的次序也是最优的。的次序也是最优的。n即：即：u矩阵连乘计算次序问题的最优解包含着其子问题的矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优解。这种性质称为最优子结构性质最优子结构性质。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 39|2.建立递归关系建立递归

28、关系计算计算Ai:j所需要的最少数乘次数所需要的最少数乘次数mij，则原问题的最优，则原问题的最优值为值为m1n。设这个计算次序在矩阵设这个计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，ikj，则其相应完全加括号方式为，则其相应完全加括号方式为(Ai Ai+1 Ak)(Ak+1 Ak+2 Aj)则总的计算量则总的计算量 Ai:k的计算量的计算量 Ak+1:j的计算量的计算量 Ai:kAk+1:j 的计算量的计算量。方法2：动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 40|2.建立递归关系建立递归关

29、系可以递归地定义可以递归地定义mij为：为：这里这里的维数为的维数为 方法2：动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 41 方法2：动态规划法|3.计算最优值计算最优值对于对于1ijn不同的有序对不同的有序对(i,j)对应于不同的子问题。对应于不同的子问题。因此，不同子问题的个数为：因此，不同子问题的个数为：4.4.构造最优解构造最优解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 42 A1A2A3A4A5A630 3535 1515 55 101

30、0 2020 25一个实例计算计算A1 A2 A3 A4 A5 A6的最优次序。的最优次序。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 43|即：即：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 44|例如：例如：计算计算A1 A2 A3 A4 A5 A6的最优次序。的最优次序。故：故：计算计算A1 A2 A3 A4 A5 A6的最优次序为的最优次序为算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳

31、45 void MatrixChain(int*p，int n，int*m，int*s)for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;/for k /for i计算最优值的算法描述算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 46

32、 构造最优解的算法描述void Traceback(int i,int j,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout“Multiply A”i“,”sij;cout“and A”sij+1“,”j endl;算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 47|算法复杂度分析：算法复杂度分析：时间复杂性时间复杂性n算法算法matrixChain的主要计算量取决于算法中对的主要计算量取决于算法中对r，i和和k的的3重循环，因此重循环，因此T(n)

33、O(n3)。空间复杂性空间复杂性nS(n)O(n2)。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 48 方法3：递归分治求解|算法描述：（算法描述：（P54）int RecurMatrix(int i,int j)if(i=j)return 0;u=RecurMatrix(i,i)+RecurMatrix(i+1,j)+pi-1*pi*pj;sij=i;for(k=i+1;kj;k+)t=RecurMatrix(i,k)+RecurMatrix(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;/for re

34、turn u;(Ai Ai+1 Ak)(Ak+1 Ak+2 Aj)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 49|分析：分析：方法3：递归分治求解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 50 小结|1.动态规划算法的基本要素动态规划算法的基本要素最优子结构最优子结构n最优子结构是问题能用动态规划算法求解的前提。最优子结构是问题能用动态规划算法求解的前提。重叠子问题重叠子问题n每一个子问题只解一次，而后将其解保存在一个表格中，每一个子问题只解一次，而后将其

35、解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看当再次需要解此子问题时，只是简单地用常数时间查看一下结果。（一下结果。（自底向上求解自底向上求解）n通常不同的子问题个数随问题的大小呈多项式增长。因通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要此用动态规划算法只需要多项式时间多项式时间，从而获得较高的，从而获得较高的解题效率。解题效率。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 51 小结|2.分治法分治法自顶向下求解自顶向下求解n对重叠的子问题被反复计算多次，效率低。对重叠的子问题被

36、反复计算多次，效率低。|3.备忘录方法备忘录方法备忘录方法的控制结构与直接递归方法的控制结备忘录方法的控制结构与直接递归方法的控制结构相同（自顶向下）构相同（自顶向下）但备忘录方法为每个解过的子问题建立了但备忘录方法为每个解过的子问题建立了备忘录备忘录，以备需要时查看，避免了相同子问题的重复求解。以备需要时查看，避免了相同子问题的重复求解。算法设计与分析算法设计与分析 0)return mij;if(i=j)return 0;int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t

37、=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 53 3.2 动态规划法的应用专题图问题中的动态规划法图问题中的动态规划法组合问题中的动态规划法组合问题中的动态规划法几何问题中的动态规划法几何问题中的动态规划法查找问题中的动态规划法查找问题中的动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 54 应用

38、专题一|图问题中的动态规划法图问题中的动态规划法多段图的最短路径问题多段图的最短路径问题每对结点间的最短路径每对结点间的最短路径TSP问题问题算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 55 每对结点间的最短路径|问题提出：问题提出：G=(V,E)是一个有是一个有n个结点的有向图，个结点的有向图，C是是G的成本邻接矩阵。其中的成本邻接矩阵。其中C(i,i)=0,C(i,j)=(当当边边 E)。要求：要求：n将每对结点间的最短路径值存入矩阵将每对结点间的最短路径值存入矩阵A：nA(i,j)：结点结点i到结点到结点j的最短路径长度

39、。的最短路径长度。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 56 每对结点间的最短路径|1.问题的最优子结构性质问题的最优子结构性质假设假设i到到j的最短路径有一个中间结点的最短路径有一个中间结点k，则由则由i到到k和和k到到j的子的子路径分别是路径分别是i到到k和和k到到j的的最短路径，否则最短路径，否则i到到j的的路径就不具有最短路径。路径就不具有最短路径。故：该问题具备故：该问题具备最优最优子结构性质。子结构性质。算法设计与分析算法设计与分析=1C(i,j)k=0算法设计与分析算法设计与分析动态规划动态规划 四川师范大

40、学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 58|3.计算最优值计算最优值依次计算依次计算A1,A2,An|构造构造最优值最优值An就记录了图中每对结点间的最短路径长度。就记录了图中每对结点间的最短路径长度。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 59 125341010050 30 1020 60A01 2 3 4 512345 0 10 30 100 0 50 0 10 20 0 60 0 A11 2 3 4 512345 0 10 30 100 0 50 0 10 20 0 60 0 每对结点间的最短路径

41、|例：例：求下图的各个结点间的最短路径长度求下图的各个结点间的最短路径长度。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 60 A21 2 3 4 512345 0 10 60 30 100 0 50 0 10 20 0 60 0 A31 2 3 4 512345 0 10 60 30 70 0 50 60 0 10 20 0 30 0 每对结点间的最短路径125341010050 30 1020 60算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 61 每对结点间

42、的最短路径A41 2 3 4 512345 0 10 50 30 60 0 50 60 0 10 20 0 30 0 A51 2 3 4 512345 0 10 50 30 60 0 50 60 0 10 20 0 30 0 125341010050 30 1020 60算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 62 每对结点间的最短路径 void All-paths(int n,int*cost,int*A)/cost-图的成本邻接矩阵图的成本邻接矩阵，A -距离矩阵距离矩阵 for(int i=1;i=n;i+)/初始化

43、初始化Aij for(int j=1;j=n;j+)Aij=costij;for(int k=1;k=n;k+)for(int i=1;i=n;i+)for(int j=1;j=n;j+)Aij=min(Aij,Aik+Akj);算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 63 TSP问题|问题描述：问题描述：旅行商问题旅行商问题（Traveling Salesman Problem）|问题抽象：问题抽象：可以用结点表示城市，城市间的交通路线用边表可以用结点表示城市，城市间的交通路线用边表示，而城市间的交通线路距离可用附加于边

44、的权示，而城市间的交通线路距离可用附加于边的权表示。表示。这样：上述问题可以归结为寻找一条权的总和为这样：上述问题可以归结为寻找一条权的总和为最短的哈密尔顿回路的问题。最短的哈密尔顿回路的问题。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 64 TSP问题|分析：分析：各个城市间的距离可以用代价矩阵来表示。各个城市间的距离可以用代价矩阵来表示。01323 524256 67337算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 65 TSP问题|1.最优子结构性质最优

45、子结构性质设设s,s1,s2,sp,s是从是从s出发的一条路径长度最短出发的一条路径长度最短的简单回路，的简单回路，假设从假设从s到下一个城市到下一个城市s1已经求出，则问题转化为已经求出，则问题转化为求从求从s1到到s的最短路径，显然的最短路径，显然s1,s2,sp,s一定构一定构成一条从成一条从s1到到s的最短路径的最短路径。即即TSP问题具备最优子结构性质。问题具备最优子结构性质。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 66 TSP问题|2.定义递归关系定义递归关系假设从顶点假设从顶点s出发，令出发，令d(i,V)表

46、示从顶点表示从顶点i出发经过出发经过V中各个顶点一次且仅一次，最后回到出发点中各个顶点一次且仅一次，最后回到出发点s的的最短路径长度，最短路径长度，开始时，开始时，i s，VV s，于是，于是，TSP问题的动态规划函数为：问题的动态规划函数为：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 67 TSP问题|3.计算最优值计算最优值（1）从城市）从城市0出发经城市出发经城市1、2、3然后然后回到城市回到城市0的最短路径长度是：的最短路径长度是：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+

47、d(3,1,2)这是最后一个阶段的决策。这是最后一个阶段的决策。这一阶段的决策又依赖于下面的计算结这一阶段的决策又依赖于下面的计算结果。果。01323 52425667337算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 68 TSP问题|3.计算最优值计算最优值（2）d(1,2,3)=minc12+d(2,3),c13+d(3,2)d(2,1,3)=minc21+d(1,3),c23+d(3,1)d(3,1,2)=minc31+d(1,2),c32+d(2,1)这一阶段的决策又依赖于下面这一阶段的决策又依赖于下面的计算结果。的计

48、算结果。01323 52425667337算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 69 TSP问题|3.计算最优值计算最优值（3）d(1,2)=c12+d(2,)d(2,3)=c23+d(3,)d(3,2)=c32+d(2,)d(1,3)=c13+d(3,)d(2,1)=c21+d(1,)d(3,1)=c31+d(1,)这一阶段的决策又依赖于下面这一阶段的决策又依赖于下面的计算结果：的计算结果：01323 52425667337算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学

49、学院 刘芳刘芳 70 TSP问题|3.计算最优值计算最优值（4）而下式可以直接获得（括）而下式可以直接获得（括号中是该决策引起的状态转移）：号中是该决策引起的状态转移）：d(1,)=c10=5(10)d(2,)=c20=6(20)d(3,)=c30=3(30)再往前推再往前推01323 52425667337算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 71 TSP问题|3.计算最优值计算最优值d(1,2)=c12+d(2,)=2+6=8(12)d(2,3)=c23+d(3,)=2+3=5(23)d(3,2)=c32+d(2,)

50、=5+6=11(32)d(1,3)=c13+d(3,)=3+3=7(13)d(2,1)=c21+d(1,)=4+5=9(21)d(3,1)=c31+d(1,)=7+5=11(31)再往前推再往前推01323 52425667337算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 72 TSP问题|3.计算最优值计算最优值d(1,2,3)=minc12+d(2,3),c13+d(3,2)=min2+5,3+11=7(12)d(2,1,3)=minc21+d(1,3),c23+d(3,1)=min4+6,2+12=10(21)d(3,1