贪心算法

一个贪婪算法是一种用于优化问题的简单、直观的算法。算法在每一步都做出最优选择，因为它试图找到解决整个问题的整体最优方法。贪婪算法在某些问题上是相当成功的，例如哈夫曼编码哪一个用于压缩数据，或迪杰斯特拉算法，用于寻找通过图的最短路径。

然而，在许多问题中，贪心策略并不能产生最优解。例如，在下面的动画中，贪心算法寻找的是和最大的路径。它通过在每一步选择最大的可用数字来做到这一点。然而，贪婪算法无法找到最大的和，因为它只根据每一步的信息做出决策，而不考虑整个问题。

贪心算法的目标是达到最大的和，在每一步中，它会选择似乎是最优的立即选择，所以它会在第二步中选择12而不是3，不会达到包含99的最佳解。^[1]

贪婪算法的结构

贪婪算法获取一个特定问题的所有数据，然后在算法的每一步设置一个规则，为哪些元素添加到解决方案中。在上面的动画中，数据集是图表中所有的数字，规则是在图表的每一层中选择最大的可用数字。算法构建的解决方案是所有这些选择的和。

如果下面两个属性都为真，则可以使用贪心算法来解决问题。

• 贪心选择的属性:通过在每一步选择最优方案，可以得到全局(整体)最优解。
• 最优子结构:如果整个问题的最优解包含子问题的最优解，则该问题具有最优子结构。

换句话说，贪婪算法处理的问题是，在每一步，都有一个选择是该问题的最优解，在最后一步之后，算法产生了整个问题的最优解。

要做一个贪心算法，识别问题中的一个最优子结构或子问题。然后，确定解决方案将包括什么(例如，最大的和，最短路径，等等)。创建某种迭代的方法来遍历所有子问题并构建解决方案。

有时贪婪算法因为没有考虑所有的数据而不能找到全局最优解。贪婪算法所做的选择可能取决于它目前所做的选择，但它不知道它未来可能做出的选择。

在下面的图中，一个贪心算法试图找到通过图的最长路径(每个节点内的数字构成总长度)。为此，它在算法的每一步中选择最大的数字。通过对图的快速视觉检查，很明显，该算法不会得到正确的解。正确的解决方案是什么?为什么贪心算法不适合这个问题?

贪心算法的一个例子，在树中搜索最大的路径^[２]

---

图中最长路径的正确解是 $7 3 1 99$．这对我们来说是很清楚的，因为我们可以看到其他节点的组合不会接近于的和 $99$所以无论我们选择哪条路，我们都知道它应该是这样的 $99$的路径。只有一个选项包括 $99$： $7 3 1 99$．

贪婪算法不能解决这个问题，因为它的决策纯粹是基于当时的最佳答案:在每一步做了选择最大的数。然而，由于算法可能还没有看到某个巨大的数字，它最终可能会选择一条不包含这个巨大数字的路径。寻找最大和或最长路径的子问题的解不一定出现在整个问题的解中。最优子结构和贪婪选择的性质并不适用于这类问题。 $_ \广场$

在这里，我们将看一种形式背包问题．背包问题涉及到，如果您想优化某些价值，那么您应该从一组项目中选择哪个项目子集:可能是项目的价值、项目的大小，或者价值与大小的比值。

在这个问题中，我们假设我们要么接受一个项目，要么放弃它(我们不能接受一个项目的一小部分)。我们还将假设每种商品只有一个。我们的背包有一个固定的尺寸，我们想要优化我们所带物品的价值，所以我们必须谨慎地选择我们所带的物品。^［３］

我们的背包最多能装25个单位的空间。

这是商品清单及其价值。

项	大小	价格
移动PC	22	12
游戏机	10	9
教科书	9	9
篮球	7	6

我们选择哪些商品来优化价格?

---

我们可以提出两种贪婪算法来解决这个问题。其中一个规则是在每一步选择价格最高的物品，另一个规则是在每一步选择尺寸最小的物品。

• 最大价格算法:第一步，我们取笔记本电脑。我们获得 $12$单位的价值，但现在只能携带 $25-22 = 3$背包中额外空间的单位。因为剩下的东西都装不进包里了，我们只能带着笔记本电脑，总共有 $12$单位的价值。
• 最小物品算法:在第一步，我们将取最小的物品:篮球。这给了我们 $6$价值单位，留给我们的是 $25-7 = 18$袋子里的空间单位。接下来，我们选择下一个最小的项目，教科书。这就得到了 $6 + 9 = 15$价值单位，留给我们的是 $=带队打出了9$单位的空间。因为没有剩下的项目 $9$空间单位或更少，我们不能带更多的物品。

贪婪算法得到的解 $12$价值单位和 $15$单位的价值。但这两种方法都不是最佳解决方案。自己检查表格，看看是否可以选择更好的项目。

拿着教科书和PlayStation游戏机 $9 + 9 = 18$价值单位和占用单位 $10 + 9 = 19$单位的空间。这是最优答案，我们可以看到贪婪算法不能解决背包问题，因为贪婪选择和最优子结构属性不成立。 $_ \广场$

在贪婪算法失败的问题中，动态规划这可能是一个更好的方法。

贪婪算法有很多应用。下面是一个著名的图搜索算法——Dijkstra算法的贪婪本质的简要解释。

迪杰斯特拉算法

迪杰斯特拉算法用于查找图中节点之间的最短路径。该算法维护一组未访问的节点，并计算给定节点到另一个节点的暂定距离。如果算法找到到达给定节点的更短的路径，路径就会更新以反映更短的距离。该问题具有满足条件的优化子结构 $一个$被连接到 $B,$ $B$被连接到 $C$，这条路必须穿过 $一个$而且 $B$到达目的地 $C$的最短路径 $一个$来 $B$最短路径是从 $B$来 $C$必须是最短路径的一部分 $一个$来 $C$．所以子问题的最优答案确实有助于整个问题的最优答案。这是因为算法跟踪到任何给定节点的最短路径。

Dijkstra算法寻找最短路径之间一个而且b．它选择距离最小的未访问顶点，计算通过它到每个未访问邻居的距离，如果更小，则更新邻居的距离。马克拜访了邻居(设置为红色)。^[4]

霍夫曼编码

哈夫曼编码是贪婪方法成功的算法的另一个例子。霍夫曼算法分析消息，根据消息中使用的字符的频率，为每个符号分配可变长度的编码。较常用的符号编码较短，而罕见的符号编码较长。

霍夫曼编码算法接受有关特定符号出现的频率或概率的信息。它开始从下往上构建前缀树，从列表中概率最小的两个符号开始。它接受这些符号并形成包含它们的子树，然后从列表中删除单个符号。该算法将子树中元素的概率相加，并将子树及其概率添加到列表中。接下来，算法搜索列表并选择概率最小的两个符号或子树。它使用这些来创建一个新的子树，从列表中删除原来的子树/符号，然后将新的子树及其组合概率添加到列表中。这个过程一直重复，直到有一个树，所有的元素都被添加。在每个子树上，为每个符号创建最优编码，并共同组成整体最优编码。

有关贪婪算法的更多应用，请参见“参阅”部分。

• *搜索
• Dijkstra最短路径算法
• 旅行推销员的问题
• 哈夫曼编码
• 动态规划

1. ,年代。Greedy-search-path-example．检索自2016年5月2日https://en.wikipedia.org/wiki/File:Greedy-search-path-example.gif
2. ,年代。Greedy-search-path．检索自2016年5月4日https://commons.wikimedia.org/wiki/File:Greedy-search-path.gif
3. 农夫移民。贪心算法．检索自2016年5月2日http://www.radford.edu/~nokie/classes/360/greedy.html
4. ,我。Dijkstra算法动画．检索自2016年5月2日https://commons.wikimedia.org/wiki/File:Dijkstra_Animation.gif