greedy - 如何证明贪心法行不通

Question

对于贪婪方法无法给出最优值的任何给定问题，我们可以找到一个反例来反驳该方法。

但是，是否有可能证明对于给定的问题，一般情况下任何贪心方法都不起作用。

Answer 1

我能想到的最普遍的答案是任何贪心算法都会找到局部最优值。如果一个问题有多个局部最优值，其中只有一个代表全局最优值，那么任何贪心算法都可能陷入局部最优值之一。

要找到一个反例，您所要做的就是找出具有这种局部最优的问题实例，并构造它，以便您“欺骗”算法使其进入局部最优。

我不认为有一种通用的方法可以证明贪婪的方法是行不通的。反驳一个算法的最好方法可能是找到一个它没有产生正确结果的反例。