贪心算法.

1. 应用场景-集合覆盖问题

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

2. 贪心算法介绍

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

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

2.1 思路分析

2.1.1 穷举法

列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算10个子集， 如图:

在广播台数量多的时候，时间成本高。

2.1.2 贪心算法

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

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

3. 代码实现

public class GreedyAlgorithm {
    public static void main(String[] args) {
        // 创建广播电台 放到Map
        HashMap<String, HashSet<String>> broadCasts = new HashMap<>();
        // 将各个电台放入到broadCasts中
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        broadCasts.put("K1", hashSet1);
        broadCasts.put("K2", hashSet2);
        broadCasts.put("K3", hashSet3);
        broadCasts.put("K4", hashSet4);
        broadCasts.put("K5", hashSet5);

        // 建立AllAreas来存放还未被覆盖的地区
        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");

        // 建立List来存放选择的电台集合
        ArrayList<String> selects = new ArrayList<>();

        // 定义一个临时的集合，来保存遍历每个电台中的时候，来存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集，例如k1电台和allAreas的交集.......
        HashSet<String> tempSet = new HashSet<>();

        // 定义maxKey来保存在一次遍历过程中，能够覆盖最多未覆盖地区对应的电台的key
        // 如果maxKey不为空，则会加入到selects里面
        String maxKey = null;

        while (allAreas.size() != 0) { // 只要allAreas不为0，就说明还没有覆盖到所有的地区
            // maxkey清空
            maxKey = null;

            // 开始遍历broadCasts，取出对应的key（电台）
            for (String key : broadCasts.keySet()) {
                // tempSet清空
                tempSet.clear();

                // 当前key能够覆盖的地区
                HashSet<String> areas = broadCasts.get(key);
                tempSet.addAll(areas);
                // 求出tempSet和allAreas的交集部分，这个交集会赋值给tempSet
                tempSet.retainAll(allAreas);


                // 如果当前交集的数量>0 或者交集的数量>maxKey对应的地区的数量
                if (tempSet.size() > 0 && (maxKey == null || (tempSet.size() > broadCasts.get(maxKey).size()))) {
                    maxKey = key;
                }
            }
            // 添加地区到selects里
            if (maxKey != null) {
                selects.add(maxKey);
                // 将maxKey指向的电台对应的地区从allAreas里删除
                allAreas.removeAll(broadCasts.get(maxKey));
            }


        }

        System.out.println(selects.toString());
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86