第6章 动态规划

1、1第 6 章236.1 一般方法与求解步骤一般方法与求解步骤动态规划简介 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。 20世纪50年代美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，创立了解决多阶段过程优化问题的新方法动态规划。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。46.1.11.几个概念几个概念 多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。 对于每一个决策序列，可以在满足问

2、题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。 52. 举例说明举例说明67 3. 最优性原理最优性原理 最优性原理：“作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略”。 也就是说,最优决策序列中的任何子序列都是最优的。 最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。 最优子结构特性是动态规划求解问题的必要条件。 8 例如，求得在数字串8473139

3、26中插入5个乘号，使乘积最大的最优解为： 8*4*731*3*92*6=38737152 该最优解包含了在84731中插入2个乘号使乘积最大为8*4*731；在7313中插入1个乘号使乘积最大为731*3；在3926中插入2个乘号使乘积最大为3*92*6等子问题的最优解，这就是最优子结构特性。 最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。 4. 最优子结构特性最优子结构特性9（1） 把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。（2） 将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，

4、并确定初始（边界）条件。（3） 应用递推求解最优值。（4） 根据计算最优值时所得到的信息，构造最优解。 构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题具体实际记录更多的信息，根据所记录的信息构造出问题的最优解。 6.1.2 动态规划求解步骤动态规划求解步骤10 6.2 装载问题装载问题11(2） 动态规划设计1213 14【例6.3】 在一个由n个数字组成的数字串中插入r个乘号(1rn10)，将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大。例如，对给定的整数847313926，如何插入r=5个乘号，使其乘积最大? 如何插入r=4个乘号，使其乘积最大

5、?15例子给定一个数字串：847313926，插入r=5个乘号目标：求最优值目标：求最优值f(9,5)设前8个数字中已插入4个乘号，则最大乘积为f(8,4)*6设前7个数字中已插入4个乘号，则最大乘积为f(7,4)*26设前6个数字中已插入4个乘号，则最大乘积为f(6,4)*926设前5个数字中已插入4个乘号，则最大乘积为f(5,4)*3926比较以上比较以上4个数值的最大值即为个数值的最大值即为f(9,5)以此类推，为了求以此类推，为了求f(8,4):设前7个数字中已插入3个乘号，则最大乘积为f(7,3)*2设前6个数字中已插入3个乘号，则最大乘积为f(6,3)*92设前5个数字中已插入3个

6、乘号，则最大乘积为f(5,3)*392设前4个数字中已插入3个乘号，则最大乘积为f(4,3)*1392比较以上比较以上4个数值的最大值即为个数值的最大值即为f(8,4)为了求取f(i,k)，考察数字串的前i个数字，设前j(kji)个数字中已插入k-1个乘号的基础上，在第j个数字后插入第k个乘号，显然此时的最大乘积为f(j,k-1)*a(j+1,i)。可以得到递推关系式：f(i,k)=max(f(j,k-1)*a(j+1,i) (kji)前j个数字没有插入乘号时的值显然为前j个数字组成的整数，f(j,0)=a(1,j) (1ji)18for(d=0,j=1;j=n;j+) d=d*10+bj-1

7、-48; /* 把b数组的一个字符转化为数值 */ a1j=d; fj0=a1j; /* f(j,0)赋初始值 */ for(k=1;k=r;k+) for(i=k+1;i=n;i+) for(amax=0,j=k;ji;j+) for(d=0,u=j+1;u=i;u+) d=d*10+bu-1-48; aj+1i=d; if(amaxfjk-1*aj+1i) /* 求f(j,k-1)*a(j+1,i)最大值 */ amax=fjk-1*aj+1i; fik=amax; /* 赋值给f(i,k) */ printf(“printf(“最优值为最优值为%ld”,fn,r);%ld”,fn,r);

8、 nn19省略数组a(i,j)与amax也,以上递推可简化为：for(d=0,j=1;j=n;j+) d=d*10+bj-1-48; /* 把b数组的一个字符转化为数值 */ fj0=d; /* 计算初始值fj0 */ for(k=1;k=r;k+) for(i=k+1;i=n;i+) for(j=k;ji;j+) for(d=0,u=j+1;u=i;u+) d=d*10+bu-1-48; /* 计算d即为a(j+1,i) */ if(fikm(i+1,cw), i=1,2,n-1则 xi=1; 装载w(i). 其中cw=c开始， cw=cw-x(i)*w(i).否则, x(i)=0,不装载w

9、(i) 。 最后，所装载的物品效益之和与最优值比较，最后，所装载的物品效益之和与最优值比较，决定决定w(n)是否装载是否装载。 26 3. 动态规划顺推设计动态规划顺推设计27 顺推计算最优值顺推计算最优值 for(j=0;j=w1 ) g1j=p1; /* 首先计算g(1,j) */else g1j=0;for(i=2;i=n;i+) /* 顺推计算g(i,j) */for(j=0;j=wi & gi-1ji，比较当 a(j)a(i)时的b(j)的最大值，显然b(i)为这一最大值加1，表示加上a(i)本身这一项。因而有递推关系： b(i)=max(b(j)+1 (a(j)a(i),1i=1;

10、i-) max=0;for(j=i+1;j=n;j+) if(aimax) max=bj; bi=max+1; /* 逆推得bi */ 逆推依次求得逆推依次求得b(n-1),b(1)b(n-1),b(1)，比较这，比较这n-1n-1个值得其个值得其中的最大值中的最大值lmaxlmax，即为所求的最长非降子序列的长度即最，即为所求的最长非降子序列的长度即最优值优值。 32(3） 构造最优解从序列的第1项开始，依次输出b(i)分别等于lmax,lmax-1,1的项a(i)，这就是所求的一个最长非降子序列。(4） 算法复杂度分析以上动态规划算法的时间复杂度为以上动态规划算法的时间复杂度为O(n2)O

11、(n2)，空间复杂度为空间复杂度为O(n)O(n)。 336.5.2 最长公共子序列34(1） 建立递推关系35(2) 逆推计算最优值根据以上递推关系, 逆推计算最优值c(0,0)流程为:for(i=0;i=m;i+) cin=0; /* 赋初始值 */ for(j=0;j=0;i-) /* 计算最优值 */ for(j=n-1;j=0;j-) if(xi=yj) cij=ci+1j+1+1; else if(cij+1ci+1j) cij=cij+1; else cij=ci+1j; printf( printf(最长公共子串的长度为：最长公共子串的长度为：%d,c00);%d,c00);

12、36(3) 构造最优解为构造最优解，设置数组s(i,j)： 当x(i)=y(j)时s(i,j)=1；当x(i)y(j)时s(i,j)=0。实施x(i)与 y(j)比较，其中i=0,1,m-1;j=t,1,n-1； 变量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项。构造

13、最长公共子序列描述：构造最长公共子序列描述：for(t=0,w=0,i=0;i=m-1;i+)for(j=t;jb(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=n-1,2,1 边界条件：b(n,j)=a(n,j), j=1,2,n。 所求的最大路径数值和即问题的最优值为所求的最大路径数值和即问题的最优值为b(1,1)b(1,1)。 39(2) 逆推计算最优值for(j=1;j=1;i-) /* 逆推得bij */for(j=1;jbi+1j) bij=aij+bi+1j+1; stmij=R; else

14、bij=aij+bi+1j; stmij=L;Printf(“%d”,b(1,1);40(3) 构造最优解为了确定与并输出最大路径,利用stm数组从上而下查找:先打印a(1,1),若stm(1,1)= R ，则下一个打印a(2,2),否则打印a(2,1)。一般地,在输出i循环（i=2,3,n）中： 若 stm(i-1,j)=R 则打印 -R-;a(i,j+1);同时赋值j=j+1. 若 stm(i-1,j)=L 则打印 -L-;a(i,j);.依此打印出最大路径，即所求的最优解依此打印出最大路径，即所求的最优解. 416.6.2 边数值矩形的最优路径搜索【例6.9】 已知n行m列的边数值矩阵，

15、每一个点可向右或向下两个去向，试求左上角顶点到右下角顶点的所经边数值和最小的路径。例如给出一个例如给出一个4 4行行5 5列的边数值矩形如下图所示。列的边数值矩形如下图所示。 42(1(1） 建立递推关系建立递推关系 从点(i,j)水平向右的边长记为r(i,j)(jm)，点(i,j)向下的边长记为d(i,j)(i=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-) /* 逆推求解a(i,j) */ for(j=m-1;j

16、=1;j-) if(ai+1j+dijaij+1+rij) aij=ai+1j+dij;stij=d; else aij=aij+1+rij;stij=r;所求左上角顶点到右下角顶点的最短路程即最优值为所求左上角顶点到右下角顶点的最短路程即最优值为a(1,1)a(1,1)。 44(3) 构造最优解利用路标数组输出最优解，从点（1,1）即i=1,j=1开始判断： if(stij=d) printf(-%d-,dij);i+; else printf(-%d-,rij);j+;必要时可打印出点座标。(4） 算法的复杂度分析以上动态规划算法的时间复杂度为以上动态规划算法的时间复杂度为O(mn)O(m

17、n)。 456.7 动态规划与其他算法的比较6.7.1 动态规划与递推比较(1) 动态规划是用来求解多阶段最优化问题的有效算法，而递推一般是解决某些判定性问题或计数问题的方法，两者求解对象有区别。(2) 动态规划求解的多阶段决策问题必须满足最优子结构特性，而递推所求解的计数问题无需满足最优子结构特性。(3) 动态规划在求得问题的最优值后通常需构造出最优值的最优决策序列，即求出最优解，而递推在求出计数结果后没有最优解的构造需求。(4) 从算法的时间复杂度而言，动态规划通常设置二维以上数组，其时间复杂度与二重循环以上的递推时间复杂度基本相同，一般都在O(n2)以上。(5) 当动态规划与递推需设置三维数组时，其空间复杂度都比较高，限制了求解范围。 466.7.2 动态规划与贪心算法比较(1) 动态规划算法求解最优化问题，通过建立每一阶段状态转移之间的递