第3章 动态规划(part1)

,第,3,章 动态规划,Part 1,上海大学计算机学院,沈云付,学习要点,理解动态规划算法的概念与基本思想。,掌握动态规划算法的两个基本要素,（,1,）最优子结构性质 （,2,）重叠子问题性质,掌握设计动态规划算法方法,求解步骤,-4,步,自上而下自下而上求解方式；备忘录（打表）的应用,动态规划典型问题,矩阵连乘、最长公共子序列、,0-1,背包问题、最大子段和、流水作业调度（,Johnson,调度法则）,等等,引言,几个典型问题,问题,1,：最短路径,有一个棋盘形街道，某人从西南角,O,走到东北角,U,，想选择一条路线使所走的路径最短，如何走法？,O,B,A,C,D,E,F,G,H,I,N,K,L,M,P,Q,R,S,T,U,1 3 2 3,2 2 1 4,2 3 4 5,2 3 1 2,2 1 2 2 3,3 4 1 2 3,2 2 1 3 4,总路径数,=C =35,3,7,问题,2,：最短路径,对有向无环图，,求从,s,到,t,的一条最短路径,2,3,4,5,6,7,8,9,10,11,1,12,s,t,9,7,3,2,4,2,5,6,5,3,4,5,6,8,11,11,7,2,1,2,4,问题,3,：背包问题,有一旅行者要从,n,种物品中选取体积不超过,C,的行李随身携带，要求包装得最满。,例：设有,n=8,个体积分别为,54,，,45,，,43,，,29,，,23,，,21,，,14,，,1,的物体和一个容积为,C=110,的背包，问选择哪几个物体装入背包可以使其装的最满。,问题,4,：文本相似度问题,给定两篇文章（或代码）的文本,x=,和,y=,两者公共部分的最长长度是多少？,3.1,矩阵连乘问题,3.1,矩阵连乘问题,给定,n,个矩阵,A,1,，,A,2,，,，,A,n,，其中，,A,i,与,A,j+1,是可乘的，,i=1,，,2,，,，,n-l,，现要计算出这,n,个矩阵的连乘积,A,1,A,2,A,n,。,矩阵连乘问题：,确定一种运算次序，使总的运算次数达到最少。,一、问题叙述,矩阵乘法,A=(a,ij,),m,k,，,B=(b,ij,),k,n,，,C=(c,ij,),m,n,计算,C,：每个元素需,k,次乘法，,k-1,次加法,C,有,mn,个元素：计算,C,，需,mnk,次乘法，,mn(k-1),次加法,举例：设,A,1,，,A,2,，,A,3,，分别为,10,100,，,100,5,，,5,50,的矩阵，求连乘积,A,1,A,2,A,3,时需多少次乘法运算？,矩阵连乘方法数与添括号方式数一一对应,完全加括号的矩阵连乘积可递归地定义为：,（,1,）单个矩阵是完全加括号的；,（,2,）若,矩阵连乘积,A,是完全加括号的，则,A,可表示为,2,个完全加括号的矩阵连乘积,B,和,C,的乘积并加括号，即,A=(BC),矩阵连乘积与加括号,设有四个矩阵,A,B,C,D,，它们的维数分别是：,16000, 10500, 36000, 87500, 34500,总共有五种完全加括号的方式,乘法运算数,二、算法分析,-,穷举法行吗？,列举所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数,所有可能的计算次序有多少？,设矩阵序列的加括号方式为,P(n),，可得：,p(k)p(n-k),k=1,n-1,( n 1 ),1 ( n = 1),P(n) =,P(n),是,Catalan,数,P(N)=,(,4,n,/n,3/2,),二、算法分析,-,新思路,采用一个新方法,（,1,）分析最优解的结构,记,Ai,：,j,为,A,i,A,i+1,A,j,，记,mij,是计算,A,i,A,i+1,A,j,时的最少乘法次数,显然，,Ai,：,i=A,i,，,mii=0,问题变为：计算,A1,：,n,、求,m1n,二、算法分析,-,新思路,（,2,）建立递归关系,m1n= m1k+ mk+1n+ p,0,p,k,p,n,一般情况,假定计算,Ai,：,j,的一个最优次序在矩阵,A,k,和,A,k+1,之间将矩阵链断开，,i k j,mij= mik+ mk+1j+ p,i-1,p,k,p,j,假定计算,A1,：,n,的一个最优次序在矩阵,A,k,和,A,k+1,之间将矩阵链断开，,1 k n,分析最优解的特征和结构,特征：计算,Ai:j,的最优次序所包含的计算矩阵子链,Ai:k,和,Ak+1:j,的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用这一算法求解的显著特征。,矩阵链问题的一般递推关系,mij=,0 i=j,minmik+ mk+1j+ p,i-1,p,k,p,j,i,j,i=kj,（,3,）计算最优值,1,、简单递归,2,、,动态规划的求解方法,按自底向上方式求解,对于,1ijn,不同的有序对,(i,j),对应于不同的子问题。因此，不同子问题的个数最多只有,minmik+ mk+1j+ p,i-1,p,k,p,j,i,j,i=kj,mij=,计算最优值程序,void MatrixChain(int *p, int n, int *m),int i,r,j,k,t;,for (i = 1; i = n; i+) mii = 0;,for (r = 2; r = n; r+ ),for (i = 1; i = n - r+ l; i+) ,j = i + r - 1;,mij = mi+1j + pi - 1*pi* pj;,for (k = i+1; k j; k+),t = mik + mk + 1j+ pi 1* pk * pj;,if (t mij),mij = t;,算法过程,A1,A2,A3,A4,A5,A6,30,35,35,15,15,5,5,10,10,20,20,25,算法复杂度分析,算法,matrixChain,的主要计算量取决于算法中对,r,，,i,和,k,的,3,重循环。循环体内的计算量为,O(1),，而,3,重循环的总次数为,O(n,3,),。因此算法的计算时间上界为,O(n,3,),。算法所占用的空间显然为,O(n,2,),。,（,4,）算法分析,-,构造最优解,void Traceback(int i, int j, int *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,引入分割点标记,sij,，确定加括号方式，构造最优解,3.2,动态规划算法的基本要素,动态规划的基本思想,算法目标：求解具有某种最优性质的问题。它可能有许多可行解，希望找到具有最优值的解。,算法思想：,动态规划算法将待求解问题分解成若干个子问题，先求解子问题，,从这些子问题的解得到原问题的解。这些子问题往往不互相独立。,分解时得到的子问题数目可能很多，有些子问题被重复计算了很多次。,求解方法,自底向上方式、自上而下方式,采用,备忘录方法,：求解过程中需保存已解决的子问题的解，而在需要时再找出已求得的解，就可避免大量的重复计算，节省时间。动态规划法用表记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。,动态规划中的概念、名词术语,(1),1.,阶段：,把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。,2.,状态：,某一阶段的出发位置称为状态。通常一个阶段包含若干状态。,3.,决策：,从某阶段的一个状态演变到下一个阶段某状态的选择。,特点：前一阶段的终点是后一阶段的起点，前一阶段的决策影响后一阶段的状态。,4.,策略：,由开始到终点的全过程中，由每段决策组成的决策序列。,动态规划中的概念、名词术语,(2),5.,状态转移方程：,描述由,k,阶段到,k+1,阶段状态的演变规律称为状态转移方程（用数学形式表达）。,6.,目标函数与最优化概念：,目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。,7.,动态规划：,在多阶段决策问题中，各阶段采取的决策依赖于目前状态，并引起状态的转移，以期求得最优化的过程,最佳原理,一个最优化策略的子策略总是最优的。,动态规划的求解步骤,1,、找出最优解的性质，并刻画其结构特征,2,、递归地定义最优值（写出动态规划方程）,3,、以自底向上（或自顶向下）的方式计算出最优值,4,、根据计算最优值时得到的信息，构造一个最优解,注意：,1,、步骤,1-3,：是动态规划算法的基本步骤。,2,、如只求最优值，步骤,4,可以省略；,3,、若需求出问题的一个最优解，则必须执行步骤,4,，步骤,3,中记录的信息必须足够多以便构造最优解。,动态规划的求解方法,按自底向上方式求解,是动态规划方法的一种,所有子问题计算一次，无需递归代价,效率较高,程序（,next page,）,void MatrixChain(int p, int n, int *m, int *s),for (int i = 1; i = n; i+) mii = 0;,for (int r = 2; r = n; r+ ),for (int i = 1; i = n - r+ l; 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 0),return mij;,if (i = j) return 0;,int u = lookupChain(i+1,j) +,pi-1*pi*pj; /,记初值,sij = i;,for (k = i+1; k j; k+),t= lookupChain(i,k),+ lookupChain(k+1,j),+ pi-1*pk*pj;,if (t u) ,u = t; sij = k;,mij = u;,return u;,动态规划小结,特征：最优子结构性质和子问题重叠性质。,最佳原理,动态规划法与分治法的联系与区别,动态规划法的使用方法,作业与上机题,1,、,分析题,3-1,，,实现题,3-4(,数字三角形,),2,、,(,补充,),设,A,、,B,、,C,、,D,、,E,、,F,分别为,50,10,、,103,、,312,、,125,、,550,、,506,的矩阵，找出计算矩阵乘积,ABCDEF,的最佳步骤，使乘法数最少。,3,、分析题,3-3,，实现题,3-2(,编辑距离,),，,3-6,（游船问题），,3-13(,最大,k,乘积,),，,实现,3-7(,汽车加油,),第四周上机：,修改,3.1,节的算法，找出计算,n,个矩阵之积的最少乘法数，并完成添括号过程。,（,http:/202.121.199.212,）,-1611,动态规划解题举例,1,1,、单侧跳马问题,给定,m*n,棋盘，求棋盘上一只马从左上角（,1,，,1,）到达右下角位置的最短路径长。,注意：在本问题中马只能向右侧、向下走“日”字形的，但马不能向所在位置的左边、向上走“日”字形。,输入,2,个整数,m,、,n,，（,1,m,，,n,19,）,),之间用一个空格隔开，表示棋盘大小。,输出,输出马从棋盘左上角跳到右下角所需的最短路径长，如果不能跳到，那么直接输出“,Impossible”,。,分析,设,f,(,i,j,),为从,(i,j),到,(,m,n,),的最短距离。从,(i,j,),开始可走,2,个位置,(,i,+1,j,+2),与,(,i,+2,j,+1),。,(m,n),(1,1),(i,j),初值：,动态规划解题举例,2,复制书稿,以前人们靠抄写员复制书籍。一次，有个剧院要排演一场戏剧,希望将剧本复制一份。已知剧本由,m,册组成，每册有,p,i,页,(1=i=m),。雇佣了,k,个抄写员,(1,k,m),每个抄写员只能被分配一个任务，即抄写连续的若干册书稿。假定每个抄写员的抄写速度一样。该任务完成所需的总时间由工作量最大的抄写员决定，即该抄写员要抄写的总书页数。,求一种分配方案，使得完成任务所需的总时间最少。,输入,整数,m,及,k,。接着输入,m,个整数,p,1,、,p,2,、,p,3,、,、,p,m,，之间用一个空格隔开。,输出,输出完成任务所需的最少总时间。,设,F,i,j,为前,i,个抄写员复制前,j,本书的最小完成时间数。考察第,i,人的抄写情况。设前面,t,本书由前,i,-1,人抄写，而从第,t,+1,，,t,+2,，,j,本书由第,i,人抄写，于是便有状态转移方程：,分析,初始时，,F,11=,p,1,。,又当,m,k,时，,其中，,1,i,k,，,i,j,m,。,3.3,最长公共子序列,概念,1,、子序列：,若给定序列,X=x,1,x,2,x,m,，则另一序列,Z=z,1,z,2,z,k,是,X,的子序列，是指存在一个严格递增下标序列,i,1,i,2,i,k,使得对于所有,j=1,2,k,有：,z,j,=x,i,j,。,例如，序列,Z=B,，,C,，,D,，,B,是序列,X=A,，,B,，,C,，,B,，,D,，,A,，,B,的子序列，相应的递增下标序列为,2,，,3,，,5,，,7,。,2,、公共子序列,给定,2,个序列,X,和,Y,，当另一序列,Z,既是,X,的子序列又是,Y,的子序列时，称,Z,是序列,X,和,Y,的公共子序列,最长公共子序问题,给定,2,个序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,，找出,X,和,Y,的最长公共子序列,Z,。,一、算法分析,用穷举法：,X,有,2,m,个子集，,m=|X|,， 逐一验证,X,的每个子集是否合要求，找出,Z,需指数时间,可否用,动态规划法,？,前提：问题是否具有,1,、最优子结构性质；,2,、子问题重叠性质？,最长公共子序列的结构,设序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,的最长公共子序列为,Z=z,1,z,2,z,k,，则,(1),若,x,m,=y,n,，则,z,k,=x,m,=y,n,，且,z,k-1,是,x,m-1,和,y,n-1,的最长公共子序列。,(2),若,x,m,y,n,且,z,k,x,m,，则,Z,是,x,m-1,和,Y,的最长公共子序列。,(3),若,x,m,y,n,且,z,k,y,n,，则,Z,是,X,和,y,n-1,的最长公共子序列。,结论,2,个序列的最长公共子序列包含了这,2,个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,二、子问题的递归结构,用,cij,记录序列,X,i,和,Y,j,的最长公共子序列的长度。,其中，,X,i,=x,1,x,2,x,i,；,Yj=y,1,y,2,y,j,。,当,i=0,或,j=0,时，空序列是,X,i,和,Y,j,的最长公共子序列。故此时,Cij=0,。,其他情况下，由最优子结构性质可建立递归关系如下：,为什么是这种形式？,三、计算最优值,子问题空间中，总共有,(mn),个不同的子问题，用动态规划算法自底向上计算最优值能提高算法的效率。,lcsLength(x,y,b),m=x.length-1; n=y.length-1;,ci0=0; c0i=0;,for (int i = 1; i = m; i+),for (int j = 1; j =cij-1), cij=ci-1j;,bij=1; /,指,else, cij=cij-1;,bij=; /,指,构造最长公共子序列,lcs,(int i,int j,char *x,int *b),if,(i =0 | j=0),return,;,if,(bij=,0,),lcs,(i-1,j-1,x,b);,printf,(xi);,else if,(bij=,1,),lcs,(i-1,j,x,b);,else lcs,(i,j-1,x,b);,求最长公共子序列问题的重叠子结构性质很明显,举例,设,X=A,B,C,B,D,A,B,和,Y=B,D,C,A,B,A,，找出,X,和,Y,的最长公共子序列,LCS(X,Y),。,先通过,LCSLength,，求,Cij,，,bij,再调用,LCS,，求得,LCS,（,X,，,Y,）,=B,，,C,，,B,，,A,算法的改进,在算法,lcsLength,和,lcs,中，可进一步将数组,b,省去。,void lcsPrint(i,j,x) ,if (i=0)|(j=0) return;,if (cij=ci-1j-1+1) ,lcsPrint(i-1,j-1,x) ; printf(xi);,else if (cijci-1j+1),lcsPrint(i-1,j,x);,else lcsPrint(i, j-1,x),如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算,cij,时，只用到数组,c,的第,i,行和第,i-1,行。因此，用,2,行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至,O(min(m,n),。,银币问题,补充,银币问题：,用天平秤银币，找出不合格的银币，且在最坏情况下秤银币的次数最少。,设有,n,个银币中有一个是不合格的，不合格的银币比合格银币要轻。,设,T,n,为最坏情况下秤,n,个银币的最少次数，需建立动态规划方程,补充：银币问题,-,续,n,块银币,C1,、,C2,、,C3,、,、,Cn,中有一块不合格，较重，用天平找出这块不合格的银币，问天平要称量多少次，如何称？,若从,n,中取出,2k,块，每边,k,块，在天平上称，设,T,n,为从,n,块中找出不合格银币的称量次数，显然，,T,n,是,n,的单调增（不是严格单调）函数。,3.4,最大子段和,心情愉快指数,问题描述：某人驾车旅行，一些道路使他心情很舒畅，如高速公路，但一些道路使他心情很沮丧，如乡村泥泞的道路。于是他对路过的这些给出心情愉快指数，并统计道路上若干路段的心情愉快指数之和，他想知道在道路上从哪个起点开始到哪个位置结束的路段上心情愉快指数最大。,您是计算机程序编程高手，请您帮助他解决这问题。,最大子段和问题,问题描述：给定由,n,个整数组成的序列,a,1, a,2, a,3, , a,n,求该序列形如,a,k,的子段和的最大值。,注：当,n,个整数均为负数时，规定其最大子段和为,0,。即，所求最大子段和为：,a,k,k=i,j,1, i j n,max, 0,max,举例,设（,a,1, a,2, a,3, a,4, a,5, a,6,）,=,（,-2,，,11,，,-4,，,13,，,-5,，,-2,），求该序列,的子段和的最大值。,算法分析,简单算法,改进算法,分治策略,动态规划,简单算法,-,枚举,int MaxSum(int n, int *a, int &besti, int &bestj), int sum = 0;,for (int i = 1;i = n;i + ),for (int j = i;j = n;j +),int thissum = 0;,for (int k = i;k sum) ,sum = thissum;,besti = i; bestj = j;,return sum;,返回,复杂性,O(n,3,),取,2,个位置,i,j,改进算法,递推,利用,=a,j,+,返回,a,k,k=i,j,a,k,k=i,j-1,int MaxSum(int n, int *a, int &besti, int &bestj), int sum = 0, thissum;,for (int i = 1;i = n;i + ),thissum = 0;,for (int j = i;j sum), sum = thissum; besti = i;bestj = j; ,return sum;,复杂性,O(n,2,),分治策略,将序列,a1:n,分为长度相等的两段,a1:n/2,和,an/2+1:n,，分别求出这两段的最大子段和,S,1,S,2,S,1,=max,1,i,j,n/2, ,S,2,=max,n/2+1,i,j,n, ,a,k,k=i,j,a,k,k=i,j,a1:n,的最大子段和,S,有三种可能：,S=S,1,，,S=S,2,或,S=,，,i,n/2,，,n/2+1,j,a,k,k=i,j,第三种情况的处理：,S=,返回,S,1,=max,1,i,n/2, ,S,2,=max,n/2+1,j,n, , a,k,k=i,n/2, a,k,k=n/2+1,j,确定,i,需,O(n),，确定,j,需,O(n),S=S,1,+S,2,a,k,k=i,j,时间复杂度递推式,2 T(n/2) + O(n) ( n C ),O(1) ( n,C),T(n) =,解上述递推式，得：,T( n ) = O(n log n),动态规划方法,思想：对,a1:j,，记,bj,，,1,j n,a,k,k=i,j,bj=max,1,i j, ,a1:n,的最大,子段,和,S= max,1,j n,max,1,i j,a,k,k=i,j,=max,1,j n,bj,而,bj=maxbj-1+aj,，,aj,bj-10,时,动态规划,-,程序,int MaxSum(int n, int *a),int s = 0, b = 0;,for (int i = 1;i 0) b += ai;,else b = ai;,if (b sum) sum = b;,return sum;,返回,复杂性,O(n),最大子段和的推广,2,维,-,最大子矩阵和问题的求解算法,1,维,-,最大,m,子段和问题的求解算法,最大子矩阵和问题,给定一个,m,行,n,列的整数矩阵,A,，试求矩阵,A,的一个子矩阵，使其各元素之和为最大。,0 -2 -7 0,2 -6 2,-4 1 -4 1,-1 8 0 -2,A=,算法,直接枚举：需,4,重循环，复杂性,O(m,2,n,2,),改进：记,S(i,1,i,2,j,1,j,2,)=, a,ij,i=i,1,j=j,1,i,2,j,2,要求,S= max,1,i,1,i,2, m,max,1,j,1,j,2, n,S(i,1,i,2,j,1,j,2,),=,max,1,i,1,i,2, m,t(i,1,i,2,),其中,t(i,1,i,2,)= max,1,j,1,j,2, n,S(i,1,i,2,j,1,j,2,),= max,1,j,1,j,2, n, b,j,j=j,1,j,2,b,j,是,j,列上从,i,1,行到,i,2,行的元素之和，显然,t(i,1,i,2,),是求,b1.n,的,最大子段和,a,11,a,12,a,13, a,1k ,a,1n,a,21,a,22,a,23, a,2k ,a,2n,.,a,i1,a,i2,a,i3, a,ik ,a,in,a,i+1,a,i+12,a,i+13, a,i+1k ,a,i+1n,a,i+21,a,i+22,a,i+23, a,i+2k ,a,i+2n,a,m1,a,m2,a,m3, a,mk ,a,mn,算法图示,A=,复杂性,O(m,2,n),int MaxSum(int m, int n, int *a),int sum = 0, *b = new int n + 1;,for (int i = 1;i = m;i +) ,for (int k = 1;k = n;k +) bk = aik;,for (int j = i+ l;j = m;j +),for (int k = l;k sum) sum = max;,return sum;,复杂性,O(n),总复杂性,O(m,2,n),最大,m,子段和问题,-,自学,给定由,n,个整数（可能为负整数）组成的序列,a,1,，,a,2,，,，,a,n,，以及一个正整数,m,，要求确定序列,a,1,，,a,2,，,，,a,n,的,m,个不相交子段，使这,m,个子段的总和达到最大。,设,b(i,，,j,）表示数组,a,的前,j,项中,i,个子段和的最大值，且第,i,个子段含,aj,（,1,i,m,，,i,j,n,）。则所求的最优值显然为,max b( m,，,j),。,时间复杂性,O(mn,2,),，空间,O(mn),作业,1,、试求,A=b,a,a,b,a,b,a,b,和,B=a,b,a,b,b,a,b,b,a,的,LCS,2,、 设,X=A,B,C,B,D,A,B,和,Y=B,D,C,A,B,A,，求,LCS,（,X,，,Y,）,分析,3-3,（线性规划），,实现题,3-3,（石子合并问题），,3-1,（,2,机调度）,