[数据结构与算法]java实现贪婪算法求广播问题

#贪婪算法实现求广播问题

• 贪婪算法是每次找到最优解

• 但是最后的结果不一定是最优解 但是是最靠近最优解的
  假设我们有五个广播站分别是

• k1:北京 上海 天津

• k2: 广州 北京 深圳

• k3: 成都 上海 杭州

• k4:上海 天津

• k5:杭州 大连
  要求所有站点都覆盖, 使用穷举法可以解决，但是太费事。所以使用贪婪算法。

需要的变量

• allAreas 存放所有城市
• tempList 存放所查找城市公共的城市
• select 选中的广播站
• key 遍历需要的指针
• maxKey 所选择的指针

具体思路

• 先遍历广播站的城市 然后每次key存放到tempList中
• 将tempList跟allAreas关联 然后存放到tempList里面
• 然后经过判断将maxKey替换
• 将重复值最大的保存到select中
• 重复上面步骤

package com.lhl.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GreedyMain {
    public static void main(String[] args) {
        // 创建一个hashmap用于保存电台
        HashMap<String, HashSet<String>>broadcasts = new HashMap<String, HashSet<String>>();
        // 将各个电台放到broadcasts中
        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("大连");
        // 加入到 map中
        broadcasts.put("K1",hashSet1);
        broadcasts.put("K2",hashSet2);
        broadcasts.put("K3",hashSet3);
        broadcasts.put("K4",hashSet4);
        broadcasts.put("K5",hashSet5);
        // 创建一个allArea 存放所有区域
        HashSet<String>allAreas = new HashSet<String>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        // 创建ArrayList,存放选择的电台集合
        ArrayList<String>selects = new ArrayList<String>();
        // 定义一个临时的集合，在遍历过程中，存放遍历过程中电台覆盖的地区和当前还没有覆盖地区的交集
        HashSet<String>tempSet = new HashSet<String>();
        // 定义一个maxkey 保存在一次遍历过程中,能够覆盖最大未覆盖的地区电台key
        String maxKey = null;
        // 遍历
        while(allAreas.size()!=0){
            // 每次循环将maxKey重新赋值
            maxKey = null;
            for (String key:broadcasts.keySet()){
                // 每次进入for循环将selects清空
                tempSet.clear();
                // 拿到所有数据放入到临时的集合中
                tempSet.addAll(broadcasts.get(key));
                // 从集合中抽取出公共的部分
                tempSet.retainAll(allAreas);
                // 判断是否需要将key重新赋值  如果临时集合里的长度大于当前获取到的长度  那么就将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);
    }

}