《算法设计动态规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法设计动态规划ppt课件.ppt（69页珍藏版）》请在三一办公上搜索。
1、动态规划法,2022/11/13,2,方法概述: 发展及研究内容,动态规划(dynamic programming)是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、资源分配、设备更新等问题，用动态规划比用其它方法求解更为方便
2、。,2022/11/13,3,方法概述: 发展及研究内容,虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。,2022/11/13,4,方法概述: 基本思想,动态规划的思想实质是分治思想和解决冗余。 与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。如果能够保存已解决的子问题的答案，在需
3、要时再查找，这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。,2022/11/13,5,方法概述: 求解步骤,1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；4、根据计算最优值时记录的信息，构造最优解。注：步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息是构造最优解的基础,2022/11/13,6,方法概述: 适用条件,
4、动态规划法的有效性依赖于问题本身所具有的两个重要性质最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。,2022/11/13,7,方法概述: 最优性原理及举例,Bellman给出这个原理作为动态规划的适用条件，后来Morin在1982年证明了这只是一个充分条件而非必要条件。Bellman的原定义如下： An optimal policy
5、 has the property that whatever the initial state and initial decision are, then remaining decisions must constitute an optimal policy with regard to the state resulting from first decision. 最优性原理又称为最优子结构性质： 如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。即一个最优策略的子策略总是最优的。,2022/11/13,8,方法概述: 最优性原理及举例（续）,例1：设G是一个
6、有向加权图，则G从顶点i到顶点j之间的最短路径具有最优子结构性质。证明：（反证） 设iipiq j是一条最短路径，但其中子路径ipiq j不是最优的，假设最优的路径为ipiq j 则我们重新构造一条路径：iipiq j 显然该路径长度小于iipiq j，与iipiq j是顶点i到顶点j的最短路径相矛盾. 所以，原问题满足最优性原理。,2022/11/13,9,方法概述: 设计技巧,动态规划的设计技巧：阶段的划分和状态的表示；在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。,2022/1
7、1/13,10,方法概述: 存在的问题,空间溢出的问题，是动态规划解决问题时一个普遍遇到的问题； 动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。,2022/11/13,11,例1：多段图的最短路问题,多段图：设G=是一个有向连通图，其中|V|=n, |E|=m, V有划分V1,V2,Vk，这里V1 =s,s称为源点， Vk =t,t称为终点，其中k 2 。对于每条有向边 E都存在Vi V，使得u Vi和v Vi+1, 其中
8、1i均附有代价C(u,v)，则称G是一个k段图。,2022/11/13,12,2022/11/13,13,最短路：从源点s到终点t的整条路上的代价之和为最小。,每个子集Vi构成图中的一段。由于E的约束，每条从s到t的路径都是从第一段开始，然后顺次经过第2段，第3段，最后在第k段终止。对于每条从s到t的路径，可以把它看成在k-2个阶段中做出的某个决策序列的相应结果。,2022/11/13,14,假设s,v2,v3,vk-1,t是一条从s到t的最短路径，还假定从源点s（初始状态）开始，已做出了到结点v2的决策（初始决策），因此v2就是初始决策所产生的状态。如果把v2看成是原问题的一个子问题的初始状
9、态，解这个子问题就是找出一条由v2到t的最短路径。这条路径显然是 v2,v3,vk-1,t，否则设v2,q3,qk-1,t是一条由v2到t的更短路径，则s,v2,q3,qk-1,t是一条比路径s,v2,v3,vk-1,t 更短的由s到t的路径，与假设矛盾，故最优化原理成立。,2022/11/13,15,cost(i,j)=minC(j,r)+cost(i+1,r) rVi+1 E,向前处理法：设P(i,j)是从Vi中的点j到t的一条最短路，cost(i,j)是这条路线的耗费。由后向前推算，得到,2022/11/13,16,cost(4,9)=4,cost(i,j)=minC(j,r)+cost
10、(i+1,r),cost(4,10) =2 cost(4,11)=5,cost(3,6)=,min6+cost(4,9),5+cost(4,10),=min6+4,5+2=7,从第3段的顶点6到t的最短路径是6-10-t,5+2,2022/11/13,17,cost(3,7)=,min4+cost(4,9),3+cost(4,10) =min4+4,3+2=5,从第3段的顶点7到t的最短路径是7-10-t,cost(3,8)=7从第3段的顶点8到t的最短路径是8-10-t,2022/11/13,18,cost(2,2)=7 从第2段顶点2到t的最短路是2-7-10-tcost(2,3)=9从第
11、2段顶点3到t的最短路是3-6-10-tcost(2,4)=18从第2段顶点4到t的最短路是4-8-10-tcost(2,5)=15从第2段顶点5到t的最短路是5-8-10-tcost(1,1)=16 从第1段顶点1到t的最短路径由两条： 1-2-7-10-t和1-3-6-10-t,2022/11/13,19,从s到t的一条最短路径的代价为16。,用D(i,j)表示使C(j,r)+cost(i+1,r)取得最小值的r，则在上述求解过程中同时得到：,D(3,6)=10, D(3,7)=10, D(3,8)=10D(2,2)=7, D(2,3)=6, D(2,4)=8D(2,5)=8, D(1,1
12、)=2,设从s到t的最短路径为s,w2,w3,wk-1,t,则有w2=D(1,1)=2,w3=,D(2,D(1,1)=D(2,2)=7,w4=D(3,D(2,D(1,1)=D(3,D(2,2)=D(3,7)=10,所以这条路径是1-2-7-10-t,所以这条路径是1-2-7-10-t,2022/11/13,20,为了便于描述算法，对一个k段图的顶点，按段的顺序给它的每个顶点编号。设图中有n个顶点，则编号为1，2，n。首先，给s编为1号；然后给V2中的各个顶点分别编为2，3， ，| V2 |+1号；以此类推，最后t编号为n。,这样编号使Vi+1中的任何顶点的编号大于Vi中所有顶点的编号。,于是，
13、可以按n-1,n-2,1的顺序计算出cost(i,j)和D(i,j)。算法中可以利用顺序编号的特点，而不再考虑顶点所在的段。,2022/11/13,21,设顶点的编号已知，边已知及边的代价函数C(i,j)已知。用costi表示顶点i到t的最小代价， 1i n。用Di表示从顶点i到t的最短路径上顶点i的后继顶点号，用Pi表示最短路径经过第i级的顶点号， 1i k,2022/11/13,22,求两点间最短路径的算法：,Procedure Fgraph1. for i 1 to n costi 0；2. for j =n-1 step 1 to 1 do 3. 找顶点r,使 E,且C(j,r)+co
14、str最小；4. costjC(j,r)+costr;5. Dj r ; 6. P1 1 ; Pk n;7. for j=2 to k-1 do Pj DPj-1 ,O(n+|E|),2022/11/13,23,（从前）向后：设BPij是从源点s到Vi中顶点j的最小成本路径，bcost(i,j)是这条路径的代价,2022/11/13,24,格路问题：求从起点O(0,0)到终点E(m,n)的最短路。则分别用穷举法和动态规划法的加法次数和比较次数各是多少？,2022/11/13,25,2022/11/13,26,mn个点,2022/11/13,27,例2：货郎担问题,2022/11/13,28,不
15、失一般性，考虑以结点1为起点和终点的一条哈密顿回路。每一条这样的路线都由一条边和一条由结点k到结点1的路径组成，其中kV-1,而这条由结点k到结点1的路径通过V-1，k的每个结点各一次。如果这条周游路线是最优的，则这条由结点k到结点1的路径必定是通过V-1，k的每个结点各一次的由k到1的最短路径。,2022/11/13,29,设T( i,S)是由结点 i出发，经过结点集S中每个结点各一次并回到初始结点1的一条最短路径长度，则T(1,V-1)就是一条最优的周游路线长度。动态规划模型：,2022/11/13,30,T(1, 2,3,4)=mind12+T(2,3,4) , d13+T(3,2,4)
16、 , d14+T(4,2,3) ,T(2,3,4) =min,d23+T(3,4) ,d24+T(4,3),T(3,4) = d34+,T(4,),T(4,)=,d41,2022/11/13,31,T(1,2,3,4),T(2,3,4),T(3,2,4),T(4,2,3),T(3,4),T(4,3),T(2,4),T(4,2),T(2,3),T(3,2),T(4,),T(3,),T(4,),T(2,),T(3,),T(4,),2022/11/13,32,2022/11/13,33,1,(n-1),C(n-2,n-2),(n-1),C(n-2,n-3),第k层,(n-1) C(n-2,n-k-1
17、),n-1,一共 层,2022/11/13,34,第k层 (n-1) C(n-2,n-k-1) ；一共n-1层,= 1+ (n-1) C(n-2, ),k0,n-2,k-1,k,2n=1+C(n,1)+ C(n,2)+ C(n,n),=1+(n-1)2n-2,空间复杂性,O(n2n),2022/11/13,35,矩阵链乘法,问题描述加括号的方案数 动态规划法,2022/11/13,36,矩阵链乘法: 问题描述,给定n个矩阵A1,A2, An，Ai的维数为pi-1pi(1in),要求计算连乘积A1A2 An,由于矩阵乘法满足结合率，所以可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确
18、定。,比如： A1,A2,A3,A4 (A1 ( A2 ( A3 (A4) ) ) (A1 ( A2 A3 ) A4 ) ) (A1 A2 )( A3 A4 ) ( A1 ( A2 A3) ) A4 ) ( A1 A2 ) A3) A4 ),2022/11/13,37,不同的计算次序有不同的计算量注：1.设Apq,Aqr两矩阵相乘，普通乘法的次数为pqr,2.加括号对乘法次数的影响 如：A10100B1005C550 (AB)C): 101005+10550=7500次 (A(BC): 100550+1010050=75000次,2022/11/13,38,穷举法： 将n个矩阵从第k和第k+1
19、处隔开，对二个子序列再分别加括号，则可以得到下面递归式：,因此，穷举法不是一个有效算法,2022/11/13,39,计算m14过程如下：,自顶向下递归求解最优解的值,如A3:4被计算了2次，保存下来可以节省许多时间,2022/11/13,40,matrixChain(int p, int m, int s) int n=p.length-1; 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*
20、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; ,2022/11/13,41,矩阵链乘法:动态规划算法,自底向上记忆化方式求解mij - 计算方向： j m11, m12, m13, , m1n m22, m23, , m2n i mn-1n-1, mn-1n mnn,2022/11/13,42,矩阵链乘法:动态规划算法（续）,计算示例：,行 x 列A130 x35A235x15A315x5A4 5x10A510 x20A620 x
21、25,2022/11/13,43,矩阵链乘法:动态规划算法（续）,计算示例：,行 x 列A130 x35A235x15A315x5A4 5x10A510 x20A620 x25,traceback (int i,int j)if (i=j) return;traceback(i,sij);traceback(sij+1,j);print(“A”,i,”*A”,sij);print(“and A”,sij+1,”*A”,j);,2022/11/13,44,1.矩阵链乘问题满足最优性原理 记Ai:j为AiAi+1Aj链乘的一个最优括号方案，设Ai:j的最优次序中含有二个子链Ai:k和Ak+1:n，
22、则Ai:k和Ak+1:n也是最优的。（反证可得）,2.矩阵链乘的子问题空间：Ai:j, 1ijn A1:1, A1:2, A1,:3, , A1:n A2:2, A2:3, , A2:n An-1:n-1, An-1,n An,n,2022/11/13,45,递归求解最优解的值 记mij为计算Ai:j的最少乘法数，则原问题的最优值为 m1n,(AiAi+1Ak)pi-1pk(Ak+1Ak+2Aj)pkpj,2022/11/13,46,依据递归式自底向上计算。在计算过程中，保存已经解决的子问题答案。,A1,A2,A3,A4,A5,A6,m25 = min m22+m35+p1p2p5 m23+m
23、45+p1p3p5 m24+m55+p1p4p5,2022/11/13,47,A1=(aij)35 40 A2=(aij)40 20 A3 =(aij)20 10 A4=(aij)10 15,m13 = min,m12 =,m23 =40 20 108000m34 =20 10 153000,35 40 2028000,m11+m23+ 35 4010 ,m12+m33+ 35 2010 ,m24,m14,j= 1 2 3 4,i=1 2 3 4,2022/11/13,48,最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列
24、i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,2022/11/13,49,最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且z
25、kxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,2022/11/13,50,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：,2022/11/13,51,Algor
26、ithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i =cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;15: 16: return cmn; 17:,2022/11/13,52,0-1背包问题:问题描述及举例,问题描述举例：w=(w1,w2,w3)=(2,3,4), v=(v1,v2,v3)=(1,2,5), n=3, c=6, 求Knap(1,3,6) 取x=(1,0,1)时，,2022/1
27、1/13,53,0-1背包问题满足最优性原理证明：设(y1,y2,yn)是Knap(1,n,c)的一个最优解，则(y2,yn)是Knap(2,n,c-w1y1)子问题的一个最优解。若不然，设(z2,zn)是Knap(2,n,c-w1y1)的最优解，因此有,说明(y1,z2,zn)是Knap(1,n,c)的一个更优解，矛盾。,2022/11/13,54,0-1背包问题: 递归关系,考虑子问题： Knap(i, n, j) jc (假设c, wi取整数) 设其最优值为m(i, j), 即m(i, j)是背包容量为j, 可选物品为i,i+1,n的0-1背包问题的最优值。,子问题的背包容量在变化,20
28、22/11/13,55,0-1背包问题: 递归关系,递归式如下：,不取物品i,取物品i,2022/11/13,56,0-1背包问题: 算法,void Knapsack(int v, int w, int c, int n, int m)/输出m1c int jMax=min(wn-1, c); /因为jc, 只要计算到m1c即可 for(int j=0; j1; i-) /i1表示对i=1不处理，因为i=1时只需求m1c jMax=min(wi-1, c); for(int j=0; j=w1) m1c=max(m2c, m2c-w1+v1); else m1c=m2c; ,2022/11/1
29、3,57,0-1背包问题: 算法（续）,void Traceback(int w, int c, int n, int m, int x)/输出解x1.n for(int i=0; in; i+) if(mic=mi+1c) xi=0; else xi=1; c -= wi; xn=(mnc)?1:0;运行时间：T(n)=O(cn),2022/11/13,58,0-1背包问题,0 0 0 00 pi1(j wi) pi1(j)0 pi(j)0 目标,0,i 1,i,n,0 j wi j M,2022/11/13,59,0-1背包: 动态规划法适用范围,M=20000;重量分别为9603.61,
30、 3712.78, 2821.29,7970.46, 4728.1,2022/11/13,60,货物储运问题,在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。5,3,4,1,3,2,3,4,2022/11/13,61,货物储运问题,在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。 给
31、定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。5,3,4,1,3,2,3,4,设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，,2022/11/13,62,最大子段和: 问题描述,给定整数序列a1,a2,an，求形如 的子段和的最大值。规定子段和为负整数时，定义其最大子段和为0，即例如，(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2) 最大子段和为,2022/11/13,63,最大子段和: 动态规划算法,基本思想 子问题定义 考虑所有下标以j结束的最大子段和bj，即 原问题与子问题的关系 子问题解的递
32、归关系,2022/11/13,64,最大子段和: 动态规划算法（续）,算法int MaxSubSum3(int n, int a) int sum=0, b=0; /sum存储当前最大的bj, b存储bj for(int j=1; jsum) sum=b; return sum; 运行时间：T(n)=O(n),2022/11/13,65,漂亮打印问题,问题描述问题满足最优性原理递归关系推导 算法时间分析,2022/11/13,66,漂亮打印问题: 问题描述,n个英文单词的一篇文章，每个单词长度为li (i=1,.,n)，每行最多排M个字符。排版时，行首不为空，单词之间留一个空，不允许单词打破。
33、则 表示单词i到单词j排在一行时行尾的多余空格数。要求每行多余空格的立方和最小作为”漂亮”标准（文章的最后一行空格除外），如何排版？,2022/11/13,67,漂亮打印问题: 最优性原理,设最优排版方案中，第1行有单词1k，单词k+1n排在第2行以后，显然单词K+1n的排版子问题也是一个最优排版。 因此，原问题满足最优性原理。,2022/11/13,68,漂亮打印问题: 递归关系推导,2022/11/13,69,漂亮打印问题: 算法和时间分析,void PerfectPrinting(int l, int c, int p, int n)/l为n个单词的长度；ci为1i单词排版的最优值；p保存换行信息, 最后/一行从单词pn+1开始打印，倒数第2行从单词ppn+1开始打印 c0=0; for(int j=1; j=0 ) if( j=n ) lc0； /lc是当前行的成本 else lc=extras3; if( cjci-1+ lc ) cj=ci-1+ lc; /保存当前最优 pj=i-1; /保存上一行最后文字的序号 i-; extras -= (lj+1); /当前行加入单词i, i=j-1,j-2,1 T(n)=O(nM) S(n)=O(n) ,
