问使用贪心算法进行优化

EN

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

当然，答案是微不足道的是。如果贪心算法解决了问题，它会产生一个最优解，根据定义，该最优解位于最优解集中。

也许你的意思是“如果贪婪的算法有时会产生最优解，……”在这种情况下，答案同样是微不足道的。

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

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

可以考虑的一个很好的例子是对数字列表进行排序，使所有的单位数排在两位数之前，两位数排在三位数之前，依此类推。也就是说，你不关心99在11之前还是在11之前，你只需要9在25之前，33在872之前，555在1234之前。

这个示例问题有多个最优解。一个懒惰但不贪婪的算法不能确保11在99之前。一个过于热衷的算法会这样做。两者都会产生不同的最优解决方案。

如果这不起作用，什么都不会起作用;-)

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