贪心算法之集合覆盖问题

贪心算法介绍

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

集合覆盖问题

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

广播台	覆盖地区
K1	“北京”, “上海”, “天津”
K2	“广州”, “北京”, “深圳”
K3	“成都”, “上海”, “杭州”
K4	“上海”, “天津”
K5	“杭州”, “大连”

算法思路

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))