最近，我一直在研究一些贪婪的算法问题。我对局部最优感到困惑。如您所知，贪婪算法由局部最优选择组成。但是结合局部最优决策不一定意味着全局最优，对吗？
以进行更改为例:如果有，使用最少的硬币数来赚15¢
10美分，5美分和1美分的硬币，则可以用一枚10美分和一枚5美分来实现。但是，如果我们添加一个12¢硬币，则贪婪算法将失败，因为(1×12¢+ 3×1¢)使用的硬币要多于(1×10¢+ 1×5¢)。
考虑一些经典的贪婪算法，例如霍夫曼，迪克斯特拉。在我看来，这些算法是成功的，因为它们没有退化的情况，这意味着局部最优步骤的组合始终等于全局最优。我明白吗？
如果我的理解是正确的，是否存在检查贪婪算法是否最佳的通用方法？
我发现了一些discussion of greedy algorithms elsewhere on the site。
但是，问题并没有涉及太多细节。
最佳答案
一般而言，只要问题凸出，局部最优解始终是全局最优。这包括线性编程；具有肯定目标的二次规划；以及具有凸目标函数的非线性编程。 (但是，NLP问题往往具有非凸的目标函数。)
如果启发式函数具有某些属性，则启发式搜索将为您提供具有局部最优决策的全局最优。有关这方面的详细信息，请查阅AI书。
但是，总的来说，如果问题不是凸性的，我不知道有任何方法可以证明局部最优解的全局最优性。