📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照😜😜😜
🏅🏅🏅CSDN Python领域新星创作者，大二在读，欢迎大家找我合作学习
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

@TOC

8.1集合覆盖问题

假如你办了个广播节目，要让所有的州的听众都能听到。在每个广播台播出都需要收费，因此你要保证尽可能少的广播可以播出，每个广播台都覆盖特定区域，不同的广播台覆盖区域可能会重叠。
如何找出覆盖所有州的广播台集合呢？我们可以采用贪婪算法。

近似算法

贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
1.选出一个这样的广播台，即它覆盖了最多的未覆盖州。
2.重复第一步，直到覆盖了所有的州。
这是一种近似算法，判断近似算法优劣的标准如下：

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.贪婪算法易于实现、运行速度快，是不错的近似算法。

好啦，这就是今天要给大家分享的全部内容了
如果你喜欢的话，就不要吝惜你的一键三连了~