最近在研究一些贪心算法问题。我对局部最优感到困惑。如您所知，贪婪算法由局部最优选择组成。但局部最优决策的组合并不一定意味着全局最优，对吧？
以找零为例：用最少的硬币换成 15 美分，如果有
10 美分、5 美分和 1 美分硬币，那么您可以用一张 10 美分和一张 5 美分来实现这一点。但是，如果我们添加 12 美分的硬币，贪婪算法就会失败，因为 (1×12 美分 + 3×1 美分) 使用的硬币比 (1×10 美分 + 1×5 美分) 更多。
考虑一些经典的贪心算法，例如 Huffman、Dijkstra。在我看来，这些算法是成功的，因为它们没有退化情况，这意味着局部最优步骤的组合始终等于全局最优。我理解对吗？
如果我的理解是正确的，是否有一种通用方法来检查贪婪算法是否最优？
我在网站其他地方发现了一些关于贪婪算法的讨论。
不过，这个问题并没有涉及太多细节。
Recently I've been looking at some greedy algorithm problems. I am confused about locally optimal. As you know, greedy algorithms are composed of locally optimal choices. But combining of locally optimal decisions doesn't necessarily mean globally optimal, right?
Take making change as an example: using the least number of coins to make 15¢, if we have
10¢, 5¢, and 1¢ coins then you can achieve this with one 10¢ and one 5¢. But if we add in a 12¢ coin the greedy algorithm fails as (1×12¢ + 3×1¢) uses more coins than (1×10¢ + 1×5¢).
Consider some classic greedy algorithms, e.g. Huffman, Dijkstra. In my opinion, these algorithms are successful as they have no degenerate cases which means a combination of locally optimal steps always equals global optimal. Do I understand right?
If my understanding is correct, is there a general method for checking if a greedy algorithm is optimal?
I found some discussion of greedy algorithms elsewhere on the site.
However, the problem doesn't go into too much detail.
发布评论
评论（4）
一般来说，只要问题是凸的，局部最优解始终是全局最优解。这包括线性规划；具有正定目标的二次规划；以及具有凸目标函数的非线性规划。 （但是，NLP 问题往往具有非凸目标函数。）
如果启发式函数具有某些属性，启发式搜索将为您提供具有局部最优决策的全局最优值。有关详细信息，请查阅人工智能书籍。
但总的来说，如果问题不是凸的，我不知道有什么方法可以证明局部最优解的全局最优性。
Generally speaking, a locally optimal solution is always a global optimum whenever the problem is convex. This includes linear programming; quadratic programming with a positive definite objective; and non-linear programming with a convex objective function. (However, NLP problems tend to have a non-convex objective function.)
Heuristic search will give you a global optimum with locally optimum decisions if the heuristic function has certain properties. Consult an AI book for details on this.
In general, though, if the problem is not convex, I don't know of any methods for proving global optimality of a locally optimal solution.
有一些定理表达了贪婪算法在拟阵方面是最佳的问题。有关详细信息，请参阅此维基百科部分：http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms
There are some theorems that express problems for which greedy algorithms are optimal in terms of matroids (also:greedoids.) See this Wikipedia section for details: http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms
贪心算法几乎永远无法成功找到最优解。在这种情况下，这很大程度上取决于问题本身。正如 Ted Hopp 所解释的，使用凸曲线，可以找到全局最优值，当然假设您要找到目标函数的最大值（相反，如果要最小化，凹曲线也可以工作）。否则，你几乎肯定会陷入局部最优。这假设您已经知道目标函数。
我能想到的另一个因素是邻里功能。某些邻域，如果足够大，将包含全局最大值和局部最大值，这样您就可以避免局部最大值。但是，您不能将邻域设置得太大，否则搜索速度会很慢。
换句话说，是否使用贪心算法找到全局最优是特定于问题的，尽管在大多数情况下，您不会找到全局最优。
A greedy algorithm almost never succeeds in finding the optimal solution. In the cases that it does, this is highly dependent on the problem itself. As Ted Hopp explained, with convex curves, the global optimal can be found, assuming you are to find the maximum of the objective function of course (conversely, concave curves also work if you are to minimise). Otherwise, you will almost certainly get stuck in the local optima. This assumes that you already know the objective function.
Another factor which I can think of is the neighbourhood function. Certain neighbourhoods, if large enough, will encompass both the global and local maximas, so that you can avoid the local maxima. However, you can't make the neighbourhood too large or search will be slow.
In other words, whether you find a global optimal or not with greedy algorithms is problem specific, although for most cases, you will not find the globally optimal.
您需要设计一个见证示例，其中算法是全局算法的前提失败了。根据算法和问题进行设计。
你的硬币找零的例子不是一个有效的例子。硬币的设计目的是为了拥有所有可能的组合，但不会增加混乱。您添加的 12c 没有保证，而且是额外的。
添加后，问题不再是硬币变化，而是另一个问题（即使主题是硬币，您也可以将示例更改为您想要的）。为此，您自己给出了一个见证示例来表明该问题的贪心算法将陷入局部最大值。
You need to design a witness example where your premise that the algorithm is a global one fails. Design it according to the algorithm and the problem.
Your example of the coin change was not a valid one. Coins are designed purposely to have all the combinations possible, but not to add confusion. Your addition of 12c is not warranted and is extra.
With your addition, the problem is not coin change but a different one (even though the subject are coins, you can change the example to what you want). For this, you yourself gave a witness example to show the greedy algorithm for this problem will get stuck in a local maximum.