algorithm - 贪心算法和最优子结构

Question

在维基百科页面上，据说贪心算法只适用于具有最优子结构的问题。

问题：

1. 什么是最优/非最优子结构？
2. 什么是局部最优和全局最优？
3. 如何证明贪心算法产生全局最优？

Answer 1

我找到了答案并很高兴分享：

1. 什么是最优/非最优子结构？如果可以从其子问题的最优解有效地构造最优解，则称该问题具有最优子结构。此属性用于确定动态规划和贪心算法对问题的有用性

2. 什么是局部最优和全局最优？优化问题的局部最优是在相邻候选解集中的最优解（最大或最小）。 全局最优- 是所有可能解决方案中的最优解决方案，而不仅仅是特定值邻域中的那些。

3. 如何证明贪心算法产生全局最优？通常，全局最优可以通过归纳来证明。通常，如果可以通过归纳证明这在每一步都是最优的，则使用贪心算法来解决具有最优子结构的问题。否则，如果问题也表现出重叠的子问题，则使用动态规划。

为了证明一个优化问题可以使用贪心算法来解决，我们需要证明这个问题有以下几点：

最优子结构性质：最优全局解包含其所有子问题的最优解。

贪婪选择特性：通过贪婪地选择局部最优选择可以获得全局最优解。

在某些情况下，拟阵也可以用于机械地证明可以通过贪心方法解决特定问题。

最后，一些贪心算法的好例子。