算法——贪心算法（集合覆盖 -- Java代码实现）-蒲公英云

算法——贪心算法（集合覆盖 -- Java代码实现）

朱雀 2023-02-13 11:37 269阅读 0赞

贪心算法介绍

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

问题：使用最少的广播台覆盖全部的地区；

广播台	覆盖区域
A	北京、上海、天津
B	广州、上海、深圳
C	成都、上海、杭州
D	上海、天津
E	杭州、大连

思路分析:
➢ 如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现，列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2^n - 1个，

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

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

代码实现：可以直接发现上述问题的解决的是要选择ABCE四个广播台：

package greedy;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class GreedyAlgorithm { 
    public static void main(String[] args) { 
        // 创建广播台
        HashMap<String, HashSet<String>> broadcast = new HashMap<String, HashSet<String>>();
        HashSet<String> hashset1 = new HashSet<String>();
        hashset1.add("北京");
        hashset1.add("上海");
        hashset1.add("天津");
        HashSet<String> hashset2 = new HashSet<String>();
        hashset2.add("广州");
        hashset2.add("上海");
        hashset2.add("深圳");
        HashSet<String> hashset3 = new HashSet<String>();
        hashset3.add("成都");
        hashset3.add("上海");
        hashset3.add("杭州");
        HashSet<String> hashset4 = new HashSet<String>();
        hashset4.add("上海");
        hashset4.add("天津");
        HashSet<String> hashset5 = new HashSet<String>();
        hashset5.add("杭州");
        hashset5.add("大连");
        broadcast.put("A", hashset1);
        broadcast.put("B", hashset2);
        broadcast.put("C", hashset3);
        broadcast.put("D", hashset4);
        broadcast.put("E", hashset5);
        // 创建一个所有地区的
        HashSet<String> allAreas = new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        // 使用一个电台集合
        ArrayList<String> selects = new ArrayList<String>();
        // 临时变量,覆盖的地区和未覆盖地区的交集
        HashSet<String> temp = new HashSet<String>();
        // 定义一个在一次遍历过程中覆盖最多地区的广播台
        String maxKey = null;
        while (allAreas.size() != 0) { 
            // 遍历广播台
            for (String key : broadcast.keySet()) { 
                temp.clear();
                HashSet<String> areas = broadcast.get(key);
                temp.addAll(areas);
                // 取交集,之后交集再赋给temp
                temp.retainAll(allAreas);
                if (temp.size() > 0 && (maxKey == null || temp.size() > broadcast.get(maxKey).size())) { 
                    maxKey = key;
                }
            }
            if (maxKey != null) { 
                selects.add(maxKey);
                allAreas.removeAll(broadcast.get(maxKey));
            }
            maxKey = null;
        }
        System.out.println("结果：" + selects);
    }
}