Algorithms_Chapter_3_贪婪技术-1

贪婪算法是一种什么方法贪婪算法（Greedy Algorithm）是一种简单而经典的算法设计方法，通常用于解决优化问题。

贪婪算法每一步都采取当前情况下最优的选择，希望最终得到全局最优解。

本文将介绍贪婪算法的基本原理、应用场景以及一些经典的贪婪算法实例。

基本原理贪婪算法的基本原理是通过局部最优解来推导得到全局最优解。

在每一步中，贪婪算法选择当前看起来最好的选择，而不考虑之后的结果能否达到最优。

这种直观的选择策略有时可以给出全局最优解，但并非在所有问题中都成立。

贪婪算法的设计过程通常包含以下几个步骤：1. 定义问题的解空间和解集合，将问题转化成对这些解的选择和判定。

2. 根据问题的特点，设计选择策略，确定选择的标准。

3. 使用选择策略，逐步构建解，直到满足问题要求或无法继续选择。

需要注意的是，贪婪算法只能提供近似解，不能保证一定能得到最优解。

因此，在应用贪婪算法时需要仔细分析问题的性质，确定贪婪选择的合理性。

应用场景贪婪算法通常应用于具有贪婪选择性质的问题，即每一步都可以做出局部最优选择的问题。

这种性质常见于以下场景：最小生成树在图论中，最小生成树问题是指在一个连通无向图中找到一棵包含所有顶点且边权重之和最小的树。

典型的贪婪算法解决该问题的方法是普利姆算法（Prim's Algorithm）和克鲁斯卡尔算法（Kruskal's Algorithm）。

普利姆算法从一个起始顶点出发，每次选择与当前生成树连接的最短边对应的顶点，直到生成树包含所有顶点。

而克鲁斯卡尔算法则是从边集合中每次选择最小的边，同时保证不形成环，直到生成树包含所有顶点。

背包问题背包问题是在给定背包容量和一系列物品的重量和价值的情况下，如何选择物品放入背包中，使得背包中物品的总价值最大。

贪婪算法在背包问题的解决中有时也能给出较好的近似解。

一种典型的贪婪算法解决背包问题的方法是基于每个物品的单位价值（即单位重量所能获得的价值）来进行选择。

怎么处理？
30
The Design and Analysis of Algorithms
Chapter 1 Introduction to Algorithms
What’s an Algorithm?
算法是一系列解决问题的清晰指令，也就是说，能够对 一定规范的输入，在有限时间内获得所要求的输出。
16
The Design and Analysis of Algorithms
算法可以解决哪些问题
找出人类DNA中所有100000种基因，确定构成人类DNA的30亿种化学基 17 对的各种序列。
The Design and Analysis of Algorithms
算法可以解决哪些问题
快速访问和检索互联网数据
The Design and Analysis of Algorithms
例子
• “贝格尔”编排法(Beiger Arrangement) 把参赛队数分一半(参赛队为单数时，最后以“0” 表示形成双数)，前一半由1号开始，自上而下写在 左边；后一半的数自下而上写在右边，然后用横线 把相对的号数连接起来。这即是第一轮的比赛。 第二轮将第一轮右上角的编号(“0”或最大的一个代 号数)移到左角上，第三轮又移到右角上，以此类推。 即单数轮次时“0”或最大的一个代号在右上角，双 数轮次时则在左上角。
//使用欧几里得算法计算gcd(m,n) //输入：两个不全为0的非负整数m,n //输出：m，n的最大公约数
28
The Design and Analysis of Algorithms
例子
• “贝格尔”编排法(Beiger Arrangement)
这种编排方法是否完美？

贪婪算法
贪婪算法是求解最优化问题的一种方法，每个 最优化问题都包含一组限制条件（ 和一个优化函 数），符合限制条件的问题求解方案称为可行解， 使优化函数取得最佳值的可行解称为最优解。 例1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿， 她可能得到的东西包括一杯水、一桶牛奶、多罐不 同种类的果汁、许多不同的装在瓶子或罐子中的苏
方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价 值为3 0。
当利用重量贪婪策略时，获得的解为x =[1,0], 比最优
解[ 0 , 1 ]要差。
请你用第三种策略解n= 3 ,w=[20,15,15], p=[40,25, 25], c=30 时的最优解。
我们不必因所考察的几个贪婪算法都不能保证 得到最优解而沮丧， 0 / 1背包问题是一个N P-复杂 问题。对于这类问题，也许根本就不可能找到具有
解是最优解。这是一个典型的贪婪算法。
算法思想:
在贪婪算法中采用逐步构造最优解的方法。在 每个阶段，都作出一个看上去最优的决策（在一定 的标准下）。决策一旦作出，就不可再更改。作出 贪婪决策的依据称为贪婪准则。
一种获得最优分配的贪婪方法是逐步分配任务。 每步分配一件任务，且使其处于最优解。在选择何 种饮料时，采用以下贪婪准则：根据欲选择饮料的 满意度的大小来决定选择何种饮料，若此种饮料的 数量无法满足婴儿的需求，且有其它饮料可以选择， 则选择其它的饮料，直到满足饮料总量的要求。
实际上，我们可以从上述算法中得到启发。并最
终可以获得最优解。考虑：首先将最多k 件物品放入 背包，如果这k 件物品重量大于c，则放弃它。否则， 剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序 装入。通过考虑由启发法产生的解法中最多为k 件物

贪婪算法的基本原理贪婪算法（Greedy Algorithm）是一种常见的算法设计思想，它在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解。

贪婪算法的基本原理可以概括为“局部最优选择，期望全局最优解”。

在每个步骤中做出局部最优选择是贪婪算法的关键特点。

贪婪算法通常适用于满足贪婪选择性质（Greedy Choice Property）和最优子结构（Optimal Substructure）的问题。

贪婪选择性质意味着通过做出局部最优选择，可以得到全局最优解。

最优子结构意味着一个问题的最优解可以通过一系列子问题的最优解来表示。

当一个问题具有最优子结构性质时，我们可以通过贪婪算法来求解问题。

1.定义问题的优化目标。

2.将问题分解为若干子问题，子问题必须满足最优子结构性质。

3.设计一个贪婪策略，通过局部最优选择来做出决策。

4.解决每个子问题，得到局部最优解。

5.将各个子问题的解合并，得到原问题的解。

不过，贪婪算法不一定能得到全局最优解，因为它只关注局部最优选择，并没有进行全局。

有时，贪婪算法会陷入局部最优解而无法达到全局最优解。

因此，在使用贪婪算法求解问题时，必须确保问题满足贪心选择性质和最优子结构性质。

贪婪算法在许多问题中都有广泛的应用。

以下是几个常见问题的例子：1.最小生成树问题：通过选择边的方式，连接图中的所有顶点，并使得选择的边权和最小。

2.背包问题：在给定的背包容量下，选择一些物品放入背包中，使得物品的总价值最大。

3.哈夫曼编码：通过贪心选择思想构建最优的可变长度编码，以实现数据的高效压缩。

4.集合覆盖问题：从一组集合中选择最少的集合，覆盖全集的元素。

总结起来，贪婪算法是一种简单有效的算法设计思想，它通过局部最优选择来逐步求解问题，并期望达到全局最优解。

贪婪算法适用于满足贪心选择性质和最优子结构性质的问题，但不保证一定能得到全局最优解。

在实际应用中，我们需要理解问题的特点和约束条件，并根据问题的性质选择适合的算法来解决问题。