第6讲 动态规划专题讲座.doc

第6章 动态规划6.1 动态规划概述动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代美国数学家贝尔曼（Rechard Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，把多阶段决策过程转化为一系列单阶段问题逐个求解，创立了解决多阶段过程优化问题的新方法动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、装载等问题，用动态规划方法比用其它方法求解更为方便。6.1.1 动态规划的概念动态规划所处理的对象是多阶段决策问题。多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。例6.1 已知6种物品和一个可载重量为60的背包，物品i（i=1,2,6）的重量分别为（15,17,20,12,9,14），产生的效益分别为（32,37,46,26,21,30）。在装包时每一件物品可以装入，也可以不装，但不可拆开装。确定如何装包，使所得装包总效益最大。这就是一个多阶段决策问题，装每一件物品就是一个阶段，每一个阶段都要有一个决策：这一件物品装包还是不装。这一装包问题的约束条件为: 目标函数为:对于这6个阶段的问题，如果每一个阶段都面临2个选择，则共存在26个决策序列。应用贪心算法，按单位重量的效益从大到小装包，得第1件与第6件物品不装，依次装第5、3、2、4件物品，这就是一个决策序列，或简写为序列（0,1,1,1,1,0），该策略所得总效益为130。第1件与第4件物品不装，第2、3、5、6件物品装包，或简写为序列（0,1,1,0,1,1），这一决策序列的总载重量为60，满足约束条件，使目标函数即装包总效益达最大值134，即最优值为134。因而决策序列（0,1,1,0,1,1）为最优决策序列，即最优解，这是应用动态规划求解的目标。在求解多阶段决策问题中，各个阶段的决策依赖于当时的状态并影响以后的发展，即引起状态的转移。一个决策序列是随着变化的状态而产生的。应用动态规划设计使多阶段决策过程达到最优（成本最省，效益最高，路径最短等），依据动态规划最优性原理：“作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”。也就是说，最优决策序列中的任何子序列都是最优的。“最优性原理”用数学语言描述：假设为了解决某一多阶段决策过程的优化问题，需要依次作出n个决策D1,D2,Dn，如若这个决策序列是最优的，对于任何一个整数k，1ki，比较当ajai时的bj的最大值，显然bi为这一最大值加1，表示加上ai本身这一项。因而有递推关系：bi=max(bj)+1 (ajai,1i=1;i) max=0;for(j=i+1;j=n;j+) if(aimax) max=bj; bi=max+1; / 逆推得bi 逆推依次求得bn1,b1，比较这n1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。（3）构造最优解从序列的第1项开始，依次输出bi分别等于lmax,lmax1,1的项ai，这就是所求的一个最长非降子序列。（4）递推实现动态规划程序设计/ 递推实现动态规划 #include #include #include void main() int i,j,n,t,x,max,lmax,a2000,b2000; t=time(0)%1000;srand(t); / 随机数发生器初始化 printf( input n(n2000):); scanf(%d,&n); for(i=1;i=1;i-) / 逆推求最优值lmax max=0; for(j=i+1;j=n;j+) if(aimax) max=bj; bi=max+1; / 逆推得bi if(bilmax) lmax=bi; / 比较得最大非降序列长 printf(n L=%d.n,lmax); / 输出最大非降序列长 x=lmax; for(i=1;ii，比较当ajai时的q(j)的最大值，显然q(i)为这一最大值加1，表示加上ai本身这一项。因而有递归关系：q(i)=max(q(j)+1 (ajai,1ijn)递归出口：q(n)=1（2）递归函数设计int q(int i)int j,f,max; if(i=n) f=1; else max=0; for(j=i+1;j=n;j+) if(aimax) max=q(j); f=max+1; return f;(3) 在主函数中依次调用q(n1),q(1)，比较这n1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。（4）构造最优解从序列的第1项开始，依次输出q(i)分别等于lmax,lmax1,1所那就的项ai，这就是所求的一个最长非降子序列。（5）递归实现动态规划程序设计/ 递归实现动态规划 #include #include #include int i,n,a2000;void main() int t,x,lmax; int q(int i); t=time(0)%1000;srand(t); / 随机数发生器初始化 printf( input n(n2000):); scanf(%d,&n); for(i=1;i=1;i-) if(q(i)lmax) lmax=q(i); / 比较得最大非降序列长 printf(n L=%d.n,lmax); / 输出最大非降序列长 x=lmax; for(i=1;i=n;i+) if(q(i)=x) printf(%d ,ai);x-; / 输出一个最大非降序列 4程序运行示例与讨论运行程序，input n(n2000):1248 16 45 47 52 46 36 28 46 69 14 42L=5.16 45 47 52 69 注意，所给序列长度为5的非降子序列可能有多个，这里只输出其中一个。由上可知，在动态规划设计中，最优值可经递推得到，也可经递归得到。一般地，应用递推效率更高些，以下各案例的动态规划设计中均应用递推得最优值。6.2.2 最长公共子序列一个给定序列的子序列是在该序列中删去若干个元素后所得到的序列。用数学语言表述，给定序列，另一序列，X的子序列是指存在一个严格递增下标序列使得对于所有j=1,2,k有。例如，序列是序列的一个子序列，或按紧凑格式书写，序列“bdca”是“abcdcba”的一个子序列。若序列Z是序列X的子序列，又是序列Y的子序列，则称Z是序列X与Y的公共子序列。例如，序列“bcba”是“abcbdab”与“bdcaba”的公共子序列。1. 案例提出给定两个序列和，找出序列X和Y的最长公共子序列。例如，给出序列X：hsbafdreghsbacdba与序列Y：acdbegshbdrabsa，这两个序列的最长公共子序列如何求得？2动态规划算法设计求序列X与Y的最长公共子序列可以使用穷举法：列出X的所有子序列，检查X的每一个子序列是否也是Y的子序列，并记录其中公共子序列的长度，通过比较最终求得X与Y的最长公共子序列。对于一个长度为m的序列X，其每一个子序列对应于下标集1,2,m的一个子集，即X的子序列数目多达2m个。由此可见应用穷举法求解是指数时间的。最长公共子序列问题具有最优子结构性质，应用动态规划设计求解。（1）建立递推关系设序列和的最长公共子序列为，与(i=0,1,m;j=0,1,n)的最长公共子序列的长度为c(i,j)。若i=m+1或j=n+1，此时为空序列，c(i,j)=0（边界条件）。若x(1)=y(1)，则有z(1)=x(1),c(1,1)=c(2,2)+1（其中1为z(1)这一项）；若x(1)y(1)，则c(1,1)取c(2,1)与c(1,2)中的最大者。一般地，若x(i)=y(j)，则c(i,j)=c(i+1,j+1)+1；若x(i)y(j)，则c(i,j)=max(c(i+1,j),c(i,j+1)。因而归纳为递推关系：边界条件：c(i,j)=0 （i=m+1或j=n+1）（2）逆推计算最优值根据以上递推关系，逆推计算最优值c(0,0)流程为：for(i=0;i=m;i+) cin=0; / 赋初始值 for(j=0;j=0;i) / 计算最优值 for(j=n1;j=0;j) if(xi=yj) cij=ci+1j+1+1; else if(cij+1ci+1j) cij=cij+1; else cij=ci+1j; printf(最长公共子串的长度为：%d,c00); / 输出最优值 以上算法时间复杂度为O(mn)。（3）构造最优解为构造最优解，即具体求出最长公共子序列，设置数组s(i,j)，当x(i)=y(j)时s(i,j)=1；当x(i)y(j)时s(i,j)=0。X序列的每一项与Y序列的每一项逐一比较，根据s(i,j)与c(i,j)取值具体构造最长公共子序列。实施x(i)与y(j)比较，其中i=0,1,m1;j=t,1,n1；变量t从0开始取值，当确定最长公共子序列一项时，t=j+1。这样处理可避免重复取项。若s(i,j)=1且c(i,j)=c(0,0)时，取x(i)为最长公共子序列的第1项;随后，若s(i,j)=1且c(i,j)=c(0,0) 1时，取x(i)最长公共子序列的第2项;一般地，若s(i,j)=1且c(i,j)=c(0,0) w时(w从0开始，每确定最长公共子序列的一项，w增1)，取x(i)最长公共子序列的第w项。构造最长公共子序列描述：for(t=0,w=0,i=0;i=m1;i+)for(j=t;j=n1;j+) if(sij=1 & cij=c00w) printf(%c,xi); w+;t=j+1;break; （4）算法的复杂度分析以上动态规划算法的时间复杂度为O(n2)。3最长公共子序列C程序实现/ 最长公共子序列 #include #define N 100void main()char xN,yN; int i,j,m,n,t,w,cNN,sNN; printf(请输入序列x：); / 先后输入序列 scanf(%s,x); printf(请输入序列y：); scanf(%s,y); for(m=0,i=0;xi!=0;i+) m+; for(n=0,i=0;yi!=0;i+) n+; for(i=0;i=m;i+) cin=0; / 赋边界值 for(j=0;j=0;i) / 递推计算最优值 for(j=n1;j=0;j) if(xi=yj) cij=ci+1j+1+1; sij=1; else sij=0; if(cij+1ci+1j) cij=cij+1; else cij=ci+1j; printf(最长公共子序列的长度为：%d,c00); / 输出最优值 printf(n最长公共子序列为：); / 构造最优解 t=0;w=0; for(i=0;i=m1;i+) for(j=t;j=n1;j+) if(sij=1 & cij=c00w) printf(%c,xi); w+;t=j+1;break; printf(n); 运行程序示例：请输入序列x：hsbafdreghsbacdba请输入序列y：acdbegshbdrabsa最长公共子序列的长度为：9最长公共子序列为：adeghbaba6.3 最优路径搜索本节应用动态规划探讨两类最优路径搜索问题，一类是点数值路径，即连接成路径的每一个点都带有一个数值；另一类是边数值路径，即连接成路径的每一条边都带有一个数值。6.3.1 点数值三角形的最优路径搜索点数值三角形是一个二维数阵：三角形由n行构成，第k行有k个点，每一个点都带有一个数值数。点数值三角形的数值可以随机产生，也可从键盘输入。最优路径通常由路径所经各点的数值和来确定。1. 案例提出在一个n行的点数值三角形中，寻找从顶点开始每一步可沿左斜（L）或右斜（R）向下至底的一条路径，使该路径所经过的点的数值和最小。图6.1 7行点数值三角形例如，n=7时给出的点数值三角形如图6.1所示，如何寻找从项到底的数值和最小路径？该最优路径的数值和为多少？ 2动态规划算法设计设点数值三角形的数值存储在二维数组a(n,n)。（1）建立递推关系设数组b(i,j)为点(i,j)到底的最小数值和，字符数组stm(i,j)指明点(i,j)向左或向右的路标。b(i,j)与stm(i,j)(i=n1,2,1)的值由b数组的第i+1行的第j个元素与第j+1个元素值的大小比较决定，即有递推关系：b(i,j)=a(i,j)+b(i+1,j+1); stm(i,j)=“R” （b(i+1,j+1)b(i+1,j)）b(i,j)=a(i,j)+b(i+1,j); stm(i,j)=“L” （b(i+1,j+1)b(i+1,j)）其中i=n1,2,1边界条件：b(n,j)=a(n,j), j=1,2,n。所求的最小路径数值和即问题的最优值为b(1,1)。（2）逆推计算最优值for(j=1;j=1;i) / 逆推得bij for(j=1;j=i;j+) if (bi+1j+1bi+1j) bij=aij+bi+1j+1;stmij=R; else bij=aij+bi+1j;stmij=L;Printf(%d,b(1,1);（3）构造最优解为了确定与并输出最小路径，利用stm数组从上而下查找：先打印a(1,1)，若stm(1,1)=“R”，则下一个打印a(2,2)，否则打印a(2,1)。一般地，在输出i循环（i=2,3,n）中：若stm(i1,j)=“R”则打印“R”;a(i,j+1)；同时赋值j=j+1。若stm(i1,j)=“L”则打印“L”；a(i,j)；依此打印出最小路径，即所求的最优解. （4）算法的复杂度分析以上动态规划算法的时间复杂度为O(n2)，空间复杂度也为O(n2)。2最小路径寻求与测试程序设计/ 点数值三角形的最小路径 #include #include #include void main() int n,i,j,t; int a5050,b5050; char stm5050; printf(请输入数字三角形的行数n:); scanf(%d,&n); t=time(0)%1000; srand(t); /随机数发生器初始化 for(i=1;in;i+) j=rand(); for(i=1;i=n;i+) for(j=1;j=36-2*i;j+) printf( ); for(j=1;j=i;j+) aij=rand()/1000+1; printf(%4d,aij); / 产生并打印n行数字三角形 printf(n); printf(请在以上点数值三角形中从顶开始每步可左斜或右斜至底); printf(寻找一条数字和最小的路径.n ); for(j=1;j=1;i-) / 逆推得bij for(j=1;j=i;j+) if (bi+1j+1bi+1j) bij=aij+bi+1j+1;stmij=R; else bij=aij+bi+1j;stmij=L; printf(最小路径和为:%dn,b11); / 输出最小数字和 printf(最小路径为:%d,a11);j=1; / 输出和最小的路径 for(i=2;i=n;i+) if(stmi-1j=R) printf(-R-%d,aij+1);j+; else printf(-L-%d,aij); printf(n);运行程序，对于数据如图所示的点数值三角形，输出如下：最小路径和为:74最小路径为:22-R-19-R-10-L-12-R-6-R-2-R-36.3.2 边数值矩形的最优路径搜索边数值矩形也是一个二维数阵：矩形由n行m列构成，每一行有m1条横边，每一列有n1条竖边，每一条边都带有一个数值。最优路径通常由路径所经各边的数值和来确定。1. 案例提出已知n行m列的边数值矩阵，每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最大的路径。例如，给出一个4行5列的边数值矩形如图6.2所示，如何寻找从矩阵的左上角顶点到右下角顶点的数值和最大路径？该最优路径的数值和为多少？ 图6.2 一个4行5列的边数值矩形2动态规划算法设计设矩阵的行数n，列数m，每点为(i,j)，i=1,2,n；j=1,2,m。显然，该边数值矩阵每行有m1条横向数值边，每列有n1条纵向数值边。从点(i,j)水平向右的边长记为r(i,j)(jm)，点(i,j)向下的边长记为d(i,j)(i=1;i) aim=ai+1m+dim;stim=d; / 右边纵列初始化 for(j=m1;j=1;j) anj=anj+1+rnj;stnj=r; / 下边横行初始化 for(i=n1;i=1;i) / 逆推求解a(i,j) for(j=m1;j=1;j) if(ai+1j+dijaij+1+rij) aij=ai+1j+dij;stij=d; else aij=aij+1+rij;stij=r;所求左上角顶点到右下角顶点的最大路程即最优值为a(1,1)。（3）构造最优解利用路标数组输出最优解，从点（1,1）即i=1,j=1开始判断：if(stij=d) printf(%d,dij);i+;else printf(%d,rij);j+;必要时可打印出点座标。（4）算法的复杂度分析以上动态规划算法的时间复杂度为O(n2)。3求边数值矩阵图的最大路径程序设计/ 求边数值矩阵图的最大路径 #include #include #include void main() int m,n,i,j,t,a5050,r5050,d5050; char st5050; t=time(0)%1000;srand(t); / 随机数发生器初始化 printf( 在矩形图中寻找一条路程最大的路径.n); printf( 请输入矩阵的行数n,列数m:); scanf(%d,%d,&n,&m); for(i=1;i=n;i+) for(j=1;j=m;j+) aij=0; printf(n); for(i=1;i=n-1;i+) / 随机产生并打印数值边矩阵 for(j=1;j=m-1;j+) printf( . ); rij=rand()/1000+10; printf(%3d,rij); printf( . n); for(j=1;j=m;j+) dij=rand()/1000+10; printf(%3d ,dij); printf(n); for(j=1;j=1;i-) aim=ai+1m+dim;stim=d; for(j=m-1;j=1;j-) anj=anj+1+rnj;stnj=r; for(i=n-1;i=1;i-) for(j=m-1;j=1;j-) if(ai+1j+dijaij+1+rij) aij=ai+1j+dij;stij=d; else aij=aij+1+rij;stij=r; printf(n 最大路程为：%d.,a11); / 打印最大路程 printf(n 最大路径为：(1,1); j=1;i=1; / 打印最大路径 while(in | jm) if(stij=d) printf(-%d-,dij);i+; printf(%d,%d),i,j); else printf(-%d-,rij);j+; printf(%d,%d),i,j); printf(n); 4运行示例与说明运行程序，对图所示4行5列矩阵得：最大路程为：226.最大路径为：(1,1)-32-(2,1)-30-(2,2)-42-(2,3)-13-(2,4)-29-(3,4)-38-(3,5)-42-(4,5)为操作简单，以上各例中的三角形或矩形的点数据或边数据是应用C语言的随机函数产生的。对于求解某些实际路径问题，具体的点数据或边数据可把随机产生改为通过键盘输入，然后进行搜索，确定最优路径。6.4 装载问题1. 案例提出有n个集装箱要装上两艘载重量分别为c1,c2的轮船，其中集装箱i的重量为，且（不考虑集装箱的体积）。试求解一个合理的装载方案，把所有n个集装箱装上这两艘船。2动态规划算法设计（1）问题求解策略试采用以下的装载策略：1) 首先将第一艘船尽可能装满；2) 将剩余的集装箱装上第二艘船。设装载量为c1的船最多可装maxc1，如果满足不等式则装载问题有解。装载问题不一定总有解。例如，当n=3,c1=c2=50,w=15,40,40，显然无法把这三个集装箱装上这两艘轮船。当问题无解时，作无解说明。（2）动态规划设计为了求取maxc1，应用动态规划设计。目标函数：约束条件：按装载每一个集装箱为一个阶段，共分为n个阶段。1) 建立递推关系设m(i,j)为船C1还有载重量为j，可取集装箱编号范围为：i,i+1,n的最大装载重量值。则当0jw(i)时，物品i不可能装入。m(i,j)与m(i+1, j)相同。而当jw(i)时，有两种选择：不装入物品i，这时最大重量值为m(i+1, j)；装入物品i，这时已增加重量w(i)，剩余载重容量为jw(i)，可以选择集装箱i+1,n来装，最大载重量值为m(i+1, jw(i)+w(i)。我们期望的最大载重量值是两者中的最大者。于是有递推关系以上j、c1与w(i)均为正整数，i=1,2,n,所求最优值为m(1,c1)。2) 递推计算最优值for(j=0;jwn;j+) mnj=0;for(j=wn;j=1;i) / 逆推计算m(i,j) for(j=0;j=wi & mi+1jmi+1cw) （其中cw为当前的装载量，i=1,2, n1） 装载wi;else 不装载wi;if(所载集装箱重量m(1,c1) 装载wn.以上述举例说明：由m(1,16)m(2,16)，装w(1)=2；m(2,14)=m(3,14)，不装w(2)；m(3,14)m(4,14)，装w(3)=13；w(1)+w(3)=15=m(1,16)，不装w(5)。于是得装载方案：C1: 2 13 (15)C2: 5 8 4 (17)（5）算法复杂度分析以上动态规划算法的时间复杂度为O(nc1)，空间复杂度也为O(nc1)。通常c1n，因而上述算法的时间与空间复杂度均高于O(n2)。2装载问题的C程序实现/ 装载问题 #include #define N 100void main()int n,c1,c2,i,j,s,cw,sw,wN,mNN; printf( input c1,c2: ); scanf(%d,%d,&c1,&c2); printf( input n: ); scanf(%d,&n); s=0; for(i=1;ic1+c2) return; / 确保n个集装箱重量之和不大于c1+c2 printf(集装箱重量：); for(i=1;i=n;i+) printf( %d,wi); printf(n n=%d,s=%d ,n,s); printf(n c1=%d, c2=%d n,c1,c2); for(j=0;jwn;j+) mnj=0; for(j=wn;j=1;i) / 逆推计算m(i,j) for(j=0;j=wi & mi+1jmi+1jwi+wi) mij=mi+1jwi+wi; else mij=mi+1j; printf(maxc1=%d n,m1c1); / 得最优值m(1,c1) if(m1c1=sc2) / 判断是否有解 printf(C1:); cw=m1c1; for(sw=0,i=1;imi+1cw) cw=wi;sw+=wi; printf( %3d,wi); wi=0; / w(i)装载后赋0,为装船2作准备 if(m1c1sw=wn) printf( %3d,wn); sw+=wn; wn=0; printf( (%d)n,sw); printf(C2:); for(sw=0,i=1;i0) sw+=wi; printf( %3d,wi); printf( (%d)n,sw); else printf(此装载问题无解！); / 输出无解信息 4程序运行与说明运行程序，输入：input c1,c2:120,126input n:15集装箱重量：26 19 24 13 10 20 15 12 6 5 22 7 17 27 20n=15,s=243c1=120, c2=126maxc1=120C1: 15 12 22 7 17 27 20 (120)C2: 26 19 24 13 10 20 6 5 (123) 注意：上述所求解的装载问题中，要求各个集装箱的重量与两船的载重量c1,c2均为正整数。6.5 0-1背包问题01背包问题是应用动态规划设计求解的典型例题。本节在应用动态规划采用逆推与顺推两种设计求解一般01背包问题基础上，拓广到带两个约束条件的二维01背包问题的设计求解。6.5.1 01背包问题1. 案例提出已知n种物品和一个可容纳c重量的背包，物品i的重量为，产生的效益为。在装包时物品i可以装入，也可以不装，但不可拆开装。物品i可产生的效益为，这里。问如何装包，所得装包总效益最大。2最优子结构特性01背包的最优解具有最优子结构特性。设,是01背包的最优解，那么必然是01背包子问题的最优解：背包载重量，共有n1件物品，物品i的重量为，产生的效益为，。若不然，设是该子问题的