最近我一直在看一些贪心算法问题。我对局部最优感到困惑。你知道,贪心算法是由局部最优选择组成的。但是组合局部最优决策并不一定意味着全局最优,对吗?
以找零钱为例:用最少的硬币来凑15美分,如果我们有10美分、5美分和1美分的硬币,那么您可以用一个10美分和一个5美分实现这个目标。但是如果我们添加一个12美分的硬币,贪心算法将失败,因为(1×12美分+3×1美分)使用的硬币比(1×10美分+1×5美分)还多。
考虑一些经典的贪心算法,例如Huffman、Dijkstra。在我看来,这些算法是成功的,因为它们没有退化的情况,这意味着局部最优步骤的组合总是等于全局最优。我的理解正确吗?
如果我的理解正确,是否有一种通用方法来检查贪心算法是否是最优的?
我发现了一些网站上关于贪心算法的讨论。然而,该问题没有详细说明。