14.3.4 贪心法
贪心法每一步都选择当前看来最优的方案，并希望这些局部最优选择最终组成全局最优解。它的优点是简单高效，风险是局部最优并不总能推出全局最优。
贪心法成立的两个条件
| 条件 | 含义 |
|---|---|
| 最优子结构 | 全局最优解包含子问题的最优解 |
| 贪心选择性质 | 当前局部最优选择可以导向全局最优 |
如果只有最优子结构而没有贪心选择性质，往往要用动态规划。
典型例子
| 问题 | 贪心选择 |
|---|---|
| 哈夫曼树 | 每次合并最小的两个权值 |
| Kruskal | 每次选不成环的最小边 |
| Prim | 每次选连接集合内外的最小边 |
| Dijkstra | 每次确定当前距离最小的未确定顶点 |
贪心为什么快
贪心通常不回溯、不填完整状态表，只做当前决策，因此实现简洁、效率高。但它依赖问题性质，一旦性质不满足，就可能得到错误结果。
本节例题
下列问题中，最典型使用贪心策略的是：
自查清单
- 能否说明贪心法为什么不一定总正确？
- 能否区分最优子结构和贪心选择性质？
- 能否把哈夫曼树、Prim、Kruskal、Dijkstra 与贪心联系起来？