最近我一直在研究一些贪心算法问题。我对局部最优感到困惑。如您所知，贪心算法由局部最优选择组成。但是结合局部最优决策并不一定意味着全局最优，对吧？
以找零为例：用最少的硬币来凑 15 美分，如果我们有 10 美分、5 美分和 1 美分的硬币，那么你可以用一个 10 美分和一个 5 美分来实现。但是如果我们添加一个 12¢ 的硬币，贪心算法就会失败，因为 (1×12¢ + 3×1¢) 使用的硬币比 (1×10¢ + 1×5¢) 多。
考虑一些经典的贪心算法，例如 Huffman、Dijkstra。在我看来，这些算法是成功的，因为它们没有退化的情况，这意味着局部最优步骤的组合总是等于全局最优。我理解对了吗？
如果我的理解是正确的，是否有检查贪心算法是否最优的通用方法？
我在网站的其他地方发现了一些关于贪心算法的讨论。但是，这个问题并没有涉及太多细节。
一般来说，只要问题是凸的，局部最优解总是全局最优解。这包括线性规划；具有正确定目标的二次规划；和具有凸目标函数的非线性规划。（然而，NLP 问题往往具有非凸目标函数。）
如果启发式函数具有某些属性，则启发式搜索将为您提供具有局部最优决策的全局最优解。有关这方面的详细信息，请参阅 AI 书籍。
不过，总的来说，如果问题不是凸的，我不知道有任何方法可以证明局部最优解的全局最优性。
有一些定理表达了贪心算法在拟阵（也：greedoids）方面是最优的问题。有关详细信息，请参阅此 Wikipedia 部分：http ://en.wikipedia.org/wiki/Matroid#Greedy_algorithms
贪心算法几乎永远不会成功地找到最优解。在这种情况下，这高度依赖于问题本身。正如 Ted Hopp 解释的那样，使用凸曲线，可以找到全局最优值，假设您当然要找到目标函数的最大值（相反，如果要最小化，凹曲线也可以工作）。否则，你几乎肯定会陷入局部最优。这假设您已经知道目标函数。
我能想到的另一个因素是邻域功能。某些邻域（如果足够大）将同时包含全局最大值和局部最大值，这样您就可以避免局部最大值。但是，您不能使邻域太大，否则搜索会很慢。
换句话说，是否使用贪心算法找到全局最优值是特定于问题的，尽管在大多数情况下，您不会找到全局最优值。
您需要设计一个见证示例，其中您的算法是全局算法的前提失败了。根据算法和问题进行设计。
你的硬币变化的例子不是一个有效的例子。硬币的设计目的是为了让所有可能的组合都有可能，但不是为了增加混乱。您添加 12c 是没有保证的，是额外的。
随着您的添加，问题不是硬币变化而是另一个问题（即使主题是硬币，您也可以将示例更改为您想要的示例）。为此，您自己给出了一个见证示例，以显示该问题的贪心算法将陷入局部最大值。