设计与分析——贪心法

---

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

贪婪算法逐个构建解决方案，以能够立即带来好处的方式选择下一个部分。这种方法从不重新考虑之前做出的选择。该方法主要用于解决优化问题。贪心法很容易实现，并且在大多数情况下非常有效。因此，我们可以说，贪心算法是一种基于启发式的算法范式，每一步都遵循局部最优选择，希望找到全局最优解。

在许多问题中，尽管它在合理的时间内给出了近似（接近最优）解，但它并没有产生最优解。

贪心算法的组成部分

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

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

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

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

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

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

应用领域

贪心法用于解决很多问题，例如

• 使用 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 的最小生成树算法

• 图表 - 地图着色

• 图 - 顶点覆盖

• 背包问题

• 作业调度问题

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