贪婪算法

教室调度问题：不同课程的开始和结束时间都不同，要如何安排这些棵，使得尽可能多的课被安排在某间教室？

• 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完全问题

• 运行速度随元素数量激增，且效率降低
• 涉及组合的问题
• 不能将问题切分成小问题，必须考虑各种情况
• 问题涉及序列，集合
• 问题可以转换为集合覆盖问题和旅行商问题

推荐阅读

• <算法图解>