学习笔记之贪婪算法

贪婪算法设计算法以实现给定问题的最佳解决方案。在贪心算法方法中，决策是从给定的解决方案域做出的。由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。贪心算法试图找到一个本地...

贪婪算法

设计算法以实现给定问题的最佳解决方案。在贪心算法方法中，决策是从给定的解决方案域做出的。由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。

贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。但是，通常贪婪算法不提供全局优化的解决方案。

计数硬币

这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。如果我们提供1,2,5和10值的硬币，我们被要求计算和值为18，那么贪婪的程序将是：

虽然，它似乎工作正常，但这个数量我们只需要选择4个硬币。但是，如果我们稍微改变问题，那么相同的方法可能无法产生相同的最佳结果。

对于货币系统，我们有硬币值为1,7,10的值，计算值为18的硬币绝对是最佳的，但对于15的和值，它可能会使用超过必要的硬币。例如，贪婪的方法将使用10 + 1 + 1 + 1 + 1 + 1，总共6个硬币。而只使用3个硬币（7 + 7 + 1）就可以解决同样的问题

因此，我们可以得出结论，贪婪的方法选择了立即优化的解决方案，并且可能在全局优化是主要问题的情况下失败。

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

在分而治之的方法中，手头的问题被分成较小的子问题，然后每个问题都独立解决。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法进行更多划分的阶段。解决那些“原子”最小可能的子问题。最后合并所有子问题的解决方案以获得原始问题的解决方案。

从广义上讲，我们可以通过三个步骤来理解分而治之的方法。

划分

这一步包括将问题分解成更小的子问题。子问题应该代表原始问题的一部分。这一步通常采用递归方法来分割问题，直到没有子问题可以被进一步分割为止。在这个阶段，子问题本质上变成了原子问题，但仍然代表了实际问题的一部分。

解决

这一步接收到许多要解决的较小的子问题。一般来说，在这个层次上，问题被认为是“解决”了。

合并

当较小的子问题得到解决时，这个阶段递归地将它们组合起来，直到它们形成原始问题的解。这种算法的递归和合并步骤的工作非常接近，以至于它们看起来就像是一个。

以下是计算机算法基于分而治之的编程方法：

动态规划方法类似于分治法，将问题分解为越来越小的子问题。但与分治不同的是，这些子问题并不是独立解决的。相反，这些较小的子问题的结果被记住，并用于类似或重叠的子问题。

当我们遇到问题时，可以用动态规划的方法把问题分解成相似的子问题，这样就可以重用它们的结果。这些算法大多用于优化。在求解子问题之前，动态算法将尝试检验之前求解的子问题的结果。将子问题的解进行组合，以获得最佳解。

所以我们可以说：

对照

与贪心算法(局部优化)相比，动态算法的动机是对问题进行整体优化。

与分治算法不同的是，在分治算法中，解决方案被组合在一起以实现一个整体的解决方案，动态算法使用较小子问题的输出，然后尝试优化较大的子问题。动态算法使用记忆法来记住已经解决的子问题的输出。

使用动态规划方法可以解决以下计算机问题：