算法设计-动态规划ppt课件.ppt

《算法设计-动态规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法设计-动态规划ppt课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划法 方法概述:发展及研究内容n 动态规划(dynamic programming)是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。n 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、资源分配、设备更新等问题，用动态规划比用其它方法求解更为方便。6/6/2023 2

2、方法概述:发展及研究内容n 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。6/6/2023 3方法概述:基本思想 n 动态规划的思想实质是分治思想和解决冗余。n 与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。n 与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。n 如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免

3、重复计算、节省时间。动态规划法用一个表来记录所有已解的子问题的答案。n 这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。6/6/2023 4方法概述:求解步骤 1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；4、根据计算最优值时记录的信息，构造最优解。注：步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息是构造最优解的基础6/6/2023 5方法概述:适用条件 动态规划法的有效性依赖于问题本身所具有的两

4、个重要性质n 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。n 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。6/6/2023 6方法概述:最优性原理及举例 n Bellman给出这个原理作为动态规划的适用条件，后来Morin在1982年证明了这只是一个充分条件而非必要条件。Bellman的原定义如下：n An optimal policy has the property t

5、hat 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.n 最优性原理又称为最优子结构性质：n 如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。即一个最优策略的子策略总是最优的。6/6/2023 7方法概述:最优性原理及举例（续）n 例1：设G是一个有向加权图，则G从顶点i到顶点j之间的最短路

6、径具有最优子结构性质。n 证明：（反证）n 设iipiq j是一条最短路径，但其中子路径ipiq j不是最优的，假设最优的路径为ipiq jn 则我们重新构造一条路径：iipiq jn 显然该路径长度小于iipiq j，与iipiq j是顶点i到顶点j的最短路径相矛盾.n 所以，原问题满足最优性原理。n 6/6/2023 8方法概述:设计技巧n 动态规划的设计技巧：阶段的划分和状态的表示；n 在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。6/6/2023 9方法概述:存在的问题 n

7、空间溢出的问题，是动态规划解决问题时一个普遍遇到的问题；n 动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。6/6/2023 10l例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,其中1ik且每条边均附有代价C(u,v)，则称G是一个k段图。6

8、/6/2023 11123456789101112s97324212711118654356425V1V2V3V4V5t6/6/2023 12l最短路：从源点s到终点t的整条路上的代价之和为最小。每个子集Vi构成图中的一段。由于E的约束，每条从s到t的路径都是从第一段开始，然后顺次经过第2段，第3段，最后在第k段终止。对于每条从s到t的路径，可以把它看成在k-2个阶段中做出的某个决策序列的相应结果。6/6/2023 13l假设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的路径，与假设矛盾，故最优化原理成立。6/6/2023 14cost(i,j)=minC(j,r)+cost(i+1,r)r Vi+1 Ej rtViVi+1最短最短向前处理法：设P(i,j)是从Vi中的点j到t的一条最短路，cost(i,j)是这条路线的耗费。由后向前推算，得到6/6/2023 15123456789101112s

10、97324212711118654356425V1V2V3V4V5tcost(4,9)=4cost(i,j)=minC(j,r)+cost(i+1,r)cost(4,10)=2 cost(4,11)=5cost(3,6)=min6+cost(4,9),5+cost(4,10)=min6+4,5+2=7从第3段的顶点6到t的最短路径是6-10-t5+26/6/2023 16123456789101112s97324212711118654356425V1V2V3V4V5tcost(3,7)=min4+cost(4,9),3+cost(4,10)=min4+4,3+2=5从第3段的顶点7到t的最短

11、路径是7-10-t cost(3,8)=7从第3段的顶点8到t的最短路径是8-10-t6/6/2023 17123456789101112s97324212711118654356425V1V2V3V4V5tcost(2,2)=7 从第2段顶点2到t的最短路是2-7-10-tcost(2,3)=9从第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 6/6/2023

12、 18从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)=2设从s到t的最短路径为s,w2,w3,wk-1,t则有w2=D(1,1)=2w3=D(2,D(1,1)=D(2,2)=7w4=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-t6/6/2023 19为了便于描述算法，对一个k段

13、图的顶点，按段的顺序给它的每个顶点编号。设图中有n个顶点，则编号为1，2，n。首先，给s编为1号；然后给V2中的各个顶点分别编为2，3，|V2|+1号；以此类推，最后t编号为n。这样编号使Vi+1中的任何顶点的编号大于Vi中所有顶点的编号。于是，可以按n-1,n-2,1的顺序计算出cost(i,j)和D(i,j)。算法中可以利用顺序编号的特点，而不再考虑顶点所在的段。6/6/2023 20设顶点的编号已知，边已知及边的代价函数C(i,j)已知。用costi表示顶点i到t的最小代价，1i n。用Di表示从顶点i到t的最短路径上顶点i的后继顶点号，用Pi表示最短路径经过第i级的顶点号，1i k6/

14、6/2023 21求两点间最短路径的算法：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)+costr最小；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|)6/6/2023 22123456789101112s97324212711118654356425V1V2V3V4V5t（从前）向后：设BPij是从源点s到Vi中顶点j的最小成本路径，bcost(i,j)是这条路径的代

15、价bcost(i,j)=minbcost(i-1,r)+C(r,j)r Vi-1 E6/6/2023 23l格路问题：求从起点O(0,0)到终点E(m,n)的最短路。则分别用穷举法和动态规划法的加法次数和比较次数各是多少？E(m,n)O(0,0)xy6/6/2023 24E(m,n)O(0,0)xy6/6/2023 25E(m,n)O(0,0)xymn个点 6/6/2023 26l例2：货郎担问题1 24 3105209128 9 13156810 10 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v46/6/2023 27不失一般性，考虑以结点1为起点

16、和终点的一条哈密顿回路。每一条这样的路线都由一条边和一条由结点k到结点1的路径组成，其中k V-1,而这条由结点k到结点1的路径通过V-1，k的每个结点各一次。如果这条周游路线是最优的，则这条由结点k到结点1的路径必定是通过V-1，k的每个结点各一次的由k到1的最短路径。6/6/2023 28l设T(i,S)是由结点 i出发，经过结点集S中每个结点各一次并回到初始结点1的一条最短路径长度，则T(1,V-1)就是一条最优的周游路线长度。动态规划模型：T(1,V-1)=mind1k+T(k,V-1,k)2 k n T(i,s)=mindij+T(j,S-j)j S,i S6/6/2023 29 1

17、0 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v4T(1,2,3,4)=mind12+T(2,3,4),d13+T(3,2,4),d14+T(4,2,3)T(2,3,4)=mind23+T(3,4),d24+T(4,3)T(3,4)=d34+T(4,)T(4,)=d416/6/2023 30T(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,)6/6/2023 31T(1,2,3,4,5)T(2,3,4,5)

18、T(3,2,4,5)T(3,4,5)T(4,5)T(5,4)T(2,4,5)T(5,4)T(4,5)6/6/2023 32T(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,)1(n-1)C(n-2,n-2)(n-1)C(n-2,n-3)第k层(n-1)C(n-2,n-k-1)n-1一共 层6/6/2023 33第k层(n-1)C(n-2,n-k-1)；一共n-1层1+(n-1)C(n-2,n-k-1)k1n-1k1=1+(n-1)C(n-2,)n-

19、1=1+(n-1)C(n-2,)k0n-2k-1k2n=1+C(n,1)+C(n,2)+C(n,n)=C(n,k)k0n=1+(n-1)2n-2空间复杂性O(n2n)6/6/2023 34矩阵链乘法n 问题描述n 加括号的方案数 n 动态规划法 6/6/2023 35矩阵链乘法:问题描述给定n 个矩阵A1,A2,An，Ai的维数为pi-1pi(1 in),要求计算连乘积A1A2 An由于矩阵乘法满足结合率，所以可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。比如：A1,A2,A3,A4(A1(A2(A3(A4)(A1(A2 A3)A4)(A1 A2)(A3 A4)(A1(A2

20、A3)A4)(A1 A2)A3)A4)6/6/2023 36不同的计算次序有不同的计算量注：1.设Apq,Aqr两矩阵相乘，普通乘法的次数为pqr2.加括号对乘法次数的影响 如：A10100B1005C550(AB)C):101005+10550=7500 次(A(BC):100550+1010050=75000 次6/6/2023 37穷举法：将n 个矩阵从第k 和第k+1 处隔开，对二个子序列再分别加括号，则可以得到下面递归式：因此，穷举法不是一个有效算法6/6/2023 38计算m14 过程如下：自顶向下递归求解最优解的值如A3:4 被计算了2 次，保存下来可以节省许多时间6/6/202

21、3 39matrixChain(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*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;6/6/2023 40矩阵链乘法:动态规划算法 n 自底向上记忆化方式求解mij-计算方向：j m11,m12,m13,m1n m22,m23,m2

22、n i mn-1n-1,mn-1n mnn 6/6/2023 41矩阵链乘法:动态规划算法（续）n 计算示例：行 x 列A1 30 x35A2 35x15A3 15x5A4 5x10A5 10 x20A6 20 x2565 55 4 43 3 3 3 i3 3 3 2 23 3 3 1 1 16 5 4 3 2 1sj6543 i21 6 5 4 3 2 1 mj000000 1512550003500 10005375 2500 75010500 7125 4375 262511875 9375 7875 157506/6/2023 42矩阵链乘法:动态规划算法（续）n 计算示例：行 x 列

23、A1 30 x35A2 35x15A3 15x5A4 5x10A5 10 x20A6 20 x2565 55 4 43 3 3 3 i3 3 3 2 23 3 3 1 1 16 5 4 3 2 1sjResult(A1(A2A3)(A4A5)A6)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);6/6/2023 431.矩阵链乘问题满足最优性原理 记Ai:j 为AiAi+1Aj链乘的一个最优括号方案，

24、设Ai:j 的最优次序中含有二个子链Ai:k 和Ak+1:n，则Ai:k 和Ak+1:n 也是最优的。（反证可得）2.矩阵链乘的子问题空间：Ai:j,1 i j n A1:1,A1:2,A1,:3,A1:n A2:2,A2:3,A2:n An-1:n-1,An-1,n An,n 6/6/2023 44l 递归求解最优解的值 记mij 为计算Ai:j 的最少乘法数，则原问题的最优值为 m1n(AiAi+1Ak)pi-1pk(Ak+1Ak+2Aj)pkpj6/6/2023 45依据递归式自底向上计算。在计算过程中，保存已经解决的子问题答案。A1,A2,A3,A4,A5,A6m25=min m22+

25、m35+p1p2p5 m23+m45+p1p3p5 m24+m55+p1p4p56/6/2023 46A1=(aij)35 40 A2=(aij)40 20 A3=(aij)20 10 A4=(aij)10 15m13=min m12=m23=40 20 108000m34=20 10 15300035 40 2028000m11+m23+35 4010,m12+m33+35 2010 m24m14m11m12m13m14m22m23m24m33m34m44 j=1 2 3 4i=1 2 3 46/6/2023 47最长公共子序列 若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk

26、，是X的子序列是指存在一个严格递增下标序列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的最长公共子序列。6/6/2023 48最长公共子序列的结构设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公

27、共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。6/6/2023 49子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：6/6/2023 50A

28、lgorithm lcsLength(x,y,b)1:m x.length-1;2:n y.length-1;3:ci0=0;c0i=0;4:for(int i=1;i=m;i+)5:for(int j=1;j=cij-1)10:cij=ci-1j;11:bij=2;12:else 13:cij=cij-1;14:bij=3;15:16:return cmn;17:6/6/2023 510-1 背包问题:问题描述及举例 n 问题描述n 举例：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)时，6/6

29、/2023 52n 0-1背包问题满足最优性原理n 证明：设(y1,y2,yn)是Knap(1,n,c)的一个最优解，则n(y2,yn)是Knap(2,n,c-w1y1)子问题的一个最优解。n 若不然，设(z2,zn)是Knap(2,n,c-w1y1)的最优解，因此有说明(y1,z2,zn)是Knap(1,n,c)的一个更优解，矛盾。6/6/2023 530-1 背包问题:递归关系 n 考虑子问题：Knap(i,n,j)j c(假设c,wi取整数)设其最优值为m(i,j),即m(i,j)是背包容量为j,可选物品为i,i+1,n的0-1背包问题的最优值。子问题的背包容量在变化6/6/2023 5

30、40-1 背包问题:递归关系 n 递归式如下：不取物品i取物品i6/6/2023 550-1 背包问题:算法 void Knapsack(int v,int w,int c,int n,int m)/输出m1c int jMax=min(wn-1,c);/因为j c,只要计算到m1c即可 for(int j=0;j=jMax;j+)mnj=0;/0 jwn,(4)式 for(int j=wn;j1;i-)/i1表示对i=1不处理，因为i=1时只需求m1c jMax=min(wi-1,c);for(int j=0;j=jMax;j+)/0 jwi,(2)式 mij=mi+1j;for(int j

31、=wi;j=w1)m1c=max(m2c,m2c-w1+v1);else m1c=m2c;6/6/2023 560-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;n 运行时间：T(n)=O(cn)6/6/2023 570-1 背包问题0 0 0 00 pi1(j wi)pi1(j)0 pi(j)0 目标 0i 1i n 0 j wi j M6/6/2023 580-1 背包:动态规

32、划法适用范围M=20000;重量分别为9603.61,3712.78,2821.29,7970.46,4728.16/6/2023 59货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。5,3,4,1,3,2,3,46/6/2023 60货物储运问题在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的

33、一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。5,3,4,1,3,2,3,4设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，6/6/2023 61最大子段和:问题描述n 给定整数序列a1,a2,an，求形如 的子段和的最大值。规定子段和为负整数时，定义其最大子段和为0，即n 例如，(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)最大子段和为6/6/2023 62最大子段和:动态规划算法n 基本思想 子问题定义 考虑所有下标以j结束的最大子段和bj，即 原问题与子问题的关系 子问

34、题解的递归关系6/6/2023 63最大子段和:动态规划算法（续）n 算法int MaxSubSum3(int n,int a)int sum=0,b=0;/sum存储当前最大的bj,b存储bj for(int j=1;j=n;j+)b+=aj;if(bsum)sum=b;return sum;n 运行时间：T(n)=O(n)6/6/2023 64漂亮打印问题n 问题描述n 问题满足最优性原理n 递归关系推导 n 算法n 时间分析6/6/2023 65漂亮打印问题:问题描述 n个英文单词的一篇文章，每个单词长度为li(i=1,.,n)，每行最多排M个字符。排版时，行首不为空，单词之间留一个空，

35、不允许单词打破。则 表示单词i到单词j排在一行时行尾的多余空格数。要求每行多余空格的立方和最小作为”漂亮”标准（文章的最后一行空格除外），如何排版？6/6/2023 66漂亮打印问题:最优性原理 设最优排版方案中，第1行有单词1k，单词k+1n排在第2行以后，显然单词K+1n的排版子问题也是一个最优排版。因此，原问题满足最优性原理。6/6/2023 67漂亮打印问题:递归关系推导6/6/2023 68漂亮打印问题:算法和时间分析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)6/6/2023 69