贪婪算法————简单而可能非最优的问题解决策略。 是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。
第八章 贪婪算法
教室调度问题
一个使用贪婪算法的例子
如何在有限的时间内安排最多的课程？
- 选出最早结束的课；
- 选出在最早结束的课后开始并最早结束的课；
- 循环；
- 搞定。
体现了两点：
- 简单；
- 局部最优解。
集合覆盖问题
一个使用贪婪算法的例子
有多个含有不同元素的集合，求全覆盖目标区域的最小集合组合。
步骤：
循环选出当前覆盖未范围最大的集合，并在此过程中从目标范围中移除已覆盖范围。
python代码
# 目标覆盖范围
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
# 最终选择的集合
final_stations = set()
# 后续会逐渐减小目标范围，所以循环至空
while states_needed:
# 当前最优解
best_station = None
# 当前循环内集合最优覆盖范围
states_covered = set()
# 遍历所有集合
for station, states_for_station in stations.items():
# 当前遍历集合与待覆盖范围的交集
covered = states_needed & states_for_station
# 如果当前交集大于最优覆盖范围，则
if len(covered) > len(states_covered):
# 替换最优集合为当前遍历集合
best_station = station
# 更新当前循环内集合最优覆盖范围
states_covered = covered
# 将当次最优集合添加至最终结果
final_stations.add(best_station)
# 从目标覆盖范围中移除已覆盖范围
states_needed -= states_covered
# 打印结果
print(final_stations)
NP完全问题
Non-deterministic Polynomial
简单的说NP完全问题是难以解决的问题，大多需要先列出所有的解，再找到最小的那个，复杂度会随元素数量急剧增加。类旅行商问题和集合覆盖问题可能就是NP完全问题。
小结
- 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解
- 对于NP完全问题，还没有找到快速解决方案
- 面临NP完全问题时，最佳的做法是使用近似算法
- 贪婪算法易于实现，运行速度快，是不错的近似算法