贪婪算法与最优子结构

Question

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

问题：

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

Answer 1

我找到了答案，很高兴与大家分享：

1. 什么是最优/非最优子结构？如果一个问题的最优解可以有效地从子问题的最优解中构造，则称为最优子结构。这个性质被用来确定动态规划和贪婪算法对一个问题的有用性。
2. 什么是局部最优和全局最优?优化问题的局部最优是相邻的候选解集中的最优(最大或极小)解。全局最优-是所有可能的解中的最优解，而不仅仅是特定值邻域中的最优解。
3. 如何证明贪婪算法产生全局最优解？通常情况下，全局最优可以通过归纳法来证明。一般采用贪婪算法求解具有最优子结构的问题，通过归纳法证明每一步都是最优的。否则，如果问题表现为重叠子问题，则使用动态规划。

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

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

贪婪选择性质：通过贪婪地选择局部最优选择，得到全局最优解。

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

最后，贪婪算法的几个好例子。