《算法导论》第16章 贪心算法.pptx

贪心算法

贪心算法

求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化

问题，使用动态规划算法来求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法。贪心算法

（greedyalgorithm）就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做

出局部最优的选择，寄希望这样的选择能导致全局最优解。

贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。贪心方法是一种强有力的算法

设计方法，可以很好地解决很多问题。

贪心算法原理

贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点，它做出在当时看来最佳的选择。

这种启发式策略并不保证总能找到最优解，但对有些问题确实有效。

我们可以按照如下步骤设计贪心算法：

1、将最优化问题转化成这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。

2、证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。

3、证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优

解，这样就得到了最优子结构。

我们将使用这种设计方法，但我们应该知道，在每个贪心算法之下，几乎总有一个更繁琐的动态规

划算法。

我们如何证明一个贪心算法是否能求解一个最优化问题呢？并没有适合所有情况的方法，但贪心选

择性质和最优子结构是两个关键要素。如果我们能够证明问题具有这些性质，就向贪心算法迈出了重要

一步。

贪心选择性质

最优子结构

一个经典最优化问题的两个变形

贪心对动态规划

最小生成树

Prim算法

Prim算法图示

谢谢！