️集合覆盖和NP完全问题️ 算法图解:第八章:贪婪算法

2021年9月2日 2点热度 0条评论 来源: 是Dream呀

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

第八章:贪婪算法

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

二级目录

三级目录

最后的福利

️️️最后一点小福利带给大家:如果想快速上手python的小伙伴们,这个详细整理PPT可以迅速帮助大家打牢python基础,需要的小伙伴们可以下载一下 Python入门基础教程全套+小白速成+学不会来找我!
还有自制表白神器,需要自取:
Python表白神器,源码+解析+各种完美配置+浪漫新颖

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

    原文作者:是Dream呀
    原文地址: https://blog.csdn.net/weixin_51390582/article/details/120065298
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。