第五章-动态规划详解课件.ppt

1、动态规划动态规划（Dynamic Programming），在），在20 世纪世纪50年代由美国数学家年代由美国数学家Richard Bellman（理查德（理查德.贝尔曼）发明，作为贝尔曼）发明，作为的一种通用方法，对最优化问题提出的一种通用方法，对最优化问题提出，从而创建最优化问题，从而创建最优化问题的一种新算法设计技术的一种新算法设计技术动态规划，它是一种重要的应用数学工具。动态规划，它是一种重要的应用数学工具。至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，而最终把它作为一种而最终把它作为一种通用的通用的算法设

2、计技术，即包括某些非最优化问题。算法设计技术，即包括某些非最优化问题。多阶段决策过程最优化多阶段决策过程最优化：现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们

3、为了降低求解问题的难度，把求解过程分为降低求解问题的难度，把求解过程分为一系列阶段一系列阶段，各个阶段依次按照，各个阶段依次按照最优性原则计算，最后阶段计算得到最优性原则计算，最后阶段计算得到最优解最优解。包括。包括 分段分段、求解求解 两大步。两大步。求解算法求解算法求解算法求解算法求解算法求解算法：求解算法施加的状态是变化的。：求解算法施加的状态是变化的。当前状态只与其直接前趋状态有关，对其直接当前状态只与其直接前趋状态有关，对其直接前趋状态施加求解算法，成为当前状态。前趋状态施加求解算法，成为当前状态。(Principle of Optimality)：对特定问题该原则对特定问题该原则不

4、一定满足（罕见），有必要检查其适用性。不一定满足（罕见），有必要检查其适用性。子实例组成父实例，父实例分解为子实例。子实例组成父实例，父实例分解为子实例。对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波那契序列的动态规划算法，它们属于非最优化问题的动态规划法。那契序列的动态规划算法，它们属于非最优化问题的动态规划法。：1.分阶段（级）决策。对最优化问题，用最优性原则设计。分阶段（级）决策。

5、对最优化问题，用最优性原则设计。2.一般采用一般采用（规模减小），（规模减小），（规模增加）。（规模增加）。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。问题问题：设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上 节点值之和最大节点值之和最大。分段分段：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。无法分段的问题，不能用动态规划法求解。无法分段的问题，不能用动态规划法求解。求解求解：动态规划

6、法求解。自底向上计算，各实例计算满足最优性原则，：动态规划法求解。自底向上计算，各实例计算满足最优性原则，如实例如实例18的子实例为的子实例为12和和7，max(12+6,7+6)=18。5 级级4 级级3 级级2 级级1级级18 27 39 3267 46 6578 73911311874014261582467131211w 输入规模输入规模：为便于分析，选择数塔层数：为便于分析，选择数塔层数k(k0)；w 基本操作基本操作：节点值求和运算；：节点值求和运算；增长函数增长函数：加法次数与：加法次数与 k 的关系；的关系；w 效率类别效率类别：没有最佳、最差情况；（都要从塔顶计算到塔底）：没

7、有最佳、最差情况；（都要从塔顶计算到塔底）w 增长率（次数）增长率（次数）：各层节点数升序：各层节点数升序：1,2,3,4,6,7,8,9,10,.节点总数节点总数 n 升序：升序：1,3,6,10,21,28,36,45,55,.层数层数k（顶为（顶为1）：）：1,2,3,4,6,7,8,9,10,.路径总数路径总数 t 升序：升序：2,4,8,32,.,t=,k11.穷举法穷举法：T(k)=(k-1)2k-1，k1 （）本例本例k=5，每条路径上，每条路径上5个节点做个节点做4次加法，共次加法，共64次加法。次加法。2.动态规划法动态规划法：（：（层节点数层节点数=层数层数）自底向上计算，

8、自底向上计算，k层加法总数为层加法总数为k-1层节点数层节点数2，有效率计算式：，有效率计算式：T(k)=2(k-1+.+3+2+1)=k(k-1),k1 （）本例加法总数本例加法总数 2(4+3+2+1)=20次，比次，比64次少很多。次少很多。问题问题：在：在mn棋盘上，求马从棋盘上，求马从P点跳到点跳到Q点的所有路径。点的所有路径。PQPQPQPQPQPQ可用回溯法和递归法求解，可用回溯法和递归法求解，但递归法效率但递归法效率很低，栈空间占用很大。很低，栈空间占用很大。问题：问题：n(n1)堆沙子，重量向量堆沙子，重量向量 W=(w1,.wn)。要将它们归并为。要将它们归并为1堆，堆，归

9、并规则：每次只能将相邻归并规则：每次只能将相邻2堆归并为堆归并为1堆，经过堆，经过 n-1 次归并后，次归并后，最终归并为一堆。总代价为归并过程中最终归并为一堆。总代价为归并过程中沙堆质量之和，沙堆质量之和，这个代价最小的归并树称为最小代价子母树。这个代价最小的归并树称为最小代价子母树。分析分析：属于最优化问题，目标为总代价最小。：属于最优化问题，目标为总代价最小。分段分段：显然需要：显然需要 n-1 次归并才能将次归并才能将 n 堆归并为堆归并为 1 堆。自然地可以将每次堆。自然地可以将每次 归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。归并划分为一个阶段，成为多阶段决策问题，尝试

10、动态规划法。求解求解：（此处采用：（此处采用自底向上自底向上的分析，找规律较简洁）的分析，找规律较简洁）当当 n=2 时：仅一种归并法即时：仅一种归并法即2合合1。当当 n=3 时：有时：有2种归并方法，第一种归并方法如图，种归并方法，第一种归并方法如图，后后2堆。堆。1378f(i,j)从第从第 i 堆到第堆到第 j 堆的代价和。堆的代价和。g(i,j)从第从第 i 堆到第堆到第 j 堆的重量和。堆的重量和。f(1,3)=15+28=（最优结果）（最优结果）=f(,)+g(,3)3级级2级级1级级13781621418n=3时：第二种归并方法，时：第二种归并方法，后后1堆。堆。n=4时：有时

11、：有3大类归并法。大类归并法。后后3堆、堆、后后2堆、堆、后后1堆。堆。因因3堆有堆有2种归并法，所以一共种归并法，所以一共5小类归并法。小类归并法。第第1种情况：种情况：781613f(1,4)=15+31+44=+g(1,4)w不变不变 =f(,)+g(2,)+g(,4)若若f(2,4)越小，则越小，则f(1,4)就越小。就越小。1378f(i,j)从第从第 i 堆到第堆到第 j 堆的代价和。堆的代价和。g(i,j)从第从第 i 堆到第堆到第 j 堆的重量和。堆的重量和。f(1,3)=20+28=f(,)+g(1,)3级级2级级1级级4级级3级级2级级1级级n=4 时：前时：前1堆的第堆的

12、第2种情况。种情况。781613f(1,4)=24+31+44=+g(1,4)w不变不变 =f(,)+g(,4)+g(,4)若若f(2,4)越小，则越小，则f(1,4)就越小。就越小。n=4 时：前时：前2堆情况。堆情况。781613f(1,4)=20+24+44=+g(1,4)若若f(1,2)+f(3,4)越小，越小，f(1,4)就越小就越小4级级3级级2级级1级级3级级2级级1级级n=4 时：前时：前3堆的第堆的第1种情况。种情况。781613n=4 时：前时：前3堆的第堆的第2种情况。种情况。f(1,4)=20+28+44=+g(1,4)w不变不变 =f(,)+g(1,)+g(1,)若若

13、f(1,3)越小，则越小，则f(1,4)就越小。就越小。781613f(1,4)=15+28+44=+g(1,4)w不变不变 =f(,)+g(,3)+g(1,)若若f(1,3)越小，则越小，则f(1,4)就越小。就越小。4级级3级级2级级1级级4级级3级级2级级1级级将将 n=4 归纳为归纳为 3 大类情况：大类情况：f(1,4)=前前1堆堆 前前2堆堆 前前3堆堆将将n=4 计算式推广，对于任意的计算式推广，对于任意的 n(n1)，归纳出如下公式：，归纳出如下公式：f(1,n)=前前1堆堆 前前2堆堆 前前3堆堆 .前前n-1堆堆上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法

14、上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法不能用方程形式给出，只能是描述性的。不能用方程形式给出，只能是描述性的。F(1,n)在在(13,7,8,16,21,4,18)上的结果上的结果jikkwjikkw实例实例：计算裴波那契数的递归版本。：计算裴波那契数的递归版本。递推式：递推式：n 1，F(0)=0,F(1)=1例如，例如，F(5)计算过程用计算过程用 表示：表示：F(5)F(4)F(3)F(2)F(3)F(1)F(2)F(1)F(0)F(0)F(1)F(2)F(1)F(0)F(1)树中可以看出，计算树中可以看出，计算F(5)时要重复计算时要重复计算F(2)、F(3)显

15、然降低时间效率。此即交叠子问题，显然降低时间效率。此即交叠子问题，F(5)分为分为两个子问题两个子问题 F(4)和和 F(3)，F(4)包含了包含了F(3)。动态规划法：自底向上计算动态规划法：自底向上计算依次计算依次计算F(0),F(1),F(2),.,F(n)，各次计算结果存入数组，各次计算结果存入数组，最后一个元素就是最后一个元素就是F(n)。用一个。用一个单循环即可简单实现。单循环即可简单实现。（区别于完全最短路径问题）（区别于完全最短路径问题）概念概念：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点 的最短路径，此即

16、单起点（单源）最短路径问题。的最短路径，此即单起点（单源）最短路径问题。完全最短路径完全最短路径 问题问题要求找到从要求找到从每个顶点每个顶点到其他到其他所有顶点所有顶点之间的最短路径。之间的最短路径。分段分段：图示求解过程：红色数字为实例求解结果（最优性原则）图示求解过程：红色数字为实例求解结果（最优性原则）4本例：带权有向图本例：带权有向图23109 67103848965484源点源点收点收点前面我们已经讲过前面我们已经讲过BST的相关算法及特性，本节介绍什么是最优的相关算法及特性，本节介绍什么是最优 BST，以及用动态规划算法来构造以及用动态规划算法来构造 BST。：基于统计先验知识，

17、我们可统计出一个数表（集合）中：基于统计先验知识，我们可统计出一个数表（集合）中 各元素的各元素的，理解为集合各元素的，理解为集合各元素的出现频率出现频率。比如中文输入法。比如中文输入法 字库中各词条（单字、词组等）的字库中各词条（单字、词组等）的先验概率先验概率，针对用户习惯可以自动，针对用户习惯可以自动 调整词频调整词频所谓动态调频、所谓动态调频、高频先现高频先现原则，以减少用户翻查次数。原则，以减少用户翻查次数。这就是这就是：查找过程中键值比较次数最少，或者说：查找过程中键值比较次数最少，或者说 希望希望。为解决这样的。为解决这样的 问题，显然需要对集合的每个元素赋予一个特殊属性问题，显

18、然需要对集合的每个元素赋予一个特殊属性 查找概率。查找概率。：最优最优BST整棵树的整棵树的最小。最小。BST 好处是查找效率高，好处是查找效率高，平均查找效率属于平均查找效率属于logn型，最坏为线性（完全不平衡）。型，最坏为线性（完全不平衡）。w 已知已知：4个键个键 a1,a2,a3,a4，出现概率依次为，出现概率依次为 0.1,0.2,0.4,0.3 w 要求要求：构造包含这：构造包含这4个键的最优个键的最优BST。w 策略策略：生成包含生成包含4个键的个键的，共，共14种。然后计算每个种。然后计算每个BST的的 平均键值比较次数平均键值比较次数，从中选择比较次数最小的作为最优，从中选

19、择比较次数最小的作为最优BST。包含包含 n 个键的个键的BST总数等于第总数等于第 n 个个卡塔兰数卡塔兰数：210,()1nnnc nCn 比较比较1次次比较比较2次次比较比较3次次比较比较4次次比较比较1次次比较比较2次次比较比较3次次0.11+0.22+0.43+0.34=0.21+0.12+0.42+0.33=一定存在键值平均比较一定存在键值平均比较次数最少的最优次数最少的最优 BST。w 问题：问题：n个键个键 ，查找概率，查找概率 ，构成最优，构成最优BST，表示为表示为 ，求这棵树的平均查找次数，求这棵树的平均查找次数 （耗费最低）。（耗费最低）。换言之，如何构造这棵最优换言之

20、，如何构造这棵最优BST，使得，使得 C1,n 最小。最小。w 分段求解分段求解：动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解 由其直接前趋实例解计算得到。对于最优由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和问题，利用减一技术和 最优性原则，如果前最优性原则，如果前 个节点构成最优个节点构成最优BST，加入一个节点加入一个节点 an 后后 要求构成规模要求构成规模 的最优的最优BST。按。按 n-1,n-2,.,2,1 递归，问题可解。递归，问题可解。：C1,2C1,3.。为不失一般性用为不失一般性用

21、 Ci,j 表示由表示由 构成的构成的BST的耗费。其中的耗费。其中 1i j n。这棵树表示为。这棵树表示为 。，它的，它的 左子树为左子树为 ，右子树为，右子树为 。要求选择的。要求选择的 k 使得整棵树的平均查找使得整棵树的平均查找 次数次数 Ci,j最小。左右子树递归执行此过程。（最小。左右子树递归执行此过程。（）1,.,naa1,.,npp1nT,.,ijaajiTka1kiT 1jkT 1,.,ikaa 最优最优BST1,.,kjaa 最优最优BST1111,.,.,.,.,.ikkjikkkkjppappaapaa 根根左左子子树树右右子子树树键键值值：概概率率：k-1=i：左子

22、树缩为单节点。：左子树缩为单节点。k+1=j：右子树缩为单节点。：右子树缩为单节点。11,11111()()(,m)1inmi1(1)njkllrrl ir kjkllrrl irkjkkli kji kjC i krir kklp L ap L apCL ap L appjpip 整整树树平平均均左左子子树树（成成功功查查找找）右右子子树树（成成功功查查找找）左左子子树树平平均均根根全全部部节节点点概概率率和和右右子子树树 1,11,minC kji kjjss iC i kCpjCki j 平平均均1i j n递推计算式递推计算式例：例：4个键个键 a1,a2,a3,a4，出现概率依次为，

23、出现概率依次为 0.1,0.2,0.4,0.3，求求：构造包含这：构造包含这4个键的最优个键的最优BST。（。（n=4）解：计算公式如下：解：计算公式如下：1,11,miniijskijjsnC i jC i kjpC k 2121,12211,2min0.1:1,02,200.20.420.30.5:1,13,20.100.34kssijsskCCpCCpCk 最最优优根根31311,331311:1,00.00.2,30.81,371.52:1,min31,20.4113,30.10.40.71.2:4,3.10.00.7ssssijsskkCpkCCpCCCkCp 最最优优根根k 是选择

24、的根节点下标。上面是选择的根节点下标。上面 是下页的计算结果。是下页的计算结果。3232,23322:2,13,300.2,3min340.61.0:2,24,30.200.60.8ssijsskkCCpCCkCp 最最优优根根 1,11,miniijskijjsnC i jC i kjpC k 计算公式：计算公式：41414114,41411:1,00.01.022,42,43,43,41,:1,10.11.03:4,40.31.01.74:5,40.01.02.4min1,210.41,31.1ssssijsssksCCCCkCpkCpkCpkCpCCC 434344,33:3,24,40

25、.031.00.30.74:3,35,40.40.00.71.3,min14ssijkssCCpkCpCkC 最最优优根根 1,11,miniijskijjsnC i jC i kjpC k 计算公式：计算公式：42422,422442:2,10.00.91.9:2,23,41.02,44,40.20.30.94:5,40min31.42,30.8.00.91.7ssssijsskkCpCCpkCCkCCp 最最优优根根414141,4141142,41.43,41.1:1,00.01.02.42:1,10.11.02.1:4,40.31.04:5,40.01.02.01,4min31,20.

26、41.71,31.11ssssijkssssCkCpkCCCkCCpCpkCp 最最优优根根 已知已知 4个键个键 a1,a2,a3,a4，出现概率依次为，出现概率依次为 0.1,0.2,0.4,0.3。各阶段计算结果，例如各阶段计算结果，例如 C2,4=：图中箭头表示图中箭头表示的一对元素，将的一对元素，将与与(p2+p3+p4)相加相加C2,4=0.5+(0.2+0.4+0.3)=1.4。如此计算。如此计算Ci,j,1ijn=4。实际计算过程的实际计算过程的 i、j 范围范围 i:1n-1，j:2n，图中红色数字。，图中红色数字。w 本例计算结果本例计算结果：1,.,ikaa 最优最优BS

27、T1,.,kjaa 最优最优BST1111:,.,.,ikkkjikkjkBSTaaaaaaaaaa 根根左左子子树树右右子子树树键键值值：根表可知，根表可知，4个键的最优根下标为个键的最优根下标为3 即即a3键。它的左子树为键。它的左子树为a1 a2键键，右子树右子树为为a4键。左子树是什么结构呢？再看根表，键。左子树是什么结构呢？再看根表，a1 a2 构成的最优子树根是构成的最优子树根是a2。因为因为a1 a2，所以，所以1键是键是2键的左节点。键的左节点。procedure SUBTREE-ROOT/w 权值矩阵权值矩阵,C代价矩阵代价矩阵,r最优树根列表最优树根列表begin for

28、i1 to n dobegin wi,iqi;Ci,i0;end;for l1 to n do for i0 to n-1 dobegin ji+1;wi,jwi,j-1+pj+qj;令令m是使得是使得Ci,k-1+Ck,j最小的最小的k值值(ik=j);Ci,jwi,j+Ci,m-1+Cm,j;ri,jam;end;endp;已知已知：n 个重量个重量 w1,.,wn、价值、价值 v1,.,vn 的物品和一个承重量的物品和一个承重量W的背包。的背包。要求要求：找出最有价值子集，且能装入背包中（不超重）。：找出最有价值子集，且能装入背包中（不超重）。假定假定：物品重量、背包承重量、：物品重量、

29、背包承重量、物品数量物品数量（01背包）都是整数。背包）都是整数。：求满足约束方程的是目标函数达到最大的解向量求满足约束方程的是目标函数达到最大的解向量 X=(x1,.,xn)。穷举穷举n个物品全部组合（幂集，子集数个物品全部组合（幂集，子集数=2n），从中找出最有价值子集。），从中找出最有价值子集。贪婪法不一定能找到最优解。贪婪法不一定能找到最优解。11max(,)nniiiiiiwWxVvnxW物品数物品数承重量承重量 动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解 由直接前趋子实例解计算得到。对于由直接前趋子实例解

30、计算得到。对于01背包问题，可利用减一技术和背包问题，可利用减一技术和 最优性原则，按物品数量和背包承重量分段。最优性原则，按物品数量和背包承重量分段。前前 i 个物品中最优子集的总价值（动态规划函数）：个物品中最优子集的总价值（动态规划函数）：（0个物品），个物品），（承重量（承重量0）第第 i 个物品不能装入，个物品不能装入，j wi（不超重）（不超重）第第1阶段：装入阶段：装入1个物品，计算各种承重量下的最优价值子集；个物品，计算各种承重量下的最优价值子集；第第2阶段：装入阶段：装入2个物品，计算各种承重量下的最优价值子集；个物品，计算各种承重量下的最优价值子集；第第n阶段：装入阶段：装

31、入n个物品，计算各种承重量下的个物品，计算各种承重量下的。前前 i 个物品中最优子集的总价值（动态规划函数）：个物品中最优子集的总价值（动态规划函数）：（0个物品），个物品），（承重量（承重量0）第第 i 个物品不能装入，个物品不能装入，j wi（不超重）（不超重）说明：可按行（或列）填写此表。说明：可按行（或列）填写此表。w 例：例：01背包数据如下表，求：能够放入背包的最有价值的物品集合。背包数据如下表，求：能够放入背包的最有价值的物品集合。自底向上：按行或列填表。递推公式：自底向上：按行或列填表。递推公式：444(3,5)(4,5)(3,5)(3,5)(3,3)321522maxmaxm

32、ax37VVvVwVvV (1,)max(,)(1,)iiV ijVvjwi jV i 例如：例如：接下来，找出最优解的物品集合。接下来，找出最优解的物品集合。w 通过最优解的回溯，找出最优子集为通过最优解的回溯，找出最优子集为 w1,w2,w4 44244(3,5maxmax(3,5)32(4,537)1522wwVwVVv 放放入入未未放放入入33333(3,3)(2,322maxmax)2002(2,03)wwVvVwV 放放入入入入未未放放22142(1,3maxmax(1,3)12(2,322)1012wwVwVVv 放放入入未未放放入入11112(0,2)0(1,2)(0,maxmax2)12012wwVVvVw 放放未未放放入入入入最优解有最优解有w4最优解无最优解无w3最优解有最优解有w2最优解有最优解有w1最最 优优 解解 回回 溯溯2