最近我一直在看一些贪心算法问题。我对局部最优感到困惑。你知道，贪心算法是由局部最优选择组成的。但是组合局部最优决策并不一定意味着全局最优，对吗？
以找零钱为例：用最少的硬币来凑15美分，如果我们有10美分、5美分和1美分的硬币，那么您可以用一个10美分和一个5美分实现这个目标。但是如果我们添加一个12美分的硬币，贪心算法将失败，因为（1×12美分+3×1美分）使用的硬币比（1×10美分+1×5美分）还多。
考虑一些经典的贪心算法，例如Huffman、Dijkstra。在我看来，这些算法是成功的，因为它们没有退化的情况，这意味着局部最优步骤的组合总是等于全局最优。我的理解正确吗？
如果我的理解正确，是否有一种通用方法来检查贪心算法是否是最优的？
我发现了一些网站上关于贪心算法的讨论。然而，该问题没有详细说明。
一般来说，只要问题是凸的，局部最优解就是全局最优解。这包括线性规划；具有正定目标函数的二次规划；以及具有凸目标函数的非线性规划。（然而，NLP问题往往具有非凸目标函数。）
如果启发式搜索具有某些属性，它将在局部最优决策的基础上给出全局最优解。有关详细信息，请参考人工智能书籍。
总的来说，如果问题不是凸的，我不知道任何证明局部最优解为全局最优解的方法。
有一些定理表达了在 matroids（也称为 greedoids）方面贪心算法是最优的问题。详情请参见维基百科的这个部分：http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms
你需要设计一个证明例子，证明算法是全局性的假设失败了。根据算法和问题进行设计。
你的硬币找零的例子不是有效的。硬币被特意设计成具有所有可能的组合，但不会造成混淆。你添加的12美分是没有必要的，而且是多余的。
通过你的添加，这个问题不再是硬币找零，而是另一个问题（即使主题是硬币，你也可以将例子改为你想要的）。因此，你自己提供了一个证明例子，以展示贪心算法在这个问题上会陷入局部最大值。
