算法图解 贪婪算法

🏷️ 《算法图解》

教室调度问题

假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。

课程	开始时间	结束时间
美术	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

算法：

1. 选出结束最早的课，它就是在这间教室上的第一堂课。

2. 接下来，必须选在在上一堂课结束后才开始的课。同样，选择结束最早的课。

3. 重复上面的步骤

背包问题

假设你是个贪婪的小偷，背着可装 35 磅重东西的背包，在商场伺机盗窃各种可装入背包的商品。

贪婪策略：

1. 盗窃可装入背包的最贵商品。

2. 再盗窃可装入背包的最贵商品，以此类推。

但有可能不是最优解

旅行商问题的近似求解

1. 随机选择出发城市。

2. 选择还没有去的最近城市。

总结

• 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解

• 对于 NP 完全问题，还没有找到快速解决方案

• 面临 NP 完全问题时，最佳的做法是找出近似算法

• 贪婪算法易于实现、运行速度快，是不错的近似算法