贪心算法
一种贪婪算法是一种简单、直观的算法，用于优化问题。算法在每一步都做出最优选择，试图找到解决整个问题的整体最优方法。贪婪算法在一些问题上是非常成功的，例如霍夫曼编码它用于压缩数据，或dijkstra的算法，用于在图中找到最短路径。
但是，在许多问题中，贪婪的策略不会产生最佳解决方案。例如，在下面的动画中，贪婪算法寻求找到最大总和的路径。它通过选择每个步骤中的最大可用号码来实现这一点。贪婪算法未能找到最大的总和，因为它仅基于它在任何一步中的信息基础的决策，而不考虑整个问题。
通过实现最大的总和，在每个步骤中，贪婪算法将选择似乎是最佳立即选择的目标，因此它将在第二步中选择12而不是3，而不会达到最佳解决方案，其中包含99个．[1]
贪心算法
贪婪算法的结构
贪婪算法获取特定问题中的所有数据，然后设置一个规则，在算法的每个步骤中为解决方案添加哪些元素。在上面的动画中，数据集是图中的所有数字，规则是在图的每一层中选择最大的数字。算法构建的解决方案是所有这些选择的总和。
如果下面两个属性都是真的，贪婪算法可以用来解决这个问题。
- 贪婪的选择物业：通过在每一步选择最优方案，可以得到全局(整体)最优解。
- 最佳子结构：如果整个问题的最佳解决方案包含对子问题的最佳解决方案，则问题具有最佳的子结构。
换句话说，贪婪算法处理的是这样的问题:在每一步上，都有一个选择，在这一步之前是问题的最优解，在最后一步之后，算法产生整个问题的最优解。
为了得到贪心算法，需要确定问题中的最优子结构或子问题。然后，确定解决方案将包括什么(例如，最大和，最短路径，等等)。创建一种迭代的方法来遍历所有的子问题并构建一个解决方案。
贪心算法的局限性
有时贪婪算法无法找到全局最佳解决方案，因为它们不考虑所有数据。通过贪婪算法所做的选择可能取决于它到目前为止所做的选择，但它不知道它可以制造的未来选择。
在下面的图中，一个贪婪算法试图找到通过图的最长路径(每个节点内的数量占总长度)。为了做到这一点，它在算法的每个步骤中选择最大的数字。通过对图的快速视觉检查，很明显，这种算法不会得到正确的解决方案。正确的解决方案是什么?为什么贪婪算法不适合这个问题?
贪心算法的一个例子，在树中搜索最大的路径[2]
图中最长路径的正确解是 ．这对我们来说很清楚，因为我们可以看到没有其他节点的组合将接近一笔节点 ，所以无论我们选择什么路径，我们都知道它应该有 的路径。只有一个选项包括 ： ．
贪婪算法无法解决这个问题，因为它纯粹基于当时最好的答案是：在每个步骤中做过选择最大的数。然而，由于可能存在一些算法还没有看到的巨大数字，它最终可能会选择一条不包含这个巨大数字的路径。求最大和或最长路径的子问题的解并不一定出现在整个问题的解中。最优子结构和贪婪选择性质在这类问题中不成立。
这里，我们来看一种形式背包问题．背包问题涉及到，如果你想优化某些价值，你应该从一组物品中选择哪个物品子集:可能是物品的价值、物品的大小，或者价值与大小的比例。
在这个问题中，我们将假设我们可以拿一个物品或留下它（我们不能占用物品的小数部分）。我们还将假设每个项目中只有一个。我们的背包具有固定的大小，我们希望优化我们采取的物品的价值，因此我们必须选择我们谨慎的物品。[3]
我们的背包最多能装25个单位的空间。
这是物品清单和它们的价值。
项 尺寸 价格 笔记本电脑 22. 12. PlayStation 10. 9. 教科书 9. 9. 篮球 7. 6. 我们选择哪些物品优化价格？
有两个贪婪的算法我们可以提议解决这个问题。一个规则，可以在每个步骤中选择具有最大价格的项目，另一个具有在每个步骤中选择最小的大小项目的规则。
- 最大价格算法：在第一步，我们拍了笔记本电脑。我们获得了 价值单位，但现在只能携带 背包中的额外空间单位。由于没有仍然适合包的物品，我们只能拍摄笔记本电脑并共有 单位的价值。
- 最小的项目算法：在第一步，我们将采取最小的项目：篮球。这给了我们 价值单位，让我们留下 袋子里的空间单位。接下来，我们选择下一个最小的项目，课本。这就得到了 价值单位，让我们留下 空间单位。由于没有剩下的物品 单位空间或更小，我们不能再带更多的物品。
贪婪算法给出的解 价值单位和 单位的价值。但这两个都不是最佳解决方案。你自己检查一下桌子，看看是否能确定一个更好的选择。
采取教科书和Playstation产量 价值和占用的单位 空间单位。这是最佳答案，我们可以看到贪婪的算法不会解决贪婪的选择，因为贪婪的选择和最佳的子结构属性不保持。
在贪婪算法失败的问题中，动态编程可能是一种更好的方法。
应用程序
贪婪算法有许多应用。以下是着名图搜索算法，Dijkstra算法的贪婪性质的简要说明。
迪杰斯特拉算法
dijkstra的算法用于在图中找到节点之间的最短路径。该算法维护一组不受检测的节点，并计算从给定节点到另一个节点的暂定距离。如果算法找到到达给定节点的较短方法，则会更新路径以反映较短的距离。此问题具有令人满意的优化子结构，自IF 连接到 连接到 ，路径必须经历 和 到达目的地 ，然后是最短的路径 到 和最短的路径 到 必须是最短路径的一部分 到 ．所以子问题的最优答案确实对整个问题的最优答案有贡献。这是因为该算法能够跟踪到任何给定节点的最短路径。
用Dijkstra算法来寻找最短路径一种和B.．它选择距离最低的未访问顶点，计算通过它到每个未访问邻居的距离，如果更小，则更新邻居的距离。在与邻居完成后访问（设置为红色）。[4]
霍夫曼编码
霍夫曼编码是一种贪婪方法成功的算法的另一个例子。霍夫曼算法分析了一个消息，并根据消息中使用的字符的频率，它为每个符号分配可变长度编码。更常用的符号将具有更短的编码，而罕见的符号将具有更长的编码。
霍夫曼编码算法有关发生特定符号的频率或概率的信息。它开始从底部构建前缀树，从列表中的两个最小可能符号开始。它需要这些符号并形成包含它们的子树，然后从列表中删除各个符号。该算法将子树中元素的概率和添加到列表中的子树和其概率。接下来，算法搜索列表并选择具有最小概率的两个符号或子树。它使用那些制作新子树的人，从列表中删除原始子树/符号，然后将新子树及其组合概率添加到列表中。这重复，直到有一棵树，并添加了所有元素。在每个子树上，创建每个符号的最佳编码并一起组成整体最佳编码。
对于贪婪算法的许多应用程序，请参阅另请参见部分。
也可以看看
参考
- ，S.贪婪 - 搜索路径 - 示例．来自2016年5月2日，来自https://en.wikipedia.org/wiki/file :greeyy-search-path-example.gif.
- ，S.Greedy-search-path．从2016年5月4日中检索到的https://commons.wikimedia.org/wiki/file：greeyy-search-path.gif.
- okie，。贪心算法．来自2016年5月2日，来自http://www.radford.edu/~nokie/classes/360/greedy.html.
- ,我。Dijkstra算法动画．来自2016年5月2日，来自https://commons.wikimedia.org/wiki/file:dijkstra_animation.gif
