有关动态规划的一篇小论文.doc

动态规划 Dynam ic Program ming by S tarfish 【摘要】本文介绍了动态规划的基本思想和基本步骤,通过实例研究了利用动态规划设计算法的具体途径, 讨论了动态规划的一些实现技巧,并将动态规划和其他一些算法作了比较,最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。(说明: 这是我中学时候写的一篇小论文,因为公式和图比较多, 为了能在 bbs 上贴出来做了不少删节) 【目录】一。引言二。动态规划的基本思想三。动态规划算法的基本步骤四。动态规划的适用条件五。动态规划的实例分析六。动态规划的技巧——阶段的划分和状态的表示七。动态规划实现中的问题八。动态规划与其他算法的比较九。动态规划的理论模型一。引言动态规划(dynamic programmi ng) 是运筹学的一个分支,是求解决策过程(decision process) 最优化的数学方法。 20 世纪 50 年代初美国数学家 an 等人在研究多阶段决策过程(mult istep deci sion proce ss) 的优化问题时, 提出了著名的最优化原理(princip le of opti mality) ,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。 1957 年出版了他的名著 D ynamic Pro gramming ,这是该领域的第一本著作。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题, 用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划( 如线性规划、非线性规划) ,只要人为地引进时间因素, 把它视为多阶段决策过程,也可以用动态规划方法方便地求解。二。动态规划的基本思想一般来说,只要问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理), 则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择; 而分治法中的各个子问题是独立的(即不包含公共的子子问题) ,因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值, 而动态规划找出其中最优( 最大或最小) 值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这