使用贪心算法解决集合覆盖问题

在《算法图解》里面有一个蛮有意思的小案例,背景是一个广播节目,要让全美的50个周的听众都能够听到,但是每个电台可能覆盖多个州,每在一个电台播出就需要一笔费用,所以就是从成本的角度来看,怎么尽可能在所有的州都播出,这是一个典型的集合覆盖的问题,而且在我们的生活中算是比较典型。

比如我们先缩小范围,指定5个州,那么50个州也是同样的算法。

states_need = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])  # 传入一个数组, 它被转换为集合

有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。

如何使用贪心算法呢,就是选择覆盖尽可能多的州的电台,然后逐步缩小范围。那么覆盖面广的州所对应的电台就优先被选中,依次类推。

程序的实现是指定了一个集合states_need,里面包含所有的州,每个电台对应的州是通过初始化的数组元素来实现的,按照一二三四五的顺序来命名,当然实际上这种元素的排列set不是按照数组名的顺序,在这个场景里是kfive,ktwo,kthree,kone,kfour

然后逐步缩小范围来收敛,里面比较特别的一点就是集合的运算,使用了 & ,得到的是交集,如果是并集是 |,差集是 -,

程序代码如下:

#!/usr/bin/env python
# coding:utf-8

states_need = 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"])

print(stations)
# 最终选择的广播台集合
final_stations = set()

while states_need:
    best_station = None
    states_covered = set()
    for station, states_for_station in stations.items():
        covered = states_need & states_for_station  # 求交集
        print("states_need:",states_need,"states_for_station:",states_for_station,"covered:",covered)
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
        states_need -= states_covered
        final_stations.add(best_station)
        print("states_needed:",states_need,"best_station:",best_station,"final_stations:",final_stations)
        print("---")

print("Final_stations:",final_stations)

为了方便调试和得到一个迭代的结果,我加了几处输出日志,工参考。

{'kfive': set(['ca', 'az']), 'ktwo': set(['mt', 'id', 'wa']), 'kthree': set(['ca', 'or', 'nv']), 'kone': set(['ut', 'id', 'nv']), 'kfour': set(['ut', 'nv'])}
('states_need:', set(['wa', 'ut', 'ca', 'id', 'mt', 'az', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 'covered:', set(['ca', 'az']))
('states_needed:', set(['wa', 'ut', 'id', 'mt', 'or', 'nv']), 'best_station:', 'kfive', 'final_stations:', set(['kfive']))
---
('states_need:', set(['wa', 'ut', 'id', 'mt', 'or', 'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set(['mt', 'id', 'wa']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 'nv']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut', 'nv']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut', 'nv']))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', 'ktwo', 'final_stations:', set(['ktwo', 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'az']), 'covered:', set([]))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', None, 'final_stations:', set(['ktwo', None, 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set([]))
('states_needed:', set(['ut', 'or', 'nv']), 'best_station:', None, 'final_stations:', set(['ktwo', None, 'kfive']))
---
('states_need:', set(['ut', 'or', 'nv']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set(['or', 'nv']))
('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut']))
('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'nv']), 'covered:', set(['ut']))
('states_needed:', set(['ut']), 'best_station:', 'kthree', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ca', 'az']), 'covered:', set([]))
('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['mt', 'id', 'wa']), 'covered:', set([]))
('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ca', 'or', 'nv']), 'covered:', set([]))
('states_needed:', set(['ut']), 'best_station:', None, 'final_stations:', set(['ktwo', 'kthree', None, 'kfive']))
---
('states_need:', set(['ut']), 'states_for_station:', set(['ut', 'id', 'nv']), 'covered:', set(['ut']))
('states_needed:', set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))
---
('states_need:', set([]), 'states_for_station:', set(['ut', 'nv']), 'covered:', set([]))
('states_needed:', set([]), 'best_station:', 'kone', 'final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))
---
('Final_stations:', set(['ktwo', 'kthree', None, 'kfive', 'kone']))

最后的结果是:ktwo,kthree,kfive,kone这四个电台。

当然贪心算法得到的不是精确的结果,即可能不是最优解,算是一种近似算法,能够基本得到的最优解,而且效率很高。

本文分享自微信公众号 - 杨建荣的学习笔记(jianrong-notes)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏wym

hdu1561(数组dp入门)

ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有...

20810
来自专栏Albert陈凯

数据结构与算法汇总

文章作者博客微信公共账号:hadoop123(微信号为:hadoop-123),分享hadoop技术内幕,hadoop最新技术进展,发布hadoop相关职位和求...

38550
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

38660
来自专栏落影的专栏

程序员进阶之算法练习(二十二)

前言 时间来到6月,又是一年高考时。 几年之前是坐在教室怀念高考,现在是上班敲着代码怀念学生时代。 正文 1、Lakes in Berland 题目链接 ...

50090
来自专栏程序员叨叨叨

6.5 Swizzle 操作符

可以使用Cg语言中的swizzle操作符(.)将一个向量的成员取出组成一个新的向量。swizzle操作符被GPU硬件高效支持。swizzle操作符后接x、y、z...

25250
来自专栏进击的程序猿

理解数据结构和算法背景数据本质算法的来源应用总结参考

在我看来应该是先有数据结构,只有当有了数据,我们才会考虑算法,针对不同的数据结构会有不同的算法。

13640
来自专栏aCloudDeveloper

算法导论第九章中位数和顺序统计量(选择问题)

  本章如果要归结成一个问题的话,可以归结为选择问题,比如要从一堆数中选择最大的数,或最小的数,或第几小/大的数等, 这样的问题看似很简单,似乎没有什么可研究的...

39470
来自专栏落影的专栏

程序员进阶之算法练习(三十)附基础教程

BAT常见的算法面试题解析:程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享,算法基础教程-。

25430
来自专栏章鱼的慢慢技术路

牛课堂算法直播题目

31780
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述...

34360

扫码关注云+社区

领取腾讯云代金券