动态规划详解PPT课件

动态规划概述,动态规划概述动态规划（DynamicProgramming），在20世纪50年代由美国数学家RichardBellman（理查德.贝尔曼）发明，作为多阶段决策过程最优化的一种通用方法，对最优化问题提出最优性原则，从而创建最优化问题的一种新算法设计技术动态规划，它是一种重要的应用数学工具。至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，而最终把它作为一种通用的算法设计技术，即包括某些非最优化问题。多阶段决策过程最优化：现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了降低求解问题的难度，把求解过程分为一系列阶段，各个阶段依次按照最优性原则计算，最后阶段计算得到最优解。包括分段、求解两大步。注：不能段化的问题不能用动态规划法求解。,最优性原则,多阶段决策过程图示,动态的含义：求解算法施加的状态是变化的。当前状态只与其直接前趋状态有关，对其直接前趋状态施加求解算法，成为当前状态。最优性原则(PrincipleofOptimality)：一个最优问题任何实例的最优解，是由该实例的子实例的最优解组成的。对特定问题该原则不一定满足（罕见），有必要检查其适用性。子实例组成父实例，父实例分解为子实例。,对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波那契序列的动态规划算法，它们属于非最优化问题的动态规划法。动态规划法的特点：1.分阶段（级）决策。对最优化问题，用最优性原则设计。2.一般采用自顶向下分析（规模减小），自底向上计算（规模增加）。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。,数塔,数塔问题：设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上节点值之和最大。,分段：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。无法分段的问题，不能用动态规划法求解。求解：动态规划法求解。自底向上计算，各实例计算满足最优性原则，如实例18的子实例为12和7，max(12+6,7+6)=18。,5级4级3级2级1级,数塔问题：动态规划法与穷举法效率比较,数塔：动态规划法与穷举法的时间效率比较输入规模：为便于分析，选择数塔层数k(k0)；基本操作：节点值求和运算；增长函数：加法次数与k的关系；效率类别：没有最佳、最差情况；（都要从塔顶计算到塔底）增长率（次数）：各层节点数升序：1,2,3,4,5,6,7,8,9,10,.节点总数n升序：1,3,6,10,15,21,28,36,45,55,.层数k（顶为1）：1,2,3,4,5,6,7,8,9,10,.路径总数t升序：2,4,8,16,32,.,t=2k-1,k11.穷举法：T(k)=(k-1)2k-1，k1（指数级）本例k=5，每条路径上5个节点做4次加法，共64次加法。2.动态规划法：（层节点数=层数）自底向上计算，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点的所有路径。,654321,654321,654321,可用回溯法和递归法求解，但递归法效率很低，栈空间占用很大。,最小代价子母树,最小代价子母树问题：n(n1)堆沙子，重量向量W=(w1,.wn)。要将它们归并为1堆，归并规则：每次只能将相邻2堆归并为1堆，经过n-1次归并后，最终归并为一堆。总代价为归并过程中新产生的沙堆质量之和，这个代价最小的归并树称为最小代价子母树。分析：属于最优化问题，目标为总代价最小。分段：显然需要n-1次归并才能将n堆归并为1堆。自然地可以将每次归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。求解：（此处采用自底向上的分析，找规律较简洁）当n=2时：仅一种归并法即2合1。当n=3时：有2种归并方法，第一种归并方法如图，前1堆后2堆。,f(i,j)从第i堆到第j堆的代价和。g(i,j)从第i堆到第j堆的重量和。f(1,3)=15+28=43（最优结果）=f(2,3)+g(1,3),序号123,最小代价子母树(续1)n=4,n=3时：第二种归并方法，前2堆后1堆。,n=4时：有3大类归并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。因3堆有2种归并法，所以一共5小类归并法。前1堆第1种情况：,7,8,16,31,15,序号1234,13,44,f(1,4)=15+31+44=90=f(2,4)+g(1,4)w不变=f(2,3)+g(2,4)+g(1,4)若f(2,4)越小，则f(1,4)就越小。,13,7,8,20,28,f(i,j)从第i堆到第j堆的代价和。g(i,j)从第i堆到第j堆的重量和。f(1,3)=20+28=48=f(1,2)+g(1,3),序号123,3级2级1级,4级3级2级1级,最小代价子母树(续2)n=4,n=4时：前1堆的第2种情况。,7,8,16,24,31,13,44,序号1234,f(1,4)=24+31+44=99=f(2,4)+g(1,4)w不变=f(3,4)+g(2,4)+g(1,4)若f(2,4)越小，则f(1,4)就越小。,n=4时：前2堆情况。,7,8,16,24,20,13,44,序号1234,f(1,4)=20+24+44=88=f(1,2)+f(3,4)+g(1,4)若f(1,2)+f(3,4)越小，f(1,4)就越小,4级3级2级1级,3级2级1级,最小代价子母树(续3)n=4,n=4时：前3堆的第1种情况。,7,8,16,20,28,13,44,n=4时：前3堆的第2种情况。,序号1234,f(1,4)=20+28+44=92=f(1,3)+g(1,4)w不变=f(1,2)+g(1,3)+g(1,4)若f(1,3)越小，则f(1,4)就越小。,7,8,16,15,28,13,44,序号1234,f(1,4)=15+28+44=87最优=f(1,3)+g(1,4)w不变=f(2,3)+g(1,3)+g(1,4)若f(1,3)越小，则f(1,4)就越小。,4级3级2级1级,4级3级2级1级,最小代价子母树(续4)n=4,将n=4归纳为3大类情况：f(1,4)=minf(2,4),f(1,2)+f(3,4),f(1,3)+g(1,4)前1堆前2堆前3堆将n=4计算式推广，对于任意的n(n1)，归纳出如下公式：f(1,n)=minf(2,n),f(1,2)+f(3,n),f(1,3)+f(4,n),.,f(1,n-1)+g(1,n)前1堆前2堆前3堆.前n-1堆上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法不能用方程形式给出，只能是描述性的。,F(1,n)在(13,7,8,16,21,4,18)上的结果,/w1.n:n堆沙子的质量序列/g1.n;1.n:gi,j=/f1n:1n:fI,j表示第i层从第j个位置开始i堆沙子的最小归并代价,并约定f1,i=0proceduremincpt(w)begin计算gi,j=gj,i=fi,j0(1in,1jn);fori2tondo/i表示层次,也是归并沙子的堆数,在上图中,表示行号forj1ton-i+1do/表示列号beginminfi-1,j;forki-1step-1untill1doifminfk,j+fi-k,j+kthen/minf(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)minfk,j+fi-k,j+k;fi,jgj,i+j-1+min;end;return(fn,1);endp;,递推求解中的交叠子问题,递推求解中的交叠子问题（非最优化问题）实例：计算裴波那契数的递归版本。递推式：n1，F(n)=F(n-1)+F(n-2)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)显然降低时间效率。此即交叠子问题，F(5)分为两个子问题F(4)和F(3)，F(4)包含了F(3)。,动态规划法：自底向上计算依次计算F(0),F(1),F(2),.,F(n)一次，各次计算结果存入数组，最后一个元素就是F(n)。用一个单循环即可简单实现。,单起点最短路径问题,单起点最短路径问题（区别于完全最短路径问题）概念：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点的最短路径，此即单起点（单源）最短路径问题。完全最短路径问题要求找到从每个顶点到其他所有顶点之间的最短路径。分段：顶点集分为k个不相交子集Vd,1dk,k2,级内顶点不相邻。任一条边(u,v)，uVd，vVd+m，m1。令|V1|=|Vk|=1。,从源点到收点依次编号,V1,V2,V3,V4,V5,对于一个有k级的动态规划,需要列出从s到t的每一条路上的k-2次判定结果.其中第i级判定是利用最优化原理确定Vi+1中的哪一个顶点在可能得到的最佳线路上.设D(i,j)是从顶点集Vi中的点j到t的一条最小耗费路线,cost(i,j)是这条路线的耗费.由后向前推算,得:cost(i,j)=minC(j,l)+cost(i+1,l)C(j,l):表示顶点集Vi中的顶点j到顶点集Vi+1中的点l的耗费cost(i+1,l):表示顶点集Vi+1中的点l到目标点t的耗费,cost(3,5)=min(4+cost(4,8),8+cost(4,9)=min(4+8,8+4)=12/第三层中,顶点5到终点的耗费cost(3,6)=min(9+cost(4,8),6+cost(4,9)=min(9+8,6+4)=10/取顶点9cost(3,7)=min(5+cost(4,8),4+cost(4,9)=min(5+8,4+4)=8cost(2,2)=min(10+cost(3,5),9+cost(3,6)=min(10+12,9+10)=19cost(2,3)=min(6+12,7+10,10+8)=17cost(2,4)=min(3+10,8+8)=13/取顶点6cost(1,1)=min(4+19,2+17,3+13)=16/取顶点4,由cost(1,1)=3+cost(2,4)记下结点4由cost(2,4)=3+cost(3,6)记下结点6由cost(3,6)=6+cost(4,9)记下结点9即D(1,1)=4,D(2,4)=6,D(3,6)=9,D(4,9)=10所以得到线路:1,4,6,9,10,/最短路径算法输入:图的顶点编号表,各顶点的邻接表,边的耗费函数C(i,j)表.输出:从s到t的一条最小耗费路线及其耗费cost(1,s),即cost(1)procdureFGRAPHbeginfori1tondocosti0;forjn-1step-1to1dobegin设顶点r使(j,r)E,且C(j,r)+costr最小;/耗费时间(n+E)costjC(j,r)+costr;Djr;/记下最短路径经历的顶点End;p11;/找最小耗费路线pkn;forj2tok-1dopjDpj-1;endp;,最优二叉查找树,最优二叉查找树（最优BST）前面我们已经讲过BST的相关算法及特性，本节介绍什么是最优BST，以及用动态规划算法来构造BST。最优BST概念问题的提出：基于统计先验知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性查找概率。最优BST：最优BST整棵树的平均键值比较次数最小。BST好处是查找效率高，平均查找效率属于logn型，最坏为线性（完全不平衡）。,举例说明：解最优BST问题的蛮力策略（穷举法）,举例说明：解最优BST问题的蛮力策略（穷举法）已知：4个键a1,a2,a3,a4，出现概率依次为0.1,0.2,0.4,0.3要求：构造包含这4个键的最优BST。策略：穷举生成包含4个键的全部BST，共14种。然后计算每个BST的平均键值比较次数，从中选择比较次数最小的作为最优BST。包含n个键的BST总数等于第n个卡塔兰数：BST的平均键值比较次数的计算：（统计平均）,它以4n/n1.5速度(+),包含4个键的两种BST（非最优）,左树：0.11+0.22+0.43+0.34=2.9右树：0.21+0.12+0.42+0.33=2.1结论：一定存在键值平均比较次数最少的最优BST。,动态规划法生成最优BST算法原理,动态规划法生成最优BST算法原理问题：n个键，查找概率，构成最优BST，表示为，求这棵树的平均查找次数C1,n（耗费最低）。换言之，如何构造这棵最优BST，使得C1,n最小。分段求解：（自顶向下分析：规模减小）动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和最优性原则，如果前n-1个节点构成最优BST，加入一个节点an后要求构成规模n的最优BST。按n-1,n-2,.,2,1递归，问题可解。自底向上计算：C1,2C1,3.C1,n。为不失一般性用Ci,j表示由构成的BST的耗费。其中1ijn。这棵树表示为。从中选择一个键作根节点，它的左子树为，右子树为。要求选择的k使得整棵树的平均查找次数Ci,j最小。左右子树递归执行此过程。（根的生成过程）,动态规划法生成最优BST算法原理（续）,ak,pk,根层：L(ak)=1,k-1=i：左子树缩为单节点。k+1=j：右子树缩为单节点。kj：右子树为空树。,1ijn,自顶向下分析,递推计算式,举例说明：动态规划法生成最优BST过程,举例说明：动态规划法生成最优BST过程例：4个键a1,a2,a3,a4，出现概率依次为0.1,0.2,0.4,0.3，求：构造包含这4个键的最优BST。（n=4）解：计算公式如下：,自底向上计算：C1,2C1,3.C1,n（本例n=4）,k是选择的根节点下标。上面C2,3=0.8是下页的计算结果。,12两个键,123三个键,举例说明：动态规划法生成最优BST过程（续1）,举例说明：动态规划法生成最优BST过程（续1）,计算公式：,23两个键,最终结果：1234四个键,34两个键,举例说明：动态规划法生成最优BST过程（续2）,举例说明：动态规划法生成最优BST过程（续2）,计算公式：,最终结果：1234四个键,234三个键,将各阶段计算结果用主表C和根表R描述如下：,动态规划算法：主表C和根表K,各阶段计算结果用主表C和根表R描述：计算过程中有j=0情况，所以j从0开始编号。已知4个键a1,a2,a3,a4，出现概率依次为0.1,0.2,0.4,0.3。,主表Ci,j,各阶段计算结果，例如C2,4=1.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，图中红色数字。,根表Ri,j,动态规划法算例的计算结果图,本例计算结果：,根表Ri,j,根表可知，4个键的最优根下标为3即a3键。它的左子树为a1a2键，右子树为a4键。左子树是什么结构呢？再看根表，a1a2构成的最优子树根是a2。因为a1a2，所以1键是2键的左节点。,最终结果图,动态规划法生成最优BST算法,动态规划法生成最优BST算法,procedureSUBTREE-ROOT/w权值矩阵,C代价矩阵,r最优树根列表beginfori1tondobeginwi,iqi;Ci,i0;end;forl1tondofori0ton-1dobeginji+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;,procedureBUILDTREE(i,j)begincreattherootofTi,j,thatis,nodevi,jMarkvi,jbyrij;Letmbethesubscriptofri,jifim-1thenBUILDTREE(i,m-1);/Buildtheleftsubtreeofvi,j;ifmjthenBUILDTREE(m,j);/Buildtherightsubtreeofvi,jendp;,动态规划法解01背包,动态规划法解01背包问题描述已知：n个重量w1,.,wn、价值v1,.,vn的物品和一个承