计算机常用算法与程序设计教程 第6章 动态规划

《计算机常用算法与程序设计教程 第6章 动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章动态规划1常用算法与程序设计主要内容2常用算法与程序设计6.1一般方法与求解步骤动态规划简介动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，创立了解决多阶段过程优化问题的新方法——动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。3常用算法与程序设计6.1.1一般方法1.几个概念多阶段决策问题，是指这样的一类特殊的活动过程，问

2、题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。4常用算法与程序设计2.举例说明5常用算法与程序设计6常用算法与程序设计3.最优性原理最优性原理：“作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优

3、策略”。也就是说,最优决策序列中的任何子序列都是最优的。最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。最优子结构特性是动态规划求解问题的必要条件。7常用算法与程序设计例如，求得在数字串847313926中插入5个乘号，使乘积最大的最优解为：8*4*731*3*92*6=38737152该最优解包含了在84731中插入2个乘号使乘积最大为8*4*731；在7313中插入1个乘号使乘积最大为731*3；在3926中插入2个乘号使乘积最大为

4、3*92*6等子问题的最优解，这就是最优子结构特性。最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。4.最优子结构特性8常用算法与程序设计（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。（2）将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始（边界）条件。（3）应用递推求解最优值。（4）根据计算最优值时所得到的信息，构造最优解。构造最优解就是具体求出最优决策序列。通常在计算最优值时，

5、根据问题具体实际记录更多的信息，根据所记录的信息构造出问题的最优解。6.1.2动态规划求解步骤9常用算法与程序设计6.2装载问题10常用算法与程序设计(2）动态规划设计11常用算法与程序设计(3)递推计算最优值for(j=0;j=1;i--)/*逆推计算m(i,j)*/for(j=0;j<=c1;j++)if(j>=w[i]&&m[i+1][j]

6、i]]+w[i])m[i][j]=m[i+1][j-w[i]]+w[i];elsem[i][j]=m[i+1][j];printf(“%d”,m[1][c1]);12常用算法与程序设计(3）构造最优解构造最优解即给出所得最优值时的装载方案。if(m[i][cw]>m[i+1][cw])（其中cw为当前的装载量，i=1,2,,n-1）装载w[i];else不装载w[i];if(所载集装箱重量≠m(1,c1))装载w[n].13常用算法与程序设计6.3插入乘号问题【例6.3】在一个由n个数字组成的数字串

7、中插入r个乘号(1≤r

8、，在第j个数字后插入第k个乘号，显然此时的最大乘积为f(j,k-1)*a(j+1,i)。于是可以得递推关系式:f(i,k)=max(f(j,k-1)*a(j+1,i))（k≤j