《算法图解》第八章 贪婪算法

xiaoxiao2021-02-28  4

第八章 贪婪算法

目录

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问题,最佳做法是使用近似算法 贪婪算法易于实现,运行速度快,是不错的近似算法
转载请注明原文地址: https://www.6miu.com/read-1600171.html

最新回复(0)