贪心算法和最优子结构

Question

10

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

问题：

- Ivan Voroshilin

Dukeling，我来这里是想看答案的。你的回答没有帮助也不是负一。 - Ivan Voroshilin

@downvoters：请在评论中说明你的反对理由。 - jobin

2

@Jobin 可能是因为这个问题显示出（太）少的研究努力而被踩，但现在它已经是一个自我回答了，所以这个问题不再适用（但我们现在无法找到那些踩它的人，而且赞同已经抵消了它们）。 - Bernhard Barker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ivan Voroshilin · Accepted Answer

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

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

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

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

为了证明可以使用贪心算法解决优化问题，我们需要证明问题具有以下特点：

最优子结构性质：最优全局解包含所有子问题的最优解。 贪心选择性质：通过贪心地选择局部最优的选择，可以获得全局最优解。

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