《教学课件第3章动态规划》由会员分享，可在线阅读，更多相关《教学课件第3章动态规划（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)11001
5、010算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 7 法2：动态规划法|分析：分析：计算计算f(n)是以计算它的两个重叠子问题是以计算它的两个重叠子问题 f(n1)和和f(n2)的形式来表达的，所以，可以设计一张表的形式来表达的，所以，可以设计一张表填入填入n1个个f(n)的值。的值。 动态规划法求解斐波那契数动态规划法求解斐波那契数f(9)的填表过程的填表过程0 01 12 23 34 45 56 67 78 89 90 01 11 12 23 35 58 8131321213434算法设计与分析算法设计与分析动态规划动态规
6、划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 8 3.1.1 什么是动态规划|动态规划法的设计思想：动态规划法的设计思想：将待求解问题分解成若干个将待求解问题分解成若干个相互重叠相互重叠的子问题，每个的子问题，每个子问子问题题对应决策过程的对应决策过程的一个阶段一个阶段。一般来说，子问题的重叠关系表现在对给定问题求解的递一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中。推关系（也就是动态规划函数）中。将子问题的解求解一次并将子问题的解求解一次并填入表填入表中，当需要再次求解此子中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不
7、用再次求解，问题时，可以通过查表获得该子问题的解而不用再次求解，从而从而避免了大量重复计算避免了大量重复计算。S0P1P2Pn多阶段决策过程多阶段决策过程S1S2Sn-1Sn算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 9 动态规划与分治法的异同点|相同点：相同点：动态规划算法与分治法类似，其基本思想也是将待求解问动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题或分为若干级（阶段），然后顺序题分解成若干个子问题或分为若干级（阶段），然后顺序求出各个子问题。求出各个子问题。|区别：区别：动态规划法：动态规划法
8、：n经分解得到的子问题往往不是互相独立的。不同子问题经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。的数目常常只有多项式量级。分治法：分治法：n经分解得到的子问题往往是互相独立的，在用分治法求经分解得到的子问题往往是互相独立的，在用分治法求解时，有些子问题被重复计算了许多次。解时，有些子问题被重复计算了许多次。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 10 3.1.1 什么是动态规划|动态规划的基本要素动态规划的基本要素重叠子问题性质重叠子问题性质n能够分解为相互重叠的若干子问题；能够分解为相互重叠
9、的若干子问题；n在用分治算法自顶向下对问题进行求解时，每次产生的在用分治算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多子问题并不总是新问题，有些子问题可能被重复计算多次。次。动态规划算法利用此性质，对每个子问题只计算一动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用次，然后将其结果保存起来以便高效重用。最优化子结构性质最优化子结构性质n若问题的最优解所包含的子问题的解也是最优的，则称若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）该问题具有最优子结构性质（即满足最优化原理）算法
10、设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 11 3.1.2 动态规划的求解方法|求解方法求解方法1.把问题分成许多个子问题（一般地每个子问题把问题分成许多个子问题（一般地每个子问题是互相关联和影响的）是互相关联和影响的）2.依次研究逐个问题的决策。依次研究逐个问题的决策。n常见的处理方法：常见的处理方法：u向前处理法向前处理法( (forward approach)：u向后处理法向后处理法( (backward approach)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院
11、 刘芳刘芳 12 例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 例2：多段图的最短路径|多段图多段图多段图多段图G(V, E)是一个有向图。是一个有向图。它有如下特点：它有如下特点：n图中结点被分成图中结点被分成 k 2个不相交的集合个不相交的集合Vi （ 1 i k）；n其中：其
12、中：V1和和Vk 分别只有一个结点分别只有一个结点s(源点源点)和和t(终点终点)。n图中的边图中的边( (u,v)有如下性质：若有如下性质：若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
13、6 阶段阶段1 1阶段阶段2 2阶段阶段3 3阶段阶段4 4阶段阶段5 5算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 15 例2:多段图的最短路径|1.1.分解最优解的结构分解最优解的结构不难说明多段图问题具有最优子结构性质。不难说明多段图问题具有最优子结构性质。|2.2.建立递归关系建立递归关系(1)(1)向前处理法向前处理法n设设c为图的代价矩阵为图的代价矩阵n设设p(i,j)是一条从集合是一条从集合Vi中的结点中的结点j到终点到终点t的最的最小成本路径；小成本路径；ncost(i,j)是这条路径的成本。是这条路径的成本。
14、算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 16 例2:多段图的最短路径显然有：显然有：初始时，初始时，算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计
15、算机科学学院 刘芳刘芳 18 例2:多段图的最短路径|4.根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 19 例2:多段图的最短路径当然也可以采用：向后处理法当然也可以采用：向后处理法n设设BP(i,j)是一条从是一条从源点源点s到到集合集合Vi中的结点中的结点j的的最小成本路径最小成本路径;nBcost(i,j)是这条路径的成本。是这条路径的成本。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院
16、刘芳刘芳 20 例2:多段图的最短路径显然有：显然有：初始时，初始时，算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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一个多段图一个多段图最短路径：最短路径
17、：0358903589，长度为，长度为1616。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 23 应用实例|路径规划路径规划车辆卫星定位系统车辆卫星定位系统路径规划：路径规划：n基于具有拓扑结构的道路网络，在车辆驶前或基于具有拓扑结构的道路网络，在车辆驶前或行驶过程中寻找车辆从起始点到目的地的最佳行驶过程中寻找车辆从起始点到目的地的最佳行驶路线的过程，它是多段图最短路径问题。行驶路线的过程，它是多段图最短路径问题。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 2
18、4 例3：街道问题|问题描述：问题描述：在一个如下图所示的正方形组成的矩形地图中中在一个如下图所示的正方形组成的矩形地图中中找出从左下角到右上角的最短路径，每步只能向找出从左下角到右上角的最短路径，每步只能向右方或上方走。右方或上方走。 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 25 状态转移方程（动态规划函数）：状态转移方程（动态规划函数）：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 26 例4:数字三角形问题|数字三角形（数字三角形（P90）问题描述问题
19、描述分析分析n穷举法穷举法n动态规划法动态规划法131311118 82671212141415156 67 71313121211118 82424131311118 87 726261212141415156 67 71313121211118 82424算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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个矩阵的连乘积个矩阵的连
22、乘积 A1 A2 An问题：问题：n如何确定最优计算顺序？如何确定最优计算顺序？算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 32 3.1.4 矩阵连乘问题|例例1：设有三个矩阵设有三个矩阵A1,A2,A3 ，它们的维数分别是它们的维数分别是n A1 10100，A2 1005，A3 550，则：则：则：则：（1）计算）计算(A1A2) A3)共需要共需要：n10*100*5+10*5*5010*100*5+10*5*5075007500乘法乘法（2）计算）计算( (A1(A2A3)共需要共需要n100*5*50+10*100*
23、50100*5*50+10*100*507500075000乘法乘法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 33 3.1.4 矩阵连乘问题|例例2：设有四个矩阵设有四个矩阵ABCD ，它们的维数分别是：它们的维数分别是：16000 1050036000 8750034500算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 34 3.1.4 矩阵连乘问题|因此：因此：由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有
24、许多不同的计算次序。这种计算次序可以用多不同的计算次序。这种计算次序可以用加括号的方式加括号的方式来来确定。确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已积已完全加括号完全加括号，则可以依此次序反复调用，则可以依此次序反复调用2个矩阵相乘个矩阵相乘的标准算法计算出矩阵连乘积。的标准算法计算出矩阵连乘积。|完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；单个矩阵是完全加括号的；矩阵连乘积矩阵连乘积 A是完全加括号的，则是完全加括号的，则A可表示为可表示为2个完全加个完全加括号的矩阵
25、连乘积括号的矩阵连乘积 B和和C 的乘积并加括号，即的乘积并加括号，即A（B C）。）。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 35 矩阵连乘问题|问题提出：问题提出：给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是是可乘的，可乘的， 考察这考察这n个矩阵的连乘积个矩阵的连乘积A1 A2 An如何确定计算矩阵连乘积的计算次序（即确定矩如何确定计算矩阵连乘积的计算次序（即确定矩阵的完全加括号方式），使得依此次序计算矩阵阵的完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少？连乘积需要的数乘次数
26、最少？算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 36 方法1：穷举法|穷举法穷举法基本思想基本思想n列举出所有可能的计算次序，并计算出每一种列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。数乘次数最少的计算次序。特点：特点：n计算量大计算量大算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 37 方法1：穷举法分析分析n对于对于n个矩阵的连乘积，设其不同的计算次序个矩阵
27、的连乘积，设其不同的计算次序为为P(n)。n由于每种加括号方式都可以分解为两个子矩阵由于每种加括号方式都可以分解为两个子矩阵的加括号问题：的加括号问题：(A1.Ak)(Ak+1An)可以得到关可以得到关于于P(n)的递推式如下：的递推式如下：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 38 方法2：动态规划法|1.1.分析最优解的结构分析最优解的结构引入记号：引入记号：n将矩阵连乘积将矩阵连乘积Ai Ai+1 Aj记为记为Ai:j 。特征：特征：n计算计算A1:n的最优次序所包含的计算矩阵子链的最优次序所包含的计算矩阵子链 A
28、1:k和和Ak+1:n的次序也是最优的。的次序也是最优的。n即：即：u矩阵连乘计算次序问题的最优解包含着其子问题的矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优解。这种性质称为最优子结构性质最优子结构性质。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 39 |2.2.建立递归关系建立递归关系计算计算Ai:j所需要的最少数乘次数所需要的最少数乘次数mij，则原问题的最优，则原问题的最优值为值为m1n 。设这个计算次序在矩阵设这个计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，ikj，则其相应
29、完全加括号方式为，则其相应完全加括号方式为(Ai Ai+1 Ak) ( Ak+1 Ak+2 Aj )则总的计算量则总的计算量Ai:k的计算量的计算量Ak+1:j的计算量的计算量Ai:kAk+1:j 的计算量的计算量。方法2：动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 40 |2.2.建立递归关系建立递归关系可以递归地定义可以递归地定义mij为：为：这里这里的维数为的维数为 方法2：动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 41 方法2：动
30、态规划法|3.3.计算最优值计算最优值对于对于1ijn不同的有序对不同的有序对(i,j)对应于不同的子问对应于不同的子问题。因此，不同子问题的个数为：题。因此，不同子问题的个数为：4.4.构造最优解构造最优解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 42 A1A2A3A4A5A630 3535 1515 55 1010 2020 25一个实例计算计算A1 A2 A3 A4 A5 A6的最优次序。的最优次序。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 43 |
31、即：即：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 44 |例如：例如：计算计算A1 A2 A3 A4 A5 A6的最优次序。的最优次序。故：故：计算计算A1 A2 A3 A4 A5 A6的最优次序为的最优次序为算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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 =
32、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 构造最优解的算法描述void Traceback(int i,int j,int
33、*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)O(n3)。空间复杂性空间复杂性nS(n) O(n2)。算法设计与
34、分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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 return u;(Ai Ai+1 Ak)
35、 ( Ak+1 Ak+2 Aj )算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 49 |分析：分析：方法3：递归分治求解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 50 小结|1.动态规划算法的基本要素动态规划算法的基本要素最优子结构最优子结构n最优子结构是问题能用动态规划算法求解的前提。最优子结构是问题能用动态规划算法求解的前提。重叠子问题重叠子问题n每一个子问题只解一次，而后将其解保存在一个表格中，每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要
36、解此子问题时，只是简单地用常数时间查看当再次需要解此子问题时，只是简单地用常数时间查看一下结果。（一下结果。（自底向上求解自底向上求解）n通常不同的子问题个数随问题的大小呈多项式增长。因通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要此用动态规划算法只需要多项式时间多项式时间，从而获得较高的，从而获得较高的解题效率。解题效率。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 51 小结|2.分治法分治法自顶向下求解自顶向下求解n对重叠的子问题被反复计算多次，效率低。对重叠的子问题被反复计算多次，效率低。|3.备
37、忘录方法备忘录方法备忘录方法的控制结构与直接递归方法的控制结备忘录方法的控制结构与直接递归方法的控制结构相同（自顶向下）构相同（自顶向下）但备忘录方法为每个解过的子问题建立了但备忘录方法为每个解过的子问题建立了备忘录备忘录，以备需要时查看，避免了相同子问题的重复求解。以备需要时查看，避免了相同子问题的重复求解。算法设计与分析算法设计与分析 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
38、+) int t = 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 动态规划法的应用专题图问题中的动态规划法图问题中的动态规划法组合问题中的动态规划法组合问题中的动态规划法几何问题中的动态规划法几何问题中的动态规划法查找问题中的动态规划法查找问题中的动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学
39、 计算机科学学院计算机科学学院 刘芳刘芳 54 应用专题一|图问题中的动态规划法图问题中的动态规划法多段图的最短路径问题多段图的最短路径问题每对结点间的最短路径每对结点间的最短路径TSP问题问题算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 55 每对结点间的最短路径|问题提出：问题提出：G = (V, E)是一个有是一个有n个结点的有向图，个结点的有向图，C是是G的成本邻接矩阵。其中的成本邻接矩阵。其中C(i,i)=0, C( i, j ) = (当边当边 E )。要求：要求：n将每对结点间的最短路径值存入矩阵将每对结点间的最短
40、路径值存入矩阵A：nA(i,j)：结点结点i到结点到结点j的最短路径长度。的最短路径长度。 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 56 每对结点间的最短路径|1.1.问题的最优子结构性质问题的最优子结构性质假设假设i到到j的最短路径有一个中间结点的最短路径有一个中间结点k，则由则由i到到k和和k到到j的子的子路径分别是路径分别是i到到k和和k到到j的的最短路径，否最短路径，否则则i到到j的的路径就不具有最短路径。路径就不具有最短路径。故：该问题具备故：该问题具备最优最优子结构性质。子结构性质。算法设计与分析算法设计与分析
41、=1C(i, j) k=0算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 58 |3.3.计算最优值计算最优值依次计算依次计算A1, A2, ,An |构造构造最优值最优值An就记录了图中每对结点间的最短路径长度。就记录了图中每对结点间的最短路径长度。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 59 1 12 25 53 34 4101010010050503030101020206060A01 2 3 4 512345 0 10 30 100 0 50 0 10
42、 20 0 60 0 A11 2 3 4 512345 0 10 30 100 0 50 0 10 20 0 60 0 每对结点间的最短路径|例：例：求下图的各个结点间的最短路径长度求下图的各个结点间的最短路径长度。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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 每对结点间的最短路径1 12 25 53 34 410
43、1010010050503030101020206060算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 61 每对结点间的最短路径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 1 12 25 53 34 4101010010050503030101020206060算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院
44、 刘芳刘芳 62 每对结点间的最短路径 void All-paths( int n, int *cost, int *A ) /cost-图的成本邻接矩阵图的成本邻接矩阵，A -距离矩阵距离矩阵 for(int i = 1; i =n; i +) /初始化初始化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) ;算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四
45、川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 63 TSP问题|问题描述：问题描述：旅行商问题旅行商问题（Traveling Salesman Problem） |问题抽象：问题抽象：可以用结点表示城市，城市间的交通路线用边表可以用结点表示城市，城市间的交通路线用边表示，而城市间的交通线路距离可用附加于边的权示，而城市间的交通线路距离可用附加于边的权表示。表示。这样：上述问题可以归结为寻找一条权的总和为这样：上述问题可以归结为寻找一条权的总和为最短的哈密尔顿回路的问题。最短的哈密尔顿回路的问题。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科
46、学学院 刘芳刘芳 64 TSP问题|分析：分析：各个城市间的距离可以用代价矩阵来表示。各个城市间的距离可以用代价矩阵来表示。0 01 13 32 23 3 5 52 24 42 25 5666 67 73 33 37 7算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 65 TSP问题|1.1.最优子结构性质最优子结构性质设设s, s1, s2, , sp, s是从是从s出发的一条路径长度最出发的一条路径长度最短的简单回路，短的简单回路，假设从假设从s到下一个城市到下一个城市s1已经求出，则问题转化为已经求出，则问题转化为求从求从s
47、1到到s的最短路径，显然的最短路径，显然s1, s2, , sp, s一定一定构成一条从构成一条从s1到到s的最短路径的最短路径。即即TSP问题具备最优子结构性质。问题具备最优子结构性质。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 66 TSP问题|2.2.定义递归关系定义递归关系假设从顶点假设从顶点s出发，令出发，令d(i, V)表示从顶点表示从顶点i出发经出发经过过V中各个顶点一次且仅一次，最后回到出发点中各个顶点一次且仅一次，最后回到出发点s的最短路径长度，的最短路径长度，开始时，开始时，i s，VV s ，于是，于是，
48、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+d(3,1,2)这是最后一个阶段的决策。这是最后一个阶段的决策。这一阶段的决策又依赖于下面的计算结这一阶段的决策又依赖于下面的计算结果。果。0 01 13 32 23 3 5 52 24 4
49、2 25 56 66 67 73 33 37 7算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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)这一阶段的决策又依赖于下面这一阶段的决策又依赖于下面的计算结果。的计算结果。0 01 13 32 23 3 5 52 24 42 25 56 66 67 73 33 37 7算法设计与分析
50、算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 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,)这一阶段的决策又依赖于下面这一阶段的决策又依赖于下面的计算结果：的计算结果：0 01 13 32 23 3 5 52 24 42 25 56 66 67 73 33 37 7算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计
51、算机科学学院 刘芳刘芳 70 TSP问题|3.计算最优值计算最优值（4）而下式可以直接获得（括）而下式可以直接获得（括号中是该决策引起的状态转移）：号中是该决策引起的状态转移）：d(1,)=c10=5(10)d(2,)=c20=6(20)d(3,)=c30=3(30)再往前推再往前推0 01 13 32 23 3 5 52 24 42 25 56 66 67 73 33 37 7算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 71 TSP问题|3.计算最优值计算最优值d(1,2)=c12+d(2,)=2+6=8(12)d(2,3)
52、=c23+d(3,)=2+3=5(23)d(3,2)=c32+d(2,)=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)再往前推再往前推0 01 13 32 23 3 5 52 24 42 25 56 66 67 73 33 37 7算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 72 TSP问题|3.计算最优值计算最优值d(1,2,3)=minc12+d(2,3),c13+ d(3,2)=min2+
53、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,2)=minc31+d(1,2),c32+ d(2,1)=min7+8,5+9=14(32)0 01 13 32 23 3 5 52 24 42 25 56 66 67 73 33 37 7算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 73 TSP问题|3.计算最优值计算最优值则：从城市则：从城市0出发经城市出发经城市1、2、3然后回然后回到城市到城市0的最短路径长度是：的最短路径长度是：
54、d(0,1,2,3)=minc01+d(1,2,3), c02+d(2,1,3), c03+d(3,1,2)=min3+7,6+10,7+14=10(01)0 01 13 32 23 3 5 52 24 42 25 56 66 67 73 33 37 74.构造最优解构造最优解从顶点从顶点0出发的出发的TSP问题的最短路径长度为问题的最短路径长度为10，路径是路径是01230。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 74 TSP问题|动态规划法求解动态规划法求解TSP问题的填表过程问题的填表过程dij表示从顶点表示从顶点i
55、经过子集经过子集Vj中的顶点一次且仅中的顶点一次且仅一次，最后回到出发点一次，最后回到出发点0 0的最短路径长度。的最短路径长度。 ji1122331,1,221,1,332,2,33 1,2,1,2,330 0 10101 15 5 8 86 6 7 7 2 26 69 9 5 5 1010 3 33 312121111 1414 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 75 TSP问题|TSP问题求解过程示意图问题求解过程示意图 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算
56、机科学学院 刘芳刘芳 76 TSP问题的算法描述1 1for (i=1; in; i+) /初始化第初始化第0 0列列di0=ci0; 2for (j=1; j2n-1- -1; j+) for (i=1; in; i+) /依次进行第依次进行第i次迭代次迭代if (子集子集Vj中不包含中不包含i) 对对Vj中的每个元素中的每个元素k，计算计算dij=min(cik+dkj- -1); 3对对V2n-1- -1中的每一个元素中的每一个元素k，计算计算d02n-1-1=min(c0k+dk2n-1- -2); 4输出最短路径长度输出最短路径长度d02n-1- -1;算法设计与分析算法设计与分析动
57、态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 77 应用专题二|组合问题中的动态规划法组合问题中的动态规划法最大子段和问题最大子段和问题最长单调递增子序列问题最长单调递增子序列问题最长公共子序列问题最长公共子序列问题0/10/1背包问题背包问题算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 78 最大子段和问题|问题提出：问题提出：给定由给定由n个整数（可能为负数）组成的序列：个整数（可能为负数）组成的序列：a1,a2,an,求该序列的最大子段和。当所有整数求该序列的最大子段和。当所有整数均为负
58、数，定义其最大子段和为均为负数，定义其最大子段和为0 0。依其定义，所。依其定义，所求的最优值为：求的最优值为：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 79 最大子段和问题|动态规划算法动态规划算法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 80 最大子段和问题|算法描述：算法描述：int maxsum(int n,int *a)sum=0;b=0;for (i=1;i0) b+=ai;else b= ai;if (bsum) sum=b;return s
59、um;算法时间复杂性算法时间复杂性：T(n)=O(n) S(n)=O(1)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 81 最大子段和问题|算法描述：算法描述：int maxsum(int n,int *a)sum=0; b0=0;for (i=1;i0) bi=bi-1+ai;else bi= ai;if (bisum) sum=bi;return sum;算法复杂性算法复杂性：T(n)=O(n) S(n)=O(n)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳
60、 82 最大子段和问题|应用举例：应用举例：最佳游览路线问题最佳游览路线问题算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 83 最长单调递增子序列问题|问题描述：问题描述：求最长单调递增子序列问题。求最长单调递增子序列问题。|例如：例如：1 23 4 5 6 7 8 9 10 a:318714101223411624b:6353432121c:375767881010算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 84 算法设计与分析算法设计与分析动态规划动态规划
61、四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 85 最长公共子序列问题|子序列与公共子序列：子序列与公共子序列：一个给定序列的子序列一个给定序列的子序列序列序列X和和Y的公共子序列的公共子序列|问题提出：问题提出：给定给定2个序列个序列X=x1,x2,xm和和Y=y1,y2,yn，找出找出X和和Y的最长公共子序列。的最长公共子序列。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 86 最长公共子序列问题|例如：例如：对对xyzyxzxz和和xzyxxyzx两个序列两个序列nxxx为长度为为长度为3 3的公共子序
62、列，的公共子序列，nxzyz为长度为为长度为4 4的公共子序列。的公共子序列。nxzyxxz为长度为为长度为6 6的最长公共子序列。的最长公共子序列。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 87 最长公共子序列问题|应用：文本相似性测试应用：文本相似性测试在遗传学中，两个串对应链条在遗传学中，两个串对应链条DNA链，它们可能来自两链，它们可能来自两个个体，若它们对应的个个体，若它们对应的DNA序列有一条长的公共子序列，序列有一条长的公共子序列，则认为它们在遗传上是相关的。则认为它们在遗传上是相关的。在软件工程应用中，两个串
63、可能来自同一个程序的源代在软件工程应用中，两个串可能来自同一个程序的源代码的两个版本，希望确定两个版本之间有哪些变化。码的两个版本，希望确定两个版本之间有哪些变化。搜索引擎中的数据收集系统搜索引擎中的数据收集系统(也称也称web蜘蛛或爬虫蜘蛛或爬虫)必定必定能区分相似的能区分相似的web页面，避免不必要的页面，避免不必要的web页面请求。页面请求。Unin/linux中提供中提供diff程序，用于比较文本文件。程序，用于比较文本文件。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 88 最长公共子序列问题|问题分析：问题分析：若若
64、A的长度为的长度为m，若若B的长度为的长度为n，则则A和和B的子序的子序列个数分别为：列个数分别为：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 89 最长公共子序列问题穷举法穷举法n耗时太多，不可取，共需要进行串比较：耗时太多，不可取，共需要进行串比较：分治法分治法n此问题不可能简单地分解成几个独立的子问题，此问题不可能简单地分解成几个独立的子问题，也不能用分治法来解。也不能用分治法来解。动态规划法动态规划法算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 90 最
65、长公共子序列问题|最长公共子序列的最优子结构性质最长公共子序列的最优子结构性质设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长公的最长公共子序列为共子序列为Z=z1,z2,zk ，则，则n(1)若若xm=yn，则，则zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最长公共子序列。的最长公共子序列。n(2)若若xmyn且且zkxm，则，则Z是是xm-1和和Y的最长公共的最长公共子序列。子序列。n(3)若若xmyn且且zkyn，则，则Z是是X和和yn-1的最长公共的最长公共子序列。子序列。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院
66、计算机科学学院 刘芳刘芳 91 |由此可见：由此可见：两个序列的最长公共子序列包含了这两个序列的两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列前缀的最长公共子序列。因此，最长公共子序列问题具有问题具有最优子结构最优子结构性质。性质。 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 92 最长公共子序列问题|二、子问题的递归结构二、子问题的递归结构算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 93 最长公共子序列问题|三、计算最优
67、值三、计算最优值第一阶段第一阶段: :计算计算X1和和Yj的最长公共子序列的长度的最长公共子序列的长度c1j。第二阶段第二阶段: :计算计算X2和和Yj的最长公共子序列的长度的最长公共子序列的长度c2j 。第第m阶段阶段: :计算计算Xm和和Yj的最长公共子序列的长度的最长公共子序列的长度cmj 。(11jn)|注：注：第第m阶段的阶段的cmn 就是序列就是序列Xm和和Yn的最长公共子序列的的最长公共子序列的长度。长度。 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 94 最长公共子序列问题int LCSLegth(int m,
68、 int n, char *x, char *y,int* c,int *b)for (j=0; j=n; j+) c0j=0; /初始化第初始化第0行行 for (i=0; j=m; i+) ci0=0; /初始化第初始化第0列列for (i=1; i=m; i+) for (j=1; j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 95 例如：yjBDCABA 0123456xi0000000A10000111B20111122
69、C30112222B40112233D50122233A60122334B70122344222131133213221322122213212222222121122212算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 96 最长公共子序列问题|四、构造最长公共子序列四、构造最长公共子序列设设cmn=k， 则则Xm与与Yn的最长公共子序列：的最长公共子序列：z1z2zk，令，令i=m;j=n，则搜索过程如下：，则搜索过程如下：n若若bi,j=1，则则xi=yj，由性质由性质1 1知：知：zk=xi，下一搜索方向为下一搜索方向为c
70、i-1,j-1;n若若bi,j=2，则则xiyj，且且ci-1,jci,j-1，由性质由性质2 2知：下一搜索知：下一搜索方向为方向为ci-1,j;n若若bi,j=3，则则xiyj，且且ci-1,jci,j-1，由性质由性质3 3知：下一搜知：下一搜索方向为索方向为ci,j-1;算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 97 最长公共子序列问题得到如下递推关系得到如下递推关系n若若bi,j=1，则：则：zk=xi，i- -;j- -;k- -;n若若bi,j=2，则：则：i- -;n若若bi,j=3，则：则：j- -;从从i
71、=m , j=n开始搜索开始搜索，直到直到i=0或或j=0结束，此时结束，此时得到最长公共子序列得到最长公共子序列z1z2zk 。算法设计与分析算法设计与分析0 & j0) if (bij= =1) zk=xi; k-; i-; j-; else if (bij= =2) i-; else j-; 输出：输出： z1z2Zcmn 。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 99 例如：yjBDCABA 0123456xi0000000A10000111B20111122C30112222B40112233D50122233A
72、60122334B70122344222131133213221322122213212222222121122212最最长公共子序列：公共子序列： BCBA算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 100 最长公共子序列问题|算法分析：算法分析：时间复杂性时间复杂性(mn)；空间复杂性空间复杂性(mn)；算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 101 0-1背包问题|问题描述问题描述|例：例：n=3,(v1,v2,v3)=(25,24,15),(w1,
73、w2,w3)=(18,15,10),c=20。0-1背包问题的最优解为背包问题的最优解为:(x1,x2,x3)=(1,0,0)。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 102 0-1背包问题|1.0-11.0-1背包问题的最优子结构性质背包问题的最优子结构性质设设( (y1,y2,yn)是所给是所给0 01 1问题的一个最优解，问题的一个最优解，则则( (y2,y3,yn)是下面相应子问题的一个最优解，是下面相应子问题的一个最优解，算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机
74、科学学院 刘芳刘芳 103 0-1背包问题|2.2.建立递归关系（建立动态规划方程）建立递归关系（建立动态规划方程）所给所给0-1背包问题的子问题为：背包问题的子问题为：令：令：m(i，j)背包容量背包容量为j，可，可选择物品物品为i，i+1,n时0_1背包背包问题的最的最优值。（0jc）算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 104 0-1背包问题jmnj =物品物品 n vn wnj0 0 j wn|分析分析（1）边界条件边界条件算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算
75、机科学学院 刘芳刘芳 105 0-1背包问题jmiji,i+1,njmi+1,ji+1,nj-wimi+1,j-wii+1,n,+vijmi+1,ji+1,nmaxwij0 j wi(2)一般形式：一般形式：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 106 0-1背包问题即：计算即：计算m(i，j)的动态规划函数如下：的动态规划函数如下：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 107 0-1背包问题|3.计算最优值计算最优值n第第1阶段：确定阶段：确定m
76、(n，j) n第第2阶段：确定阶段：确定m(n-1，j) n第第3阶段：确定阶段：确定m(n-2，j)nn第第n阶段：确定阶段：确定m(1 ，j) (其中其中m1,c为原问题为原问题的最优值的最优值)其中：（其中：（0jc）|4.构造最优解构造最优解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 108 例如：|考虑如下考虑如下0-1背包问题背包问题: :nn=3, c=6n(v1, v2, v3) = (1, 2, 5), n(w1,w2,w3) = (2, 3, 4)|以下是计算过程：以下是计算过程：1.i=3, w3=4,
77、v3=5 m(3,0)=0, m(3,1)=0, m(3,2)=0, m(3,3)=0 m(3,4)=5, m(3,5)=5, m(3,6)=5算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 109 2.i=2, w2=3 ,v2=2 m(2,0)=m(3,0)=0 m(2,1)=m(3,1)=0 m(2,2) =m(3,2)=0 m(2,3)=maxm(3,3),m(3,0)+2=2 m(2,4)=maxm(3,4),m(3,1)+2=5 m(2,5)=maxm(3,5),m(3,2)+2=5 m(2,6)=maxm(3,6),
78、m(3,3)+2=5算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 110 3.i=1, w1=2, v1=1 m(1,0)=m(2,0)=0, m(1,1)=m(2,1)=0 m(1,2)=maxm(2,2),m(2,0)+1=1 m(1,3)=maxm(2,3),m(2,1)+1=2 m(1,4)=maxm(2,4),m(2,2)+1=5 m(1,5)=maxm(2,5),m(2,3)+1=5 m(1,6)=maxm(2,6),m(2,4)+1=6算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科
79、学学院计算机科学学院 刘芳刘芳 111 构造最优解：构造最优解：由于由于m(1,6) m(2,6)放物品放物品1 1，x1=1, c=cw1 = 4 比较比较m(2,4)与与m(3,4)是否相等是否相等不不放物品放物品2 2， x2=0 由于由于m(3,4) 0 放物品放物品3 3， x3 = 1即：即：最优解为（最优解为（1 1，0 0，1 1）算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 112 算法描述void Knapsack(int *v,int *w,int *x,int c,int n, int *m) /(1)初
80、始化边界条件初始化边界条件 for(j=0; j= c ; j+) if (jwn) mnj=0; /不可装入第不可装入第n件物件物品品else mnj=vn; /可装入第可装入第n件物品件物品 算法设计与分析算法设计与分析=1; i -) for(j=0; j wi ; j+) /0jwi mij=mi+1j; /不放入第不放入第i件物品件物品 for(j=wi; j=c; j+) / jwi , 可放入第可放入第i件物品件物品 mij=max(mi+1j, mi+1j-wi+vi); 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳
81、刘芳 114 算法描述/(3)构造最优解构造最优解for(i = 1; i n; i +) if(mic=mi+1c) xi = 0; else xi = 1; c=wi; xn = (mnc)?1:0; 该算法有两个弱点：该算法有两个弱点：1.算法要求物品重量算法要求物品重量wi为整数；为整数；2.从从m(i，j)的递归式容易看出，算法需要的递归式容易看出，算法需要O(nc)计算时间。当背包容量计算时间。当背包容量c很大时，很大时，算法需要的计算时间较多。算法需要的计算时间较多。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 1
82、15 思考（方法2）： 0-1背包问题|1.0-11.0-1背包问题的最优子结构性质背包问题的最优子结构性质设设( (y1,y2,yn)是所给是所给0 01 1问题的一个最优解，问题的一个最优解，则则( (y1,y2,yn-1)是下面相应子问题的一个最优解。是下面相应子问题的一个最优解。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 116 0-1背包问题|2.2.建立递归关系（建立动态规划方程）建立递归关系（建立动态规划方程）所给所给0-1背包问题的子问题为：背包问题的子问题为：令：令：m(i，j)背包容量为背包容量为j，可选择
83、物品为，可选择物品为1,2,i时时0_1背包问题的最优值。背包问题的最优值。（0jc）算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 117 0-1背包问题jm1j =物品物品 1 v1 w1j0 0 j w1|分析分析（1）边界条件边界条件算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 118 0-1背包问题jmij1,2,ijmi-1,j1,i-1j-wimi-1,j-wi1,i-1,+vijmi-1,j1,i-1maxwij0 j wi(2)一般形式：一般形式：
84、算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 119 0-1背包问题即：计算即：计算m(i，j)的动态规划函数如下：的动态规划函数如下：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 120 0-1背包问题|3.计算最优值计算最优值n第第1阶段：确定阶段：确定m(1， j) n第第2阶段：确定阶段：确定m(2，j) n第第3阶段：确定阶段：确定m(3，j)nn第第n阶段：确定阶段：确定m(n，j) (其中其中m（n,c）为原为原问题的最优值问题的最优值)其中：（其中
85、：（0jc）|4.构造最优解构造最优解算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 121 例如：|考虑如下考虑如下0-1背包问题背包问题: :nn=3, c=6n(v1, v2, v3) = (1, 2, 5), n(w1,w2,w3) = (2, 3, 4)|练习：练习：填表情况及求解最优解；填表情况及求解最优解；写出按上述方法求解写出按上述方法求解0/1背包的算法描述。背包的算法描述。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 122 |填表情况及最优解的
86、构造填表情况及最优解的构造算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 123 应用专题三|查找问题中的动态规划法查找问题中的动态规划法最优二叉查找树最优二叉查找树模糊查找（选讲）模糊查找（选讲）算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 124 最优二叉查找树|问题描述：问题描述：最优二叉查找树（最优二叉查找树（Optimal Binary Search Trees）n以以n个记录个记录r1, r2, , rn构成的二叉查找树中具构成的二叉查找树中具有最少平均
87、比较次数的二叉查找树。有最少平均比较次数的二叉查找树。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 125 |分析分析判定树判定树n折半查找折半查找un个结点的深度为个结点的深度为log2(n1)1。n折半查找假定：折半查找假定：u所有元素的查找概率是相等的。所有元素的查找概率是相等的。如果查找概率不相等，则不是最优的。如果查找概率不相等，则不是最优的。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 126 最优二叉查找树|例如：例如：已知：已知：n集合集合A, B
88、, C, D的查找概率是的查找概率是0.1, 0.2, 0.4, 0.3， 问：二叉查找树的平均比较次数分别为多少？问：二叉查找树的平均比较次数分别为多少？ABCD(1)(2)折半查找树折半查找树(3)BCDAABCD算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 127 最优二叉查找树|一、最优二叉查找树满足最优性原理一、最优二叉查找树满足最优性原理rkT(1,n)以以rk为根的二叉查找树为根的二叉查找树T(k+1,n)T(1,k- -1)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算
89、机科学学院 刘芳刘芳 128 最优二叉查找树|二、递归地定义最优值二、递归地定义最优值设：设：nT(i, j)是由记录是由记录ri, , rj(1ijn)构成的最优二叉查找构成的最优二叉查找树树nC(i, j)是最优二叉树的平均比较次数（是最优二叉树的平均比较次数（C(1, n)为原问题为原问题的解的解）。）。考虑从考虑从ri, , rj中选择一个记录中选择一个记录rk作为二叉查找作为二叉查找树的根结点，可以得到如下关系：树的根结点，可以得到如下关系：算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 129 最优二叉查找树|可以得到
90、如下动态规划函数可以得到如下动态规划函数： 算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 130 rkT(i,j)ri,rj以以rk为根的二叉查找树为根的二叉查找树T(k+1,j)T(i,k- -1)算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 131 |三、计算最优值三、计算最优值按对角线逐条计算每一个按对角线逐条计算每一个C(i, j)和和R(i, j)，得到最，得到最终表。终表。 01234100.10.41.11.7200.20.81.4300.41.04
91、00.35001234112 2332233333445(a)二维表二维表C(b)二维表二维表Rd=1d=2d=3d=1d=2d=3算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 132 |四、构造最优解四、构造最优解C(1, 4)1.7R(1, 4)=3 (元素元素r3为根为根)C(1, 2)0.4R(1, 2)=2 (元素元素r2为左子树根为左子树根)得到如下最优二叉查找树得到如下最优二叉查找树BCDA算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 133 应用专
92、题四|几何问题中的动态规划法几何问题中的动态规划法（选讲）（选讲）最优三角剖分最优三角剖分算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 134 本章小结：|动态规划法的基本要素动态规划法的基本要素|求解过程求解过程分析最优子结构分析最优子结构建立递归关系建立递归关系计算最优值计算最优值构造最优解构造最优解|几个典型示例几个典型示例算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 135 本章小结：|最优化问题最优化问题每个最优化问题都包含一组限制条件和一每个最优化问题都包含一组限制条件和一个优化函数个优化函数，符合限制条件的问题求解方符合限制条件的问题求解方案称为案称为可行解可行解，使优化函数取得最佳值的使优化函数取得最佳值的可行解称为可行解称为最优解最优解 。算法设计与分析算法设计与分析动态规划动态规划 四川师范大学四川师范大学 计算机科学学院计算机科学学院 刘芳刘芳 136 本章小结：|最优化问题的求解方法：最优化问题的求解方法：穷举法穷举法动态规划法动态规划法贪心法贪心法搜索法搜索法
