数据结构与算法——贪心算法

时间:2024-02-20 22:32:36

应用场景-集合覆盖问题

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

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

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

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

贪心算法介绍

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

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

思路分析

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

广播台数量n 子集总数2ⁿ 需要的时间
5 32 3.2秒
10 1024 102.4秒
32 4294967296 13.6年
100 1.26*100³º 4x10²³年

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

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

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

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

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

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

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

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

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

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

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

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

图解

给定的广播电台如下

广播台 覆盖地区
K1 "北京", "上海", "天津"
K2 "广州", "北京", "深圳"
K3 "成都", "上海", "杭州"
K4 "上海", "天津"
K5 "杭州", "大连"
  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 = {"成都", "杭州", "大连"}
  1. ... 以此类推,最后完成状态如下
// 所有暂时还未覆盖的地区列表
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,则可解决这个问题。

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