跳到主要内容

贪心算法

提示
  1. 基本原理：贪婪算法通过在每一步选择当前最优选项解决问题，不考虑这些选择是否会导致全局最优解。
  2. 决策属性：贪婪算法适用于具有贪婪选择性质和最优子结构的问题，即每一步的局部最优选择能导致全局最优解。
  3. 优缺点：贪婪算法易于实现，对某些问题效果良好，但并不总能保证得到最优解。例如，在寻找树的最长路径问题中，贪婪选择可能导致非最优解。

贪婪算法是一种通过选择当前可用的最佳选项来解决问题的方法。它不关心当前的最佳结果是否会带来整体最优的结果。

该算法不会改变之前的决策，即使选择是错误的。它以自顶向下的方式工作。

这种算法可能并不适用于所有问题的最佳结果。这是因为它总是选择局部最佳选择以产生全局最佳结果。

然而，我们可以确定如果问题具有以下属性，那么该算法是否可以用于该问题：

1. 贪婪选择性质

如果问题的最优解可以通过在每一步选择最佳选择而无需重新考虑一旦选择的先前步骤，那么可以使用贪婪方法解决该问题。这种属性称为贪婪选择性质。

2. 最优子结构

如果问题的整体最优解对应于其子问题的最优解，那么可以使用贪婪方法解决该问题。这种属性称为最优子结构。

贪婪方法的优点​

  • 该算法更容易描述。
  • 该算法在某些情况下表现更好（但不是在所有情况下）。

贪婪方法的缺点​

正如前面所述，贪婪算法并不总是产生最优解。这是该算法的主要缺点。

例如，假设我们想要从下面的树的根到叶子找到最长路径。让我们在这里使用贪婪算法。

应用贪婪方法来查找最长路径

贪婪方法

  1. 让我们从根节点 20 开始。右子节点的权重为 3，左子节点的权重为 2。

  2. 我们的问题是找到最大路径。而此刻的最优解是 3。所以，贪婪算法将选择 3。

  3. 最后，3 的唯一子节点的权重是 1。这给我们带来了最终结果 20 + 3 + 1 = 24。

然而，这不是最优解。如下图所示，还有一条路径承载更多的权重（20 + 2 + 10 = 32）。

最长路径

因此，贪婪算法并不总是提供最优/可行的解决方案。

贪婪算法​

  1. 首先，解决方案集（包含答案）为空。
  2. 在每个步骤中，将一个项目添加到解决方案集，直到找到解决方案。
  3. 如果解决方案集是可行的，则保留当前项目。
  4. 否则，拒绝该项目，不再考虑。

现在让我们使用这个算法来解决一个问题。

示例 - 贪婪算法​

问题：您必须使用尽可能少的硬币来找零。
金额：$18

可用硬币有
  $5 硬币
  $2 硬币
  $1 硬币
每种硬币的数量没有限制。

解决方案：

  1. 创建一个空的 解决方案集 = { }。可用硬币为 {5, 2, 1}。
  2. 我们要找到 总和 = 18。让我们从 总和 = 0 开始。
  3. 总是选择面值最大的硬币（即 5），直到 总和 > 18。（当我们在每个步骤选择最大值时，我们希望更快地达到目标。这个概念被称为贪婪选择性质。）
  4. 在第一次迭代中，解决方案集 = {5} 和 总和 = 5。
  5. 在第二次迭代中，解决方案集 = {5, 5} 和 总和 = 10。
  6. 在第三次迭代中，解决方案集 = {5, 5, 5} 和 总和 = 15。
  7. 在第四次迭代中，解决方案集 = {5, 5, 5, 2} 和 总和 = 17。（在这里我们不能选择 5，因为这样做会使 总和 = 20 大于 18。所以我们选择第二大的硬币，即 2。）
  8. 类似地，在第五次迭代中，选择 1。现在 总和 = 18 和 解决方案集 = {5, 5, 5, 2, 1}。

不同类型的贪婪算法​

最后于 更新