1、常用算法与程序设计常用算法与程序设计1常用算法与程序设计常用算法与程序设计2常用算法与程序设计常用算法与程序设计36.1 一般方法与求解步骤动态规划简介动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪 50年代美国数学家贝尔曼（ R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，创立了解决多阶段过程优化问题的新方法 动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。常用算法与程序设计常用算法与程序设计46.1.1 一般方法一般方法1. 几个概念 多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分
2、解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。 常用算法与程序设计常用算法与程序设计52. 举例说明常用算法与程序设计常用算法与程序设计6常用算法与程序设计常用算法与程序设计73. 最优性原理 最优性原理： “ 作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何 ,对前面的决策所形成的状态而言 ,余下的诸决策必须构成最优策略 ” 。 也就是说 ,最优决策
3、序列中的任何子序列都是最优的。 最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。 最优子结构特性是动态规划求解问题的必要条件。 常用算法与程序设计常用算法与程序设计8 例如， 求得在数字串 847313926中插入 5个乘号，使乘积最大的最优解为： 8*4*731*3*92*6=38737152 该最优解包含了在 84731中插入 2个乘号使乘积最大为 8*4*731；在 7313中插入 1个乘号使乘积最大为 731*3；在 3926中插入 2个乘号使乘积最大为3*92*6等子问题的最优解，这就是最优子结构特性。 最优性原理是动态
4、规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。 4. 最优子结构特性常用算法与程序设计常用算法与程序设计9 （ 1） 把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。 （ 2） 将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始（边界）条件。 （ 3） 应用递推求解最优值。 （ 4） 根据计算最优值时所得到的信息，构造最优解。 构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题具体实际记录更多的信息，根据所记录的信息构造出问题的最优解。 6.1.2 动态规划求解步骤常用算法与程序设计常用算法与程序设计106.2 装载问题
