0%

贪心算法

简介

贪心算法和动态规划算法一样,通常用来求解最优化问题

贪心算法的思想是每一步都选择局部最优解,很多时候这种方法能得到最优解,而且速度比动态规划快很多,也更简单。

原理

并没有确定的方法简单证明一个问题是否适用贪心算法。

贪心选择性质最优子结构是两个关键要素。

步骤

(1)将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解。

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

(3)证明做出贪心选择后剩余的子结构满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法