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

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