algorithm - 使用贪心算法进行优化

Question

如果一个优化问题可以用贪心法来解决，那么它的所有最优解一定总是包含第一选择(即贪心选择)是真的吗？

Answer 1

我将您的问题解释为“所有最佳解决方案的集合必须始终包含第一选择”，否则一个解决方案包含另一个解决方案是没有意义的。

当然，答案是肯定的。如果贪心算法解决了问题，它会产生一个最优解，根据定义，该最优解在最优解集合中。

也许你的意思是“如果一个贪心算法有时产生一个最优解，......”在那种情况下答案也是微不足道的。

如果您的意思是“如果贪心算法有时产生最优解，那么所有有保证的最优算法是否也会产生该解？”答案取决于问题是否具有唯一最优解或多个最优解。

如果一个问题有多个最优解，答案显然是否定的。

一个值得思考的好例子是对数字列表进行排序，使所有单个数字排在两位数之前，两位数排在三位数字之前，等等。 IE。你不关心 99 出现在 11 之前还是相反，你只希望 9 出现在 25 之前，33 出现在 872 之前，555 出现在 1234 之前。

这个示例问题有多个最优解。懒惰但不贪婪的算法无法确保 11 在 99 之前出现。过于热情的算法会这样做。两者都会产生彼此不同的最优解。

如果这没有帮助，什么也没有;-)