贪婪算法
教室调度问题：不同课程的开始和结束时间都不同，要如何安排这些棵，使得尽可能多的课被安排在某间教室？
- 1.先选最早结束的课，放在第一个
- 2.在剩下的课里挑离上一个课结束的时间最早的课，作为而且结束最早的课，放在第二个
- 3.重复2
所以，贪婪算法是每步采取最优的做法，即每步都选择局部最优解。这样就能找到全局最优解
背包问题:假设背包只能装固定重量的东西，要如何将将背包装的价值最高。存在问题：
- 如果每次按最贵的东西装，不能保证空间被完全利用，而且不能保证包内价值总和最大
所以，贪婪算法在这个问题上并不能获得最优解，但很接近，当我们只需要一个近似解的时候，就可以用这个方法，毕竟：
完美是优秀的敌人。
集合覆盖问题：让广播台能被50个州的人收到，如何选择最小的广播台，能覆盖到50个州，台之间集合存在覆盖现象。
- 对于这类问题，求精确解到时间开销极大，可以用贪婪算法，来计算近似解。
- 近似算法(approximation algorithm)：判断优劣的标准
- 速度多快
- 近似解和精确解的接近程度
问题求解
idea：用贪婪算法，来近似求解
- 选择一个包含最多未覆盖洲的电台；-->需要覆盖的州&这个电台能覆盖的州
- 重复上一步
具体做法：
- 建一个集合，包含所有需要覆盖的州
- 建一个散列表，代表每个电台对应覆盖的区域
- 遍历散列表，从里面选一个未覆盖区域最多的电台，州数量减去这个覆盖集合
- 重复遍历上一步，直到需要覆盖的州集合为空
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 in stations.items():
covered = states_needed & states #所有州和每个电台对应的州的交集==电台实际覆盖的州
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered #剩下还未被覆盖的州集合
final_stations.add(best_station)
print(repr(final_stations))
{'ktwo', 'kthree', 'kfive', 'kone'}
np完全问题
- 运行速度随元素数量激增，且效率降低
- 涉及组合的问题
- 不能将问题切分成小问题，必须考虑各种情况
- 问题涉及序列，集合
- 问题可以转换为集合覆盖问题和旅行商问题
推荐阅读
- <算法图解>
