第八章 贪婪算法
目录
8.1教室调度问题
8.2背包问题
8.3集合覆盖问题
近似算法
8.4NP-Hard完全问题
8.4.1旅行商问题详解
8.4.2如何识别NP-hard完全问题
8.5小结
8.1教室调度问题
有很多门课，上课的时间和时长可能会交叉，那要怎么安排在某间教室的课程安排，且最大程度利用好这间教室呢？
---按课程时间选出不冲突的，比如9：00--10：00 10：00---11；00，而不是选9：00--10：00 9：20--10：30
这就是贪婪算法，每步选择最优，也就是选择局部最优解，并非在任何情况下都行之有效，但是易于实现---联想OMP算法也是贪婪算法，每次都找到投影最大值最大的那一列
8.2背包问题
有个小偷要偷东西，现在有如上图三种东西可以偷，但是他的包只能装35kg的东西，那他偷东西的时候要怎么选最优呢？
如果开始就选了最贵的，但是重量达到30，他就没法再装下大于5的东西了，那要怎么办呢？
说明：贪婪策略斌不能获得最优解--有些情况下，完美是优秀的敌人
8.3集合覆盖问题
1.现在有一档节目要在全美50个州播放，你要选择一些广播台，能够覆盖全美，且用尽量少的广播台
降低数据量后
假设有10个州需要覆盖，有5个广播台可以选择，设计算法进行广播台的选择
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,state in stations.items():
covered = states_needed & state
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
final_stations.add(best_station)
states_needed -= states_covered
print(final_stations)
程序具体讲解 贪婪算法近似集合覆盖问题的解 - lilong117194的博客 - 博客
http://blog.csdn.net/lilong117194/article/details/77657978
2.python里集合的概念，是没有重复的元素的
arr=[1,2,3,3,3,4]
set(arr)
set([1,2,3,4])
3.&交集 - 差集
并集 |
4.广度优先搜索算法BFS 狄克斯特拉算法 都是贪婪算法
5.贪婪算法和精确算法的运行时间比较
近似算法
贪婪算法是一种比较好的近似算法
8.4NP-Hard完全问题
1.没有快速算法解决的问题，所以退而求其次，近似算法
2.未解决集合覆盖问题，你必须计算每个可能的集合
8.4.1旅行商问题
商人要到各个城市去，要找一条最短路径，如果要找出最短路径得把所有可能的结果都列出来是n的阶乘问题n!
所以找到一条比较短的就不错了，从出发城市开始，选择下一个城市时，就选还没去最短的城市
8.4.2如何识别NP完全问题
学习识别NPhard完全问题，以免浪费时间去寻找解决答案
1.阶乘问题
2.需要找出所有的结果，涉及所有组合
3.元素较少时，算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢
4.不能将问题分为小问题，必须考虑所有情况，可能就是NPHard问题
5.如果问题涉及序列，如旅行商问题中的城市序列，难以解决，可能就是NPHard问题
6.如果问题转为集合覆盖问题或旅行商问题，肯定是NPHard问题
8.5小结
贪婪算法寻找局部最优解，企图以这种方式获得全局最优解
对于NPHard问题，还没有找到快速解决方案
面临NPHard问题，最佳做法是使用近似算法
贪婪算法易于实现，运行速度快，是不错的近似算法
