15

贪心算法有什么用？一个真实的例子？

4

10 回答 10

19

最小生成树 - Prim算法和Kruskal算法

最短路径计算 - Dijkstra 算法

更多：（分数背包问题，霍夫曼编码，最优合并，拓扑排序）。

于 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

贪心算法有什么用？

贪心算法在每个阶段选择最佳/最优解决方案。看看维基百科的文章

一个真实的例子？

最小生成树算法是贪心算法

著名的 Dijkstra 算法也是贪心算法

于 2011-02-01T20:43:30.263 回答
2

贪心算法的一个真实例子是间隔调度。

例如，如果您想最大化可以使用会议室的客户数量，您可以使用间隔调度算法。

于 2013-02-24T22:42:29.053 回答
0

贪心法的应用

Prim算法, Kruskal算法

于 2014-11-24T17:02:29.660 回答
0

http://en.wikipedia.org/wiki/Greedy_algorithm

于 2011-02-01T20:22:04.007 回答
0

在这里，我列出了一些贪婪算法及其潜在的现实世界用例。

Dijkstra 算法

  • IP路由首先找到Open shortest Path First。
  • 网络路由协议

在此处了解有关 Dijkstra 算法在现实世界中的应用的更多信息

Prim 的最小生成树算法

  • 聚类分析。

  • 实时人脸跟踪和验证（即在视频流中定位人脸）。

  • 计算机科学中避免网络周期的协议。

  • 基于熵的图像配准

  • 最大瓶颈路径。

  • 抖动（为数字录音添加白噪声以减少失真）。

旅行商问题

  • 无中间存储的作业车间调度

  • 对数据数组进行聚类

  • 车辆路线

图表 - 地图着色

  • 制定时间表/时间表

  • 数独

  • 移动无线电频率分配

您可以在本文中了解更多信息

Kruskal 的最小生成树算法

  • 电视网络组建

  • 旅游运营

背包问题

于 2020-03-05T11:31:49.353 回答
0

贪心算法有什么用？

我们使用贪心算法来获得最优解。但是所有问题都不能使用贪心算法来解决。

最优子结构属性和贪心选择属性 是关键要素。如果我们能够证明问题具有这些属性，那么我们就可以很好地为其开发贪心算法。

真实的例子？

  • 活动调度问题
  • 霍夫曼编码
  • 硬币面额
  • 单源最短路径问题（Dijkstra）
  • 最小生成树（Prim 算法，Kruskal 算法）
  • 分数背包问题。

几乎所有可以使用动态方法解决的问题都可以通过贪婪方法解决。

于 2019-07-12T03:23:23.707 回答