Java使用贪心算法解决电台覆盖问题(示例详解)

java使用贪心算法解决电台覆盖问题

代码实现

/**
* 贪心算法实现集合覆盖
*/
public class Demo {
   public static void main(String[] args) {
       // 创建电台和地区集合
       HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
       // 创建各个电台
       HashSet<String> k1 = new HashSet<>();
       k1.add("北京");
       k1.add("上海");
       k1.add("天津");
       HashSet<String> k2 = new HashSet<>();
       k2.add("广州");
       k2.add("北京");
       k2.add("深圳");
       HashSet<String> k3 = new HashSet<>();
       k3.add("成都");
       k3.add("上海");
       k3.add("杭州");
       HashSet<String> k4 = new HashSet<>();
       k4.add("上海");
       k4.add("天津");
       HashSet<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);
       // 建立各个地区的集合
       HashSet<String> allAreas = new HashSet<>();
       for (Map.Entry<String, HashSet<String>> entry : broadcasts.entrySet()) {
           HashSet<String> value = entry.getValue();
           allAreas.addAll(value);
       }
       // 创建选择的电台的集合
       ArrayList<String> broadSelect = new ArrayList<>();
       // 定义一个临时的集合
       HashSet<String> tempSet = new HashSet<>();
       // 定义一个指针，用于指向当前最优
       String maxKey = null;
       while (allAreas.size() > 0) {
           // 重置置空
           maxKey = null;
           // 遍历
           for (String key : broadcasts.keySet()) {
               // 重置置空
               tempSet.clear();
               HashSet<String> value = broadcasts.get(key);
               tempSet.addAll(value);
               // 求出temp和allAreas的交集
               tempSet.retainAll(allAreas);
               // 如果当前选择有覆盖地区
               if (tempSet.size() > 0 &&
                       // 此时，如果maxKey还没有指向就指向
                       (maxKey == null ||
                               // 如果maxKey已经有指向就比较谁最优解
                               (tempSet.size() > (broadcasts.get(maxKey).size())))) {
                   maxKey = key;
               }
           }
           if (maxKey != null) {
               // 将maxKey加入
               broadSelect.add(maxKey);
               // 并将allAreas去掉maxKey能覆盖的地区
               allAreas.removeAll(broadcasts.get(maxKey));
       // 打印结果
       System.out.println(broadSelect);
   }
}

补充：下面看下贪心算法解决集合覆盖问题

贪心算法：指在对问题求解时，在每一步都选择最好的选择，从而希望得到最好的结果。

解决集合覆盖问题

比如有5个广播台，每个广播台覆盖的区域不一样，怎么选择最少的广播台，让所有区域都覆盖上
如 k1广播台覆盖的区域有：北京、上海、天津
k2广播台覆盖的区域有：北京、山东、深圳
k3广播台覆盖的区域有：成都、上海、杭州
k4广播台覆盖的区域有：上海、天津
k5广播台覆盖的区域有：杭州、武汉

步骤：

1. 遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台
2. 将这个电台加入到集合中，想办法将该电台覆盖的地区下次比较时去掉
3. 重复第1步，直到覆盖了全部区域

图解

所有区域：{北京、上海、天津、山东、深圳、成都、杭州、武汉};
选择的电台：{}

第一步：遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台
k1(北京、上海、天津),k2(北京、山东、深圳),k3(成都、上海、杭州)在所有区域({北京、上海、天津、山东、深圳、成都、杭州、武汉})中覆盖的个数为3
k4(上海、天津),k5(杭州、武汉)在在所有区域({北京、上海、天津、山东、深圳、成都、杭州、武汉})中覆盖的个数为2
选择最大覆盖数k1加入到选择的电台{k1}，
第二步：将k1（北京、上海、天津）从所覆盖的区域从所有区域中移除，所有区域更新为：{山东、深圳、成都、杭州、武汉};

第三步：重复第一步，遍历所有广播
k1(北京、上海、天津)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为0
k2(北京、山东、深圳)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2
k3(成都、上海、杭州)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2
k4(上海、天津)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为0
k5(杭州、武汉)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2
选择最大覆盖数k2加入到选择的电台{k1,k2}
将k2(北京、山东、深圳)从所覆盖的区域从所有区域中移除，所有区域更新为：{成都、杭州、武汉};
k1(北京、上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k2(北京、山东、深圳)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k3(成都、上海、杭州)在所有区域({成都、杭州、武汉})中覆盖的个数为2
k4(上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k5(杭州、武汉)在所有区域({成都、杭州、武汉})中覆盖的个数为2

选择最大覆盖数k3加入到选择的电台{k1,k2,k3}
将k3(成都、上海、杭州)从所覆盖的区域从所有区域中移除，所有区域更新为：{武汉};
k1(北京、上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k2(北京、山东、深圳)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k3(成都、上海、杭州)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k4(上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k5(杭州、武汉)在所有区域({成都、杭州、武汉})中覆盖的个数为1

选择最大覆盖数k5加入到选择的电台{k1,k2,k3,k5}
完成

代码实现：

package azhong.greedy_algo;

import java.util.*;
/**
* 贪心算法
* 在对问题求解时，在每一步都选择最好的选择，从而希望得到最好的结果。
*/
public class GreedyAlgoDemo {
   public static void main(String[] args) {
       //每个电台覆盖的区域
       Map<String,HashSet<String>> allStations = initRadioStation();
       //需要覆盖的所有区域
       HashSet<String> allAreas = getAllAreas(allStations);
       //存放选择的电台
       List<String> selectedStations = new ArrayList<>();
       while (allAreas.size()>0) {
           //遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台
           int maxIndex=0;
           String maxK=null;
           HashSet<String> areaInMaxK=null;
           for (Map.Entry<String, HashSet<String>> entry : allStations.entrySet()) {
               final String k = entry.getKey();
               HashSet<String> values = entry.getValue();
               //当前电台在所有区域覆盖的个数
               int c = testIntersectionOfSet(values, allAreas);
               System.out.println(k + " 在所有区域覆盖的个数: " + c);
               if(c>maxIndex){
                   maxIndex=c;
                   maxK=k;
                   areaInMaxK=values;
               }
           }
           if(maxK!=null){
               //选择最大覆盖数k1加入到选择的电台{k1}，
               selectedStations.add(maxK);
               //将k1（北京、上海、天津）从所覆盖的区域从所有区域中移除，所有区域更新为：{山东、深圳、成都、杭州、武汉};
               allAreas.removeAll(areaInMaxK);
               //重置，进入下一次循环
               maxIndex=0;
               maxK=null;
               areaInMaxK=null;
               System.out.println("****************************");
       }
       System.out.println(selectedStations);
   }
   /**
    * 测试：求两个集合的交集
    * A{北京、上海、天津}
    * B{北京、上海、天津、山东、深圳、成都、杭州、武汉}
    * A.retainAll(B); 得到A{北京、上海、天津} 个数为3
    */
   private static int testIntersectionOfSet(HashSet A,HashSet B){
       //将存在于集合A中但不存在于集合B中的元素移除。
       A.retainAll(B);
       return A.size();
    * 初始化电台
    * k1广播台覆盖的区域有：北京、上海、天津
    * k2广播台覆盖的区域有：北京、山东、深圳
    * k3广播台覆盖的区域有：成都、上海、杭州
    * k4广播台覆盖的区域有：上海、天津
    * k5广播台覆盖的区域有：杭州、武汉
    * @return Map<String,HashSet<String>>类型电台集合
   private static Map<String,HashSet<String>> initRadioStation(){
       Map<String,HashSet<String>> allStations = new HashMap<String,HashSet<String>>();
       HashSet<String> k1 = new HashSet<>();
       k1.add("北京");
       k1.add("上海");
       k1.add("天津");
       HashSet<String> k2 = new HashSet<>();
       k2.add("北京");
       k2.add("山东");
       k2.add("深圳");
       HashSet<String> k3 = new HashSet<>();
       k3.add("成都");
       k3.add("上海");
       k3.add("杭州");
       HashSet<String> k4 = new HashSet<>();
       k4.add("上海");
       k4.add("天津");
       HashSet<String> k5 = new HashSet<>();
       k5.add("杭州");
       k5.add("武汉");
       allStations.put("k1",k1);
       allStations.put("k2",k2);
       allStations.put("k3",k3);
       allStations.put("k4",k4);
       allStations.put("k5",k5);
       return allStations;
   private static HashSet<String> getAllAreas(Map<String,HashSet<String>> allStations){
       HashSet<String> allAreas = new HashSet<>();
       Collection<HashSet<String>> stations = allStations.values();
       for(HashSet<String> station:stations){
           Iterator<String> areas = station.iterator();
           //操泥玛，写成了if
           while (areas.hasNext()){
               allAreas.add(areas.next());
       return allAreas;
}

 运行结果为：

k1 在所有区域覆盖的个数: 3
k2 在所有区域覆盖的个数: 3
k3 在所有区域覆盖的个数: 3
k4 在所有区域覆盖的个数: 2
k5 在所有区域覆盖的个数: 2
****************************
k1 在所有区域覆盖的个数: 0
k2 在所有区域覆盖的个数: 2
k3 在所有区域覆盖的个数: 2
k4 在所有区域覆盖的个数: 0
k5 在所有区域覆盖的个数: 2
****************************
k1 在所有区域覆盖的个数: 0
k2 在所有区域覆盖的个数: 0
k3 在所有区域覆盖的个数: 2
k4 在所有区域覆盖的个数: 0
k5 在所有区域覆盖的个数: 2
****************************
k1 在所有区域覆盖的个数: 0
k2 在所有区域覆盖的个数: 0
k3 在所有区域覆盖的个数: 0
k4 在所有区域覆盖的个数: 0
k5 在所有区域覆盖的个数: 1
****************************
[k1, k2, k3, k5]

来源：https://www.cnblogs.com/coderDreams/p/16188966.html