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

Question

关于 Wikipedia page据说贪心算法只适用于具有最优子结构的问题。

问题:

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

Answer 1

我已经找到答案并很高兴分享:

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

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

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

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

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

贪心选择性质:通过贪婪地选择局部最优选择，可以获得全局最优解。

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

最后，some good examples of greedy algorithms .