贪心算法之集合覆盖问题

谁践踏了优雅 2023-06-16 15:52 85阅读 0赞

# 贪心算法介绍 #

1.  贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
2.  贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

# 集合覆盖问题 #

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号？

## 算法思路 ##

1.  遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
2.  将这个电台加入到一个集合中(比如ArrayList), 把该电台覆盖的地区从未覆盖地区中去掉。
3.  重复第1步直到覆盖了全部的地区

## 代码实现 ##

def greedy_cover(stations: dict):
        """ 使用贪心算法解决集合覆盖问题：选择最少的广播台，让所有的地区都可以接收到信号 :param stations: :return: """
    
        # 创建一个set存放需要覆盖但还未覆盖的地区
        not_cover = set()
        for v in stations.values():
            for s in v:
                not_cover.add(s)
        selects = []  # 存放我们选择的电台
        while True:
            # 首先，选择覆盖了最多未覆盖地区的电台
            max_key = ''
            max_num = 0
            for k in stations.keys():
                intersection = not_cover.intersection(stations[k])
                if len(intersection) > max_num:
                    max_key = k
                    max_num = len(intersection)
            selects.append(max_key)
            # 然后，将选择电台覆盖的地区从not_cover中移除
            for e in stations[max_key]:
                if e in not_cover:
                    not_cover.remove(e)
            # 如果，not_cover未空即所有地区已覆盖，则可以结束算法
            if len(not_cover) == 0:
                break
    
        return selects
    
    
    if __name__ == '__main__':
        stations = { "k1": ["北京", "上海", "天津"], "k2": ["广州", "北京", "深圳"],
                    "k3": ["成都", "上海", "杭州"], "k4": ["上海", "天津"],
                    "k5": ["杭州", "大连"]}
        print(greedy_cover(stations))

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]  
欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114704923.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191127074219545.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ==,size_16,color_FFFFFF,t_70
[20200430114704923.jpg]: https://img-blog.csdnimg.cn/20200430114704923.jpg