算法图解》总结第 8 章:贪婪算法"/>
《算法图解》总结第 8 章:贪婪算法
仅用于记录学习,欢迎批评指正,大神勿喷
系列文章目录
《算法图解》总结第 1 章:二分查找、大O表示法;
《算法图解》总结第 2 章:数组和链表,选择排序;
《算法图解》总结第 3 章:while循环、递归、栈;
《算法图解》总结第 4 章:分而治之、快速排序;
《算法图解》总结第 5 章:散列表;
《算法图解》总结第 6 章:广度优先搜索;
《算法图解》总结第 7 章:狄克斯特拉算法;
《算法图解》总结第 8 章:贪婪算法
《算法图解》总结第 9 章:动态规划
《算法图解》总结第 10 章:K最近邻算法
《算法图解》总结第 11 章:十种算法简介
文章目录
- 系列文章目录
- 贪婪算法
- 补充知识
- 应用案例:集合覆盖问题
- 案例分析
- NP完全问题
- 定义
- 如何识别NP完全问题
贪婪算法
贪婪算法很简单:每步都采取最优的做法,用专业术语来说,就是每步都选择局部最优解,最终得到的就是全局最优解。(贪婪算法并非在任何情况下都行之有效,第7章乐谱换架子鼓就是一个典型例子。)
贪婪算法有时不能获得最优解,但是非常接近,有时你只需找到一个能够大致解决问题的算法,此时就可使用贪婪算法,这是一种近似算法。近似算法判断优劣的标准:
(1)速度有多快;
(2)得到的近似解与最优解的接近程度;
贪婪算法优点:易于实现,运行速度快,是不错的近似算法。
补充知识
并集、交集、差集
和数学中学的一样,这里作补充的是实现代码(Python),直接借用例子进行说明。
案例:
fruits = set(["avocado","tomato","banana"])
vegetables = set(["beets","carrots","tomato"])
并集:将集合合并
fruits | vegetables
输出结果:
{'avocado', 'banana', 'beets', 'carrots', 'tomato'}
交集:找出两个集合中都有的元素
fruits & vegetables
输出结果:
{'tomato'}
差集:从一个集合中剔除出现在另一个集合中的元素
fruits - vegetables
输出结果:
{'avocado', 'banana'}
应用案例:集合覆盖问题
案例:假设办个广播节目,要让全美50个州的听众都收听到,为支付较低的费用,尽量选择尽可能少的广播台播出。以下图为例,每个广播台能覆盖的特定区域,不同广播台的覆盖区域可能重叠。
将上图整理成表,显示如下:
案例分析
第一步:创建一个列表,包含要覆盖的州,要用集合来表示,集合类似于列表,但是集合中不能包含重复的元素
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循环
while states_needed:# 定义最初最好的广播台best_station = None# 定义一个集合,存储已经覆盖的州states_covered = set()''' for循环迭代每个广播台,并确定它是否是最佳,items()存储键值(广播台和相应的覆盖州)即每次仅能确定一个最佳的广播台'''for station,states_from_station in stations.items():# 需要覆盖的州和当前该广播台能覆盖的州的交集covered = states_needed & states_from_station # 如果当前广播台州交集的个数大于当前要覆盖的州if len(covered) > len(states_covered):# 就替换为最佳的广播台best_station = station# 替换已经覆盖的州states_covered = covered# for循环结束一次后,要从需要覆盖的州中减去已经覆盖过的州states_needed -= states_covered # 打印剩余需要覆盖的州print('states_needed:',states_needed)'''添加最佳的广播台,并开始下一轮新的while循环直至需要覆盖的州为空 (注:新一轮while循环中的best_station和states_covered不是for循环后的,还是while循环中最初定义的那些,因为for循环只是while循环中的一块,这个必须想明白)''' final_stations.add(best_station)
print(final_stations)
输出结果:
F:\anaconda\python.exe E:/lecode/tanlan.py # 代码存储位置,方便自己下次找到
states_needed: {'or', 'az', 'ca', 'wa', 'mt'}
states_needed: {'or', 'az', 'ca'}
states_needed: {'az'}
states_needed: set()
{'ktwo', 'kone', 'kthree', 'kfive'}
NP完全问题
定义
NP完全问题的简单定义是以难解著称的问题,如集合覆盖问题和旅行商问题,这两个问题的共同之处在于我们需要计算所有的解,并从中选择最小或者最短的那个,感兴趣的同学可以去 了解一下旅行商问题。这是一类很多聪明人都认为,根本不可能编写出可快速解决这些问题的算法。
如何识别NP完全问题
我们为什么会关注到NP完全问题的识别这个问题呢?若我们能识别出一个问题是NP完全问题,那么我们就可以用近似求解的方法去解决这个问题,而不用再去费力去求解完美解了。尽管我们没有办法判断某个问题是不是NP完全问题,但是还是有一些蛛丝马迹可引导我们做出判断:
(1)元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢;
(2)涉及“所有组合”的问题通常是NP完全问题;
(3)不能将问题分成小问题,必须考虑各种可能的情况,这可能是NP完全问题;
(4)如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题;
(5)如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题;
(6)如果问题可转换为集合覆盖问题或旅行商问题,那它肯定就是NP完全问题。
更多推荐
《算法图解》总结第 8 章:贪婪算法
发布评论