第6章 动态规划

《第6章 动态规划》由会员分享，可在线阅读，更多相关《第6章 动态规划（47页珍藏版）》请在文档大全上搜索。

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),1