《算法设计与分析》-第三章 动态规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章 动态规划（,Dynamic-Programming,）,3.1,动态规划法的基本思想,3.2,动态规划法的适用条件,3.3,动态规划法的基本步骤,3.4,应用举例,0/1,背包问题,3.1,动态规划法的基本思想,为求解给定问题，有一系列子问题需要解答。对这些子问题按照某种方式仔细设计，使得其后的每一个子问题都可以通过上面已经求出的一个或多个子问题的合并而获得其解。,3.1,动态规划法的基本思想,动态规划法与分治法的异同：,与分治法类似，动态规划法也是对问题进行递归分解。,而当递归分解得到的子问题不互相独立时，用分治法求解，则有些子问题被重复计算了许多次。而动态规划法通过保存已解决的子问题的解，在需要时再找出已求得的解，可以避免大量重复计算。,3.2,动态规划法的适用条件,动态规划法解所能解决的问题一般具有以下两个基本因素：,一、最优子结构性质,当,问题的最优解包含着其子问题的最优解时，称该问题具有,最优子结构性质,。,二、重叠子问题性质,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。,这种性质称为,子问题的重叠性质,。,其它同分治法,3.2,动态规划法的适用条件,一最优子结构性质,当,问题的最优解包含着其子问题的最优解时，称该问题具有,最优子结构性质,。,例,1,：,Fibonacci,数问题,n n,1,F(n,),F(n-1),F(n-2)n1,3.2,动态规划法的适用条件,一、最优子结构性质,当,问题的最优解包含着其子问题的最优解时，称该问题具有,最优子结构性质,。,例,2,：求解二项式系数,1,1,m=0,n=m,其它,3.2,动态规划法的适用条件,一、最优子结构性质,在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,32,动态规划法的适用条件,一、最优子结构性质,例,3,最短路径问题,设,G,是有向图，若,G,中从顶点,i,到顶点,j,有路径存在，找出最短的一条。,下面证明最短路径问题具有最优子结构性质,3.2,动态规划法的适用条件,一、最优子结构性质,证明：,设,i,i,1,i,2,i,k,j,是从,i,到,j,的一条最短路径。从初始顶点,i,开始，设从,i,到下一顶点,i,1,的判定已经做出。接下去，问题就转化为用,i,1,替代,i,，重复原来的问题，找出一条从,i,1,到,j,的路径。显然，,i,1,i,2,i,k,j,一定构成了从从,i,1,到,j,的最短路径（与原问题相同的最优子序列）,3.2,动态规划法的适用条件,一、最优子结构性质,证明：,若不然，设,i,1,r,1,r,2,r,p,j,是一条从,i,1,到,j,的最短路径，则,i,i,1,r,1,r,2,r,p,j,将是一条从,i,到,j,的路径且比路径,i,i,1,i,2,i,k,j,要短，得出矛盾。,所以，最短路径问题具有最优子结构性质。,3.2,动态规划法的适用条件,一、最优子结构性质,利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,3.2,动态规划法的适用条件,二、重叠子问题性质,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。,这种性质称为,子问题的重叠性质,。,3.2,动态规划法的适用条件,二、重叠子问题性质,例,1,：,Fibonacci,数问题的递归树,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(1),Fib(2),Fib(1),T(n,)=,O(Fib(n,),3.2,动态规划法的适用条件,二、重叠子问题性质,例,2,：,求解二项式系数的递归树,T(n,)=O(),3.3,动态规划法的基本步骤,找出最优解的性质，并刻划其结构特征。考察是否适合采用动态规划法。,递归地定义最优值,(,建立递归式或动态规划方程,),。,以自底向上迭代的方式或以自顶向下的,备忘录方法,）计算出,最优值,；,根据计算最优值时得到的信息，构造,最优解,。,3.3,动态规划法的基本步骤,例,1,Fibonacci,数问题,求解步骤：,1,具有最优子结构性质,2,具有重叠子问题性质,3,建立递归式或动态规划方程,4,求解值。,3.3,动态规划法的基本步骤,int,Fib(int,n),f1=f2=0;,for(f,=1,i=0;i=n;i+),f2=f1;f1=f;f=f1+f2;,return f;,3.3,动态规划法的基本步骤,例,2,求解二项式系数,求解步骤：,1,具有最优子结构性质,2,具有重叠子问题性质,3,建立递归式或动态规划方程,4,求解3.3,动态规划法的基本步骤,例,2,求解二项式系数,求解方法：,1,动态规划法：,计算如下序列：,S,0,=,S,1,=,，,S,2,=,，,S,n,=,，,3.3,动态规划法的基本步骤,例,2,求解二项式系数,1,动态规划法：,Pascal,三角形,n,0 1,1 1 1,2 1 2 1,3 1 3 3 1,4 1 4 6 4 1,5 1 5 10,10,5 1,6 1 6 15 20 15 6 1,7 1 7 21 35,35,21 7 1,3.3,动态规划法的基本步骤,例,2,求解二项式系数,int,Binom,（,int,n,int,m,）,int,bMAXSIZE,;b0=1;for(i,=1;i0;j+),bj,=bj+bj-1;,return,bm,;,3.3,动态规划法的基本步骤,例,2,求解二项式系数,求解方法：,2,备忘录法：,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,3.3,动态规划法的基本步骤,例,2,求解二项式系数,2,备忘录法：,int,Binom,（,int,n,int,m,）,if(n,=m|m=0)filltable(n,m,0);return 1;,else,if(!lookupTable(n-1,m,t1),t1=Binom(n-1,m);filltable(n-1,m,t1);,if(!lookupTable(n-1,m-1,t2),t2=Binom(n-1,m-1);filltable(n-1,m-1,t2);,return t1+t2;,3.4,应用举例,0/1,背包问题,0-1,背包问题,给定,n,种物品和一背包。物品,i,的重量是,w,i,，其价值为,v,i,，背包的容量为,C,。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,0-1,背包问题是一个特殊的整数规划问题。,3.4,应用举例,0/1,背包问题,1,最优子结构性质考查,2,建立递归方程,3,重叠子问题性质考查,4,求解,0-1,背包问题,设所给,0-1,背包问题的子问题,的最优值为,m(i,，,j),，即,m(i,，,j),是背包容量为,j,，可选择物品为,i,，,i+1,，,，,n,时,0-1,背包问题的最优值。由,0-1,背包问题的最优子结构性质，可以建立计算,m(i,，,j),的递归式如下。,3.4,应用举例,0/1,背包问题,求解：,1,动态规划法,/,权为整数的迭代法,思考：备忘录法,0-1,背包问题,-,权为整数的迭代法,void,KnapSack(int,v,int,w,int,c,int,n,int,m )/,求,m ,int,jMax,=min(wn-1,c);,for(j=0;j=,jMax;j+)/m(nj,)=0 0=j,wn,mnj,=0;,for(j=,wn;j,=,wn,mnj,=,vn,;,for(i=n-1;i1;i-),int,jMax,=min(wi-1,c);,for(j=0;j=,jMax;j+)/m(i,j,)=m(i+1,j)0=j,wi,mij,=mi+1j;,for(j=,wi;j,=,wn,mij,=max(mi+1j,mi+1j-wi+vi);,m1c=m2c;,if(c,=w1),m1c=max(m2c,m2c-w1+v1);,0-1,背包问题,-,权为整数的迭代法,void,traceback(int,m,int,w,int,c,int,x),/,求,x,for(i,=1;i0?1:0);,