算法设计与分析论文（贪心算法）.pdfVIP

贪心算法 ——不在贪心中爆发，就在贪心中灭亡 徐晓龙 武汉理工大学计算机科学与技术学院软件ZY1101 班 摘要 本文介绍贪心算法的基本意义以及算法的使用范围，并通过具体的案例来分 析贪心算法的具体应用，从而指出其特点和存在问题。 关键字：贪心算法，贪心策略，TSP 、0/1 背包 引言 我们用了 13 周的时间学完了《算法设计与分析》这本书。这本书中涵盖了 大量的常见算法，包括蛮力法、分治法、动态规划法、贪心算法等等。我最有印 象的就是贪心算法。贪心算法是一种有合理的数据组织和清晰高效的算法，它简 单有效。下面我们来详细解读一下这个算法。 1. 贪心算法的含义 贪心算法可以简单描述为:对一组数据进行排序，找出最小值，进行处理，再 找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状 态下最好或最优的选择，从而希望得到结果是最好或最优的算法。 2. 贪心算法的基本思想 贪心算法，法如其名，每次都贪心的选取当前最优解，一旦确定了当前解， 不管将来有什么结果，之后都不会再修正，这一点与动态规划法比起来稍有逊色。 如果一个问题的最优解只能用蛮力法穷举得到，则贪心法不失为寻找问题近似最 优解的一个较好办法。 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某 个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的 选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行 解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加 算法停止。 3. 贪心算法的基本要素 3.1 贪心选择 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪 心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划 算法的主要区别。 贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择 就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否 具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最 优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作 了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法 证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。 3.2 最优子结构 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性 质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该 问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对 结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做 出选择，不能回退;动态规划则会根据以前的选择结果对当前进行选择，有回退 功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。 4. 贪心算法的核心 贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪 心策略。贪心策略决定着贪心算法是爆发或者是灭亡。所以，选择一个合理、正 确的贪心策略是至关重要的。下面用例子说明： 第一个例子我们选用大家熟知的0/1 背包问题。给定 种物品和一个背包。 n 物品 的重量是 ，其价值为 ，背包的容量为 。在选择物品 装入背包时， i w v C i i i 不可以选择物品 的一部分，一定要全部装入背包，1  i  n 。应如何选择 i 装入背包的物品，使得装入背包中物品的总价值最大? 设 表示物品 装入背包的情况，根据问题的要求，有如下约束条件和目标 x i i 函数： n