贪婪算法
在所有算法方法中，最简单直接的方法是贪婪方法。在这种方法中，决策基于当前可用信息，而不考虑当前决策在未来的影响。
贪婪算法逐个部分构建解决方案，选择下一个部分时，会立即带来收益。这种方法不会重新考虑之前的选择。这种方法主要用于解决优化问题。贪婪方法易于实现，并且在大多数情况下非常高效。因此，我们可以说贪婪算法是一种基于启发式的算法范式，它在每一步都遵循局部最优选择，以期找到全局最优解。
在许多问题中，它虽然在合理的时间内给出了近似（接近最优）解，但并不能产生最优解。
贪婪算法的组成部分
贪婪算法包含以下五个组成部分 −
候选集 − 从该集合中创建一个解。
选择函数 − 用于选择最佳候选集添加到解中。
可行性函数 −用于确定候选函数是否可用于为解决方案做出贡献。
目标函数 − 用于为解或部分解赋值。
解函数 −用于指示是否已得到完整的解决方案。
应用领域
贪婪方法用于解决许多问题，例如
使用 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）即可解决。
因此，我们可以得出结论，贪婪方法会选择一个即时优化的解决方案，但在需要重点考虑全局优化的情况下可能会失败。
贪婪方法失败的原因
在许多问题中，贪婪算法无法找到最优解，而且可能会产生最差解。像旅行商问题和背包问题这样的问题无法用这种方法解决。
贪婪算法示例
大多数网络算法都使用贪婪方法。这里列出了其中一些 −
我们将在本教程的后续章节中详细讨论这些示例。
