当局部最优解等于全局最优解时？关于贪心算法的思考
最近我一直在研究一些贪婪的算法问题。我对局部最优感到困惑。如你所知，贪婪算法是由局部最优选择组成的。但是组合局部最优决策并不一定意味着全局最优，对吧？
以找零为例:用最少的硬币制造15美分，如果我们有10美分，5美分和1美分的硬币，那么你可以用一个10美分和一个5美分来实现这一点。但如果我们添加一个12美分的硬币，贪婪算法就会失败，因为(1×12+3×1)使用的硬币比(1×10+1×5)多。
考虑一些经典的贪婪算法，例如Huffman，Dijkstra。在我看来，这些算法是成功的，因为它们没有退化的情况，这意味着局部最优步骤的组合总是等于全局最优。我没理解错吧？
如果我的理解是正确的，有没有一种通用的方法来检查贪婪算法是否是最优的？
我找到了一些discussion of greedy algorithms elsewhere on the site。然而，这个问题并没有涉及太多的细节。
回答 4
Stack Overflow用户
发布于 2011-06-29 09:13:43
一般而言，当问题是凸的时，局部最优解总是全局最优解。这包括线性规划；具有正定目标的二次规划；以及具有凸目标函数的非线性规划。(但是，NLP问题往往具有非凸目标函数。)
如果启发式函数具有某些属性，启发式搜索将为您提供全局最优和局部最优决策。有关这方面的详细信息，请参考一本AI书。
一般来说，如果问题不是凸的，我不知道有什么方法可以证明局部最优解的全局最优性。
Stack Overflow用户
发布于 2011-06-29 18:11:36
有一些定理表达了贪婪算法在拟阵方面是最优的问题(也称为拟阵)。有关详细信息，请参阅维基百科部分：http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms
Stack Overflow用户
发布于 2011-06-29 10:38:12
贪婪的算法几乎从来没有成功地找到最优解。在它确实存在的情况下，这高度依赖于问题本身。正如Ted Hopp解释的那样，对于凸曲线，可以找到全局最优，假设你要找到目标函数的最大值(相反，如果你要最小化，凹曲线也可以)。否则，你几乎肯定会陷入局部最优。这里假设您已经知道目标函数。
我能想到的另一个因素是邻域函数。某些邻域，如果足够大，将同时包含全局和局部最大值，以便您可以避免局部最大值。但是，您不能将邻居设置得太大，否则搜索速度会很慢。
换句话说，贪婪算法是否找到全局最优解是特定于问题的，尽管在大多数情况下，您不会找到全局最优解。
https://stackoverflow.com/questions/6514637
复制相似问题
腾讯云开发者
