文档介绍：动态规划的特点及其应用
摘要: 本文的主要内容就是分析它的特点。第一部分首先探究了动态规划的本质,因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较,从中探寻动态规划的一些更深层次的特点。文章在分析动态规划的特点的同时,还根据这些特点分析了我们在解题中应该怎样利用这些特点,怎样运用动态规划。这对我们的解题实践有一定的指导意义。本文介绍了动态规划的基本思想和基本步骤,通过实例研究了利用动态规划设计算法的具体途径,讨论了动态规划的一些实现技巧,并将动态规划和其他一些算法作了比较,最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。
关键词: 动态规划,阶段
1 引言
动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。 等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
2 动态规划的基本思想
一般来说,只要问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;而分治法中的各个子问题是独立的(即不包含公共的子子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包