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

Question

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

Answer 1

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

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

也许您的意思是“如果贪心算法有时会产生最佳解决方案，……”在这种情况下，答案又是微不足道的。

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

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

一个很好的例子是对一个数字列表进行排序，使所有个位数的数字排在两位数之前，两位数排在三位数字之前，依此类推。IE。您不关心 99 是否在 11 之前，反之亦然，您只希望 9 在 25 之前，33 在 872 之前，555 在 1234 之前。

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

如果这没有帮助，什么都不会;-)

Answer 2

贪心算法是一种遵循问题求解启发式的算法，即在每个阶段[1]做出局部最优选择，希望找到全局最优。在许多问题中，贪心策略通常不会产生最优解，但贪婪启发式算法可能会产生局部最优解，在合理时间内逼近全局最优解。贪心算法大多（但并非总是）无法找到全局最优解，因为它们通常不会对所有数据进行详尽的操作。