对动态规划法和贪心法的分析和比较.pdf

现代商贸工业 No．2，2009 ModernBusinessTradeIndustry 2009年第2期 对动态规划法和贪心法的分析和比较 肖青青 赵 娜 (中国地质大学(武汉)信息工程学院，湖北 武汉 430074) 摘 要 ：通过动态规划法和贪心法的介绍，并进一步分析和 比较这两种算法在求解 同一 问题时的差异。 关键词 ：动态规划法 ；贪心法 ；0—1背包问题 中图分类号：G04 文献标识码 ：A 文章编号：1672—3198(2009)02—0242—02 1 引言 策无关 。 1．1 动态规划 (5)各阶段状态之间的转换有 明确定义的费用 ，而且在 动态规划 (dynamicprogramming)是运筹学的一个分 选择最佳决策时有递推关系(即动态转移方程)。 支，是求解决策过程最优化的数学方法。20世纪 5O年代初 3 贪心法的基本思想 美国数学家 R．E．Bellman等人在研究多阶段决策过程的优 贪心法从局部 的最优 出发，简单而快捷。对于一个 问 化问题时，提 出了著名的最优化原理 ，把多阶段过程转化为 题 的最优解只能用穷举法得到时 ，用贪心法是寻找问题次 一 系列单阶段问题 ，逐个求解 ，创立 了解决这类过程优化 问 优解 的较好算法 。选择能产生 问题最优解 的最优度量标准 题 的新方法——动态规划 。 是使用贪心法的核心 问题 。 动态规划法的定义：在求解 问题中，对于每一步决策， 假定有n个物体和一个背包，物体 i有质量wi，价值为 列出各种可能的局部解，再依据某种判定条件，舍弃那些肯 pi，而背包的载荷能力为M。若将物体 i的一部分xi(1一i 定不能得到最优解的局部解，在每一步都经过筛选 ，以每一 一n，O 一xi=1)装入背包 中，则有价值 pi*xi。在约 步都是最优解来保证全局是最优解 ，这种求解方法称为动 束条件 (wl*x1+w2*x2+…………+wn*xn)=M下 态规划法。 使 目标 (pl*x1+p2*x2十……+pn*xn)达到极大，此处 0 1．2 贪心法 一xi=1，pi0，1一i一n．这个 问题称为背包 问题 贪心法 (greedymethod)是一种 改进 了的分级处理方 (Knapsackproblem)。 法 。用贪心法设计算法 的特点是一步一步地进行，根据某 要想得到最优解，就要在效益增长和背包容量消耗两 个优化测度(可能是 目标函数 ，也可能不是 目标 函数)，每一 者之间寻找平衡。也就是说，总应该把那些单位效益最高 步上都要保证能获得局部最优解 。每一步 只考虑一个数 的物体先放入背包 。 据，它的选取应满足局部优化条件。若下一个数据与部分 贪心法总是作出在 当前看来最好的选择，也就是说贪 最优解连在一起不再是可行解时，就不把该数据添加到部 心法并不从整体最优考虑，它所作 出的选择只是在某种意 分解中，直到把所有数据枚举完，或者不能再添加为止。这 义上的局部最优选择。虽然贪心法不能对所有的问题都得 种能够得到某种度量意义下的最优解的分级处理方法称为 到整体最优解 ，但对于许多问题它能产生整体最优解。在 贪心法 。 一 些情况下，即使贪心法不能得到整体最优解，其最终结果 2 动态规划的基本思想 却是最优解的很好近似。贪心法是一种最直接的设计技 动态规划法是一种强有力的算法设计技术 ，它被广泛 术 ，它能应用于求解多种问题。这类 问题的一般特征是有 n 用于求解组合最优化问题。这种技术采用 自底向上的方式 个输入以及一组约束条件 ，满足约束条件的任一输入的子