应用场景-集合覆盖问题

贪心算法可以解决很多场景的问题，这里以集合覆盖问题为例。

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

例如：k4 中有上海、天津，那么我们选择 k1，里面包含了他们，还多了一个地区。

贪心算法介绍

**贪婪算法（贪心算法）（英语：greedy algorithm） **是指在对问题进行求解时，在 每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法

贪婪算法所得到的 结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

思路分析

如何找出覆盖所有地区的广播台的集合呢，最容易想到的是使用穷举法实现，列出每个可能的广播台的集合，这被称为 幂集。假设总的有 n 个广播台，则广播台的组合总共有 2ⁿ -1 个,假设每秒可以计算 10 个子集， 如图:

由此可见：在进行组合的场景下，使用组合效率是很低的。（注意：子集总数2ⁿ 之所以少了一个减 1，是因为当n很大时，那个减1是可以忽略的）

那么贪心算法的思路如下：

目前并没有算法可以快速计算得到准确的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合，思路如下:

1. 将所有需要覆盖的地区找出来（allAreas）

   也就是所有电台中的覆盖地区去重后的列表

2. 遍历所有的广播电台，找到一个 覆盖了最多未覆盖的地区 的电台

   此电台可能包含一些已覆盖的地区，但是没有关系。

   比如：k1 中有三个地区，在上面找出来的列表中去判定是否覆盖其中的地区，找到则 k1 为 覆盖了最多未覆盖的地区 的电台。（不懂没关系，往后看）

3. 将这个电台加入到一个集合中（如 ArrayList），并想办法把该电台覆盖的地区在下次比较时去掉。

   比如：前面 k1 为 覆盖了最多未覆盖的地区，把 k1 加到该集合中，并从把 k1 已经覆盖过的地区从 allAreas 中移除

4. 重复第 2 步，直到覆盖了全部的地区

图解

给定的广播电台如下

1. 找出所有需要覆盖的地区

   // 遍历所有电台的覆盖区域，然后去重，得到如下列表：共需要覆盖 8 个地区
   allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
   

2. 遍历广播电台列表：找出一个覆盖了最多地区的电台，重点：如何确定覆盖了最多的电台？

   可以这样做：遍历广播台，计算每个电台中覆盖的地区在未覆盖地区列表中，覆盖了几个？

   // 所有暂时还未覆盖的地区列表
   allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
   

   广播台	覆盖地区	覆盖数量（未覆盖地区的数量）
   K1	"北京", "上海", "天津"	3
   K2	"广州", "北京", "深圳"	3
   K3	"成都", "上海", "杭州"	3
   K4	"上海", "天津"	2
   K5	"杭州", "大连"	2

   上图覆盖数量计算，例如：k1 覆盖地区有三个，这三个地区现在都在 未覆盖地区（allAreas），所以：k1 的覆盖数量则是 3

3. 找到覆盖数量最大的电台（每一步的选择都选择最优）

   // 未覆盖地区
   allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
   

   上第 2 步骤中，计算出的覆盖数量，k1 为最大的（k2 也是 3，但是不大于 k1 的覆盖数量），计为 maxKey，将它添加到 选择列表中，表示该电台已被选择，同时将 k1 中覆盖地区，从 allAreas 列表中去掉，那么现在的情况就如下：

   // 已选电台
   selects =  {"k1"}
   // 未覆盖地区
   allAreas = {广州", "深圳", "成都", "杭州", "大连"}
   

4. 重新计算未被选择的电台的覆盖数量

   // 已选电台
   selects =  {"k1"}
   // 未覆盖地区
   allAreas = {广州", "深圳", "成都", "杭州", "大连"}
   

   广播台	覆盖地区	覆盖数量（未覆盖地区的数量）
   K1	"北京", "上海", "天津"	0
   K2	"广州", "北京", "深圳"	2
   K3	"成都", "上海", "杭州"	2
   K4	"上海", "天津"	0
   K5	"杭州", "大连"	2

   注意：因为 k1，已经被选择过，可以不重新对它计数，也可以重新计数，对性能影响不太大。

   上图覆盖数量计算，例如：

   • k1 覆盖地区有三个，这三个地区现在在 未覆盖地区（allAreas）中一个都没有，所以：k1 的覆盖数量则是 0
   • k2 覆盖的确有三个，这三个地区现在在 未覆盖地区（allAreas）中有 2 个：广州、深圳，而北京已经被覆盖掉了（k1），所以：k2 的覆盖数量则是 2

5. 找到覆盖数量最大的电台

   当前状态：

   // 已选择电台
   selects =  {"k1"}
   // 所有暂时还未覆盖的地区列表
   allAreas = {广州", "深圳", "成都", "杭州", "大连"}
   

此时找到下一个覆盖数量最大的电台后的状态：
   
   ```java
   // 已选择电台
   selects =  {"k1","K2"}
   // 所有暂时还未覆盖的地区列表
   allAreas = {"成都", "杭州", "大连"}

6. ... 以此类推，最后完成状态如下

// 所有暂时还未覆盖的地区列表
selects =  {"k1","K2","K3","K5"}
allAreas = {}

代码实现

/**
 * 贪心算法
 */
public class GreedyAlgorithm {

    /**
     * 构建广播电台 与 覆盖的地区
     * 
     * k: 电台
     * v：覆盖的地区
     * 
     *
     * @return
     */
    public Map<String, Set<String>> buildBroadcasts() {
        Map<String, Set<String>> broadcasts = new HashMap<>();
        Set<String> k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        Set<String> k2 = new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        Set<String> k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        Set<String> k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        Set<String> k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("大连");

        broadcasts.put("k1", k1);
        broadcasts.put("k2", k2);
        broadcasts.put("k3", k3);
        broadcasts.put("k4", k4);
        broadcasts.put("k5", k5);

        return broadcasts;
    }

    /**
     * 贪心算法: 选择最少的电台，覆盖所有的地区
     *
     * @param broadcasts 电台信息
     * @return 返回选择的电台列表
     */
    public Set<String> greedy(Map<String, Set<String>> broadcasts) {
        // 构建待覆盖的所有地区
        Set<String> allAreas = new HashSet<>();
        broadcasts.forEach((k, v) -> {
            allAreas.addAll(v);
        });
        System.out.println("需要覆盖的地区：" + allAreas);

        // 存放已选择的电台
        Set<String> selects = new HashSet<>();

        // 当所有需要覆盖的地区还有时，则可以继续选择

        String maxKey = null; // 当次覆盖地区最多的电台
        int maxKeyCoverNum = 0; // maxKey 覆盖的数量
        Set<String> temp = new HashSet<>();  // 临时变量，用于计算电台中的覆盖地区：在剩余要覆盖地区中  覆盖的数量
        while (!allAreas.isEmpty()) {
            // 选择出当次还未选择中：覆盖地区最多的电台
            for (String key : broadcasts.keySet()) {
                Set<String> areas = broadcasts.get(key);
                temp.addAll(areas);
                //求出temp 和   allAreas 集合的交集, 交集会赋给 temp
                temp.retainAll(allAreas);
                // 如果：当前尝试选择的电台，覆盖数量比 maxKey 还大，则把它设置为 maxKey
                if (temp.size() > 0 && temp.size() > maxKeyCoverNum) {
                    maxKey = key;
                    maxKeyCoverNum = temp.size();
                }
                //注意 要清空temp
                temp.clear();
            }
            if (maxKey == null) {
                continue;
            }
            // 循环完成后，找到了本轮的 maxKey
            // 添加到已选择列表中，并且从 未覆盖列表 中删除已经覆盖过的地区
            selects.add(maxKey);
            allAreas.removeAll(broadcasts.get(maxKey));
            // 清空临时变量，方便下次查找
            maxKey = null;
            maxKeyCoverNum = 0;
        }
        return selects;
    }

    @Test
    public void fun() {
        Map<String, Set<String>> broadcasts = buildBroadcasts();
        System.out.println("电台列表" + broadcasts);
        Set<String> greedy = greedy(broadcasts);
        System.out.println("选择好的电台列表：" + greedy);
    }
}

测试输出

电台列表{k1=[上海, 天津, 北京], k2=[广州, 北京, 深圳], k3=[成都, 上海, 杭州], k4=[上海, 天津], k5=[大连, 杭州]}
需要覆盖的地区：[成都, 上海, 广州, 天津, 大连, 杭州, 北京, 深圳]y
选择好的电台列表：[k1, k2, k3, k5]

贪婪算法注意事项

贪婪算法所得到的结果 不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

比如上题的算法选出的是 K1, K2, K3, K5，符合覆盖了全部的地区，但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果 K2 的使用成本低于 K1 ，那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的.

但是笔者觉得上述举例并不是问题：如果加上成本：那么只要在 maxKey 覆盖数量相等的情况下，判定采用成本更低的 key，则可解决这个问题。

总的来说，有需求，必定有解决需求的办法。