# 贪心算法

> 贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。

- ID: m06019
- 分类: technical
- 领域: 算法

## 定义

在每一步选择中都采取在当前状态下最好（局部最优）的选择，希望从而导致全局最优解。虽然不一定能得到全局最优，但在很多问题上高效且足够好。脚手架作用： 短视的生存策略。在环境变化极快、无法预测未来的情况下，长远规划往往是徒劳的。此时“贪心算法”（活在当下、抓住眼前的机会）反而是最佳的进化策略。

## 机制

贪心算法在每一步都选择当前看来最优的局部决策，期望由此得到全局最优。它高效但不保证最优，仅对满足贪心选择性质与最优子结构的问题成立。

## 练习

将问题分解为一系列决策并定义「最优局部选择」。证明局部最优能导向全局最优（或接受近似）。按序执行，不回溯。

## 脚手架用法

短视的生存策略。在环境变化极快、无法预测未来的情况下，长远规划往往是徒劳的。此时“贪心算法”（活在当下、抓住眼前的机会）反而是最佳的进化策略。

[阅读网页](https://thinkingmodels.site/entries/detail/m06019)