贪婪算法

在所有算法方法中，最简单直接的方法是贪婪方法。在这种方法中，决策是基于当前可用的信息做出的，而不考虑当前决策对未来的影响。

贪婪算法逐部分构建解决方案，选择下一部分的方式是，它能带来直接的收益。这种方法永远不会重新考虑之前做出的选择。这种方法主要用于解决优化问题。贪婪方法易于实现，并且在大多数情况下都非常高效。因此，我们可以说贪婪算法是一种基于启发式的算法范式，它在每个步骤都遵循局部最优选择，希望找到全局最优解。

在许多问题中，它虽然不能产生最优解，但在合理的时间内给出了一个近似（接近最优）的解。

贪婪算法的组成部分

贪婪算法具有以下五个组成部分：

• 候选集 - 从该集合中创建解决方案。

• 选择函数 - 用于选择要添加到解决方案中的最佳候选者。

• 可行性函数 - 用于确定候选者是否可以用于为解决方案做出贡献。

• 目标函数 - 用于为解决方案或部分解决方案分配一个值。

• 解决方案函数 - 用于指示是否已达到完整解决方案。

应用领域

贪婪方法用于解决许多问题，例如

• 使用 Dijkstra 算法查找两个顶点之间的最短路径。

• 使用 Prim/Kruskal 算法等查找图中的最小生成树。

硬币计数问题

硬币计数问题是通过选择最少的硬币来计算到一个期望值，贪婪方法强制算法选择尽可能大的硬币。如果我们提供 1、2、5 和 10 的硬币，并要求我们计算 18，则贪婪过程将是：

• 1 - 选择一枚 10 元硬币，剩余计数为 8

• 2 - 然后选择一枚 5 元硬币，剩余计数为 3

• 3 - 然后选择一枚 2 元硬币，剩余计数为 1

• 4 - 最后，选择一枚 1 元硬币解决了问题

虽然，这似乎工作正常，但对于此计数，我们只需要选择 4 枚硬币。但是，如果我们稍微更改一下问题，则相同的方法可能无法产生相同的最优结果。

对于我们有 1、7、10 值的硬币的货币系统，计算 18 值的硬币将是绝对最优的，但对于 15 这样的计数，它可能使用的硬币多于必要。例如，贪婪方法将使用 10 + 1 + 1 + 1 + 1 + 1，总共 6 枚硬币。而同样的问题可以用 3 枚硬币（7 + 7 + 1）解决

因此，我们可以得出结论，贪婪方法选择一个直接的优化解决方案，并且在全局优化是一个主要问题的地方可能会失败。

贪婪方法在哪里失效

在许多问题中，贪婪算法无法找到最优解，此外它可能会产生最差的解。旅行商和背包等问题不能使用这种方法解决。

贪婪算法的示例

大多数网络算法都使用贪婪方法。以下列出其中的一些：

• 旅行商问题

• Prim 最小生成树算法

• Kruskal 最小生成树算法

• Dijkstra 最小生成树算法

• 图 - 地图着色

• 图 - 顶点覆盖

• DSA - 分数背包问题

• DSA - 带截止日期的作业排序

• DSA - 最佳合并模式算法

我们将在本教程的后续章节中详细讨论这些示例。