贪心算法和最优子

Question

在Wikipedia page据说贪心算法仅适用于具有最优子问题的理想选择。

问题：

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

Answer 1

我已经找到了答案，并高兴地分享：

1. 什么是最佳/非最佳子？一个问题是说，有如果最优解决方案可以有效地从它的子问题的最优解来构造最优子。此属性用于确定一个问题的动态规划和贪婪算法的有效性
2. 什么是局部和全局最优？最优化问题的局部最优是一个解决方案，是最佳的候选解决方案的邻近集合内（无论是最大或最小）。全球最佳 - 是所有可能的解决方案中的最佳解决方案，而不仅仅是那些在值的特定街区。
3. 如何证明贪心算法产量全局最优解？通常情况下，全局最优可以通过感应来证明。典型地，贪心算法被用于解决与最优子一个问题，如果它可以通过感应来证明，这是在每个步骤最佳的。否则，提供所述问题呈现重叠子问题，以及，使用动态编程。

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

最优子属性：最佳的全球性解决方案包含其所有子问题的最优解。

贪婪选择属性：全局最优解可通过贪婪地选择的一个局部最优的choise来获得。

拟阵可以用于机械地证明一个特定的问题可以用贪婪方法来解决一些情况下可以使用为好。

最后，some good examples of greedy algorithms。