贪婪算法的使用例子？

贪心算法的用途是什么？一个真实的例子？贪婪算法的使用例子？

来源

2011-02-01 Antonio Barra

http://en.wikipedia.org/wiki/Algorithm#By_design_paradigm – Axn 2011-02-01 20:54:54

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

来源

2011-02-01 20:22:04 Mikhail

任何地方的最佳解决方案是不可能的 - 或者非常非常难。

贪心算法需要在当前点的最佳解决方案，即使这不是最好的解决办法，如果你检查所有aternatives

来源

2011-02-01 20:22:40

旅行商最佳的解决方案是不可能的。事实上，有一些有效的算法可以为大量城市提供精确的解决方案。而且没有什么能够阻止贪婪算法从一个问题提供最优解决方案。我认为你的回答有点误导。贪婪算法甚至不用于旅行商问题。对于次优解决方案，您可以使用近似算法。 -1直到你改善这个。 – IVlad 2011-02-01 21:05:03

如果您在每一步前往下一个最近的未访问城市，可以使用TSP的贪婪算法。 – 2011-02-01 21:30:14

但你为什么要那样做？它可以很容易地给出最糟糕的**可能的解决方案。 TSP是**不使用贪婪算法的最佳例子。我仍然不同意你的第一条线 - 如果最佳解决方案非常困难，我认为最好说你会使用近似算法而不是贪婪算法。您可以使用贪婪算法来解决问题，您可以证明它们始终提供最佳解决方案。但无论如何，这是TSP的例子，我窃听了，所以我删除了-1。 – IVlad 2011-02-01 21:35:20

的一些问题是这样的，贪婪的解决方案实际上是最优的，有时他们设计那样。一个有趣的例子是，许多国家的硬币价值是这样的，即返回变化的贪婪方法（即总是返回最大可能的硬币直到完成为止）有效。

来源

2011-02-01 20:34:46