算法图解 贪婪算法
🏷️ 《算法图解》
教室调度问题
假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。
| 课程 | 开始时间 | 结束时间 |
|---|---|---|
| 美术 | 09:00 AM | 10:00 AM |
| 英语 | 09:30 AM | 10:30 AM |
| 数学 | 10:00 AM | 11:00 AM |
| 计算机 | 10:30 AM | 11:30 AM |
| 音乐 | 11:00 AM | 12:00 AM |
算法：
选出结束最早的课，它就是在这间教室上的第一堂课。
接下来，必须选在在上一堂课结束后才开始的课。同样，选择结束最早的课。
重复上面的步骤
背包问题
假设你是个贪婪的小偷，背着可装 35 磅重东西的背包，在商场伺机盗窃各种可装入背包的商品。
贪婪策略：
盗窃可装入背包的最贵商品。
再盗窃可装入背包的最贵商品，以此类推。
但有可能不是最优解
旅行商问题的近似求解
随机选择出发城市。
选择还没有去的最近城市。
总结
贪婪算法寻找局部最优解，企图以这种方式获得全局最优解
对于 NP 完全问题，还没有找到快速解决方案
面临 NP 完全问题时，最佳的做法是找出近似算法
贪婪算法易于实现、运行速度快，是不错的近似算法