为什么这是一种贪心算法？

Question

6

我在我的教科书上有这个问题:

"假设我们有一组活动需要安排在许多讲堂中，任何活动都可以在任何讲堂中进行。我们希望使用尽可能少的讲堂来安排所有活动。给出一个有效的贪心算法来确定哪些活动应该使用哪些讲堂。"

(第一个解决方案)

我的问题是，为什么这个算法是贪心算法？

我认为它是因为它做了（贪心？）的选择，总是将一个活动放入一个已经有一个或多个活动的讲堂中（如果可能），而不是将活动放入一个新的空讲堂中。但我不确定。 :)

- Guest

既“贪心”又“高效”... 呃 - bragboy

@Bragby：实际上这取决于他们所指的“效率”是什么。也许这里指的是计算效率（即速度），而不是找到高效解决方案的能力... - digEmAll

4个回答

2

这是因为在考虑其它问题之前，你需要首先最大限度地利用讲堂1。从这个意义上讲，讲堂1是“贪心的”。

- Ted Hopp

是的，事实上有时贪心算法也被称为“近视算法”，因为它们对问题具有短视。 - digEmAll

维基百科有一篇关于贪心算法的好文章。 - Ted Hopp

1

贪心算法的定义是在每一步中选择表面上最好的选择，而不考虑几步之后的情况。因此，它找到了搜索空间的局部最小值（梯度下降可能值得一查）。象棋程序是一个很好的例子，贪心算法总是会做出最强有力的直接移动（拿走一枚棋子，最大化棋子发展），但不会考虑未来几步的情况。

不幸的是，我现在似乎无法打开您包含的链接。但我可以猜测该算法是贪心的，因为一旦它将事件安排到大厅中，它就不会重新考虑那个决定（回溯在这一点上可能值得快速查询）。

- Charles Keepax

1

我不知道是否存在单一官方定义的“贪心算法”，但对我而言，贪心算法是将问题简化为选择一系列局部最优解的解决方案，希望当它们组合在一起时，它们接近于整体最优解。（有时这种希望不只是希望。）

- biziclop

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- soandos · Accepted Answer

贪心意味着您不会重新考虑您的选择。这使得想出最佳解决方案非常困难，并描述了该算法。