Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照 ?
入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！
最后，愿我们都能在看不到的地方闪闪发光，一起加油进步
“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~
第八章：贪婪算法
- 8.1集合覆盖问题
- 8.2NP完全问题
- 8.2.1旅行商问题
- 8.2.2如何识别Np完全问题
- 8.3小结
- 二级目录
- 三级目录
- 最后的福利
8.1集合覆盖问题
假如你办了个广播节目，要让所有的州的听众都能听到。在每个广播台播出都需要收费，因此你要保证尽可能少的广播可以播出，每个广播台都覆盖特定区域，不同的广播台覆盖区域可能会重叠。
如何找出覆盖所有州的广播台集合呢？我们可以采用贪婪算法。
近似算法
贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
1.选出一个这样的广播台，即它覆盖了最多的未覆盖州。
2.重复第一步，直到覆盖了所有的州。
这是一种近似算法，判断近似算法优劣的标准如下：
1.准备工作
首先，创建一个列表，其中包含要覆盖的州。
states_needed= set(['mt','wa','or','id','nv','ut','ca','az'])#你传入一个数组，被转化为了集合。
还需要有可供选择的广播台清单，我选择使用散列表来表示它们：
stations={}stations['knoe']= 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()2.计算答案
正确的解可能有多个。你需要遍历所有的广播台，从中选择覆盖了最多的未覆盖州的广播台。我将这个广播台存储在best_station中。
best_station=None# states_covered=set()
states_covered是一个集合，包含该广播台覆盖的所有未覆盖的州。
最终代码：
# -*-coding:utf-8 -*-# @Author:到点了,心疼徐哥哥
# 奥利给干！！！
states_needed= set(['mt','wa','or','id','nv','ut',
'ca','az'])#你传入一个数组，被转化为了集合。
stations={}
stations['knoe']= 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'])
# print(stations.items())
final_stations=set()
best_station=None
# states_covered=set()
while states_needed:
best_station=None
states_covered=set()
for station,states_for_station in stations.items():
covered = states_needed & states_for_station # 取交集
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed-=states_covered
final_stations.add(best_station)
print(final_stations)
8.2NP完全问题
8.2.1旅行商问题
旅行商问题和集合覆盖问题都有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个，这两个问题都属于NP完全问题。
8.2.2如何识别Np完全问题
1.元素较少时算法的运行速度非常的快，但随着元素数量的增加，速度会变得非常慢。
2.涉及“所有组合”的问题通常都是NP问题。
3.不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
4.如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
5.如果问题涉及集合（如广播台集合）且难以解决，可能是NP完全问题。
6.如果问题可转化为集合覆盖问题或者旅行商问题，Nata肯定是NP完全问题。
8.3小结
1.贪婪算法寻找局部最优解，企图以这种方式获得全局最优解；
2.对于NP完全问题，还没有找到快速解决方案；
3.面临NP完全问题时，最佳的做法便是使用近似算法；
4.贪婪算法易于实现、运行速度快，是不错的近似算法。
二级目录
三级目录
最后的福利
☀️☀️☀️最后一点小福利带给大家：如果想快速上手python的小伙伴们，这个详细整理PPT可以迅速帮助大家打牢python基础，需要的小伙伴们可以下载一下 Python入门基础教程全套+小白速成+学不会来找我！
还有自制表白神器，需要自取：
Python表白神器，源码+解析+各种完美配置+浪漫新颖
好啦，这就是今天要给大家分享的全部内容了
如果你喜欢的话，就不要吝惜你的一键三连了~