本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
在计算机科学中,贪心算法是一种遵循问题求解启发式的算法,即在每个阶段做出局部最优选择,以期找到全局最优。在许多问题中,贪心策略通常不会产生最优解,但贪心启发法可能是某些问题的最佳策略,它可以在合理的时间内产生正确解的近似值。
贪心算法是一种在每个阶段都做出局部最优选择,希望找到全局最优的算法。
贪心算法与其他算法的主要区别在于,贪心算法从不重新考虑其选择,即使这会导致更好的整体解决方案。
贪心算法通过在每个阶段做出局部最优选择来工作,以期找到全局最优。
理解贪心算法如何工作的关键是要认识到它们并不总是在寻找最佳的整体解决方案,而是在每个单独的阶段寻找最佳解决方案。
当局部最优选择可能导致全局最优时,最好使用贪心算法。
一个常见的例子是最短路径问题。在最短路径问题中,我们得到一组节点和一组连接它们的边。我们还获得了一个起始节点和一个目标节点。该问题的目标是找到从起始节点到目标节点的最短路径。
贪心算法通过始终选择从当前节点到目标节点的最短路径来解决这个问题。虽然这可能并不总能找到最短路径,但很可能会找到接近最短路径的路径。
这是一个贪婪算法的简单示例。考虑以下问题:
给你一组不同价值的硬币,你被要求找到赚取一定数量的钱所需的最少硬币数量。
贪心算法总是首先选择价值最高的硬币来解决这个问题。例如,如果可用的硬币是 1、5、10 和 25,而你想赚的钱是 30,那么贪心算法会先选择价值 25 的硬币,然后选择价值 5 的硬币。这将给出总共 2 个硬币,这是制作 30 个所需的最少硬币数量。
1.实现硬币找零问题的贪心算法。
3.使用贪心算法求解问题。
5.使用贪心算法求解问题。