贪心算法有什么用?一个真实的例子?
问问题
31285 次
10 回答
19
于 2011-02-01T20:44:19.423 回答
8
任何不可能找到最佳解决方案的事情——或者非常非常困难。
贪心算法在当前点采用最佳解决方案,即使如果您检查了所有替代方案,这不是最佳解决方案
于 2011-02-01T20:22:40.653 回答
8
有些问题使得贪婪的解决方案实际上是最佳的,有时它们就是这样设计的。一个有趣的例子是,许多国家的硬币价值如此贪婪地退回找零(即总是退回最大可能的硬币,直到你完成)才有效。
于 2011-02-01T20:34:46.543 回答
7
我很惊讶没有人指出霍夫曼/香农编码......
于 2011-02-02T01:38:15.473 回答
5
于 2011-02-01T20:43:30.263 回答
2
贪心算法的一个真实例子是间隔调度。
例如,如果您想最大化可以使用会议室的客户数量,您可以使用间隔调度算法。
于 2013-02-24T22:42:29.053 回答
0
于 2011-02-01T20:22:04.007 回答
0
贪心算法有什么用?
我们使用贪心算法来获得最优解。但是所有问题都不能使用贪心算法来解决。
最优子结构属性和贪心选择属性 是关键要素。如果我们能够证明问题具有这些属性,那么我们就可以很好地为其开发贪心算法。
真实的例子?
- 活动调度问题
- 霍夫曼编码
- 硬币面额
- 单源最短路径问题(Dijkstra)
- 最小生成树(Prim 算法,Kruskal 算法)
- 分数背包问题。
几乎所有可以使用动态方法解决的问题都可以通过贪婪方法解决。
于 2019-07-12T03:23:23.707 回答