栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构(Java)贪心算法(分配广播站)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构(Java)贪心算法(分配广播站)

一、贪心算法介绍 1) 贪婪算法 ( 贪心算法 ) 是指在对问题进行求解时,在每一步选择中都采取最好或者最优 ( 即最有利 ) 的选择,从而希望能够导致结果是最好或者最优的算法 2) 贪婪算法所得到的结果 不一定是最优的结果 ( 有时候会是最优解 ) ,但是都是相对近似 ( 接近 ) 最优解的结果  二、贪心算法最佳应用-集合覆盖 1) 假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台 ,让所有的地区都可以接收到信号

广播台

覆盖地区

K1

"北京", "上海", "天津"

K2

"广州", "北京", "深圳"

K3

"成都", "上海", "杭州"

K4

"上海", "天津"

K5

"杭州", "大连"

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

       

广播台数量n

子集总数2ⁿ

需要的时间

5

32

3.2秒

10

1024

102.4秒

32

4294967296

13.6年

100

1.26*100³º

4x10²³年

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

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

1.一些静态变量的初始化

class greedy {
    static List coverageAreaOfFM100 = new ArrayList<>();
    static List coverageAreaOfFM101 = new ArrayList<>();
    static List coverageAreaOfFM102 = new ArrayList<>();
    static List coverageAreaOfFM103 = new ArrayList<>();
    static List coverageAreaOfFM104 = new ArrayList<>();
    static List allArea = new ArrayList<>();//存储待覆盖城市

    static Map> broadcastTable = new HashMap<>();
        //存放电台信息(名字+可覆盖区域)

    static int count=0;//记录第几次选择

... ...

 2.初始化城市、电台信息

  public static void init() {
        allArea.add("北京");
        allArea.add("上海");
        allArea.add("天津");
        allArea.add("广州");
        allArea.add("深圳");
        allArea.add("成都");
        allArea.add("杭州");
        allArea.add("大连");

        coverageAreaOfFM100.add("北京");
        coverageAreaOfFM100.add("上海");
        coverageAreaOfFM100.add("天津");

        coverageAreaOfFM101.add("广州");
        coverageAreaOfFM101.add("北京");
        coverageAreaOfFM101.add("深圳");

        coverageAreaOfFM102.add("成都");
        coverageAreaOfFM102.add("上海");
        coverageAreaOfFM102.add("杭州");

        coverageAreaOfFM103.add("上海");
        coverageAreaOfFM103.add("天津");

        coverageAreaOfFM104.add("杭州");
        coverageAreaOfFM104.add("大连");

        broadcastTable.put("FM100", coverageAreaOfFM100);
        broadcastTable.put("FM101", coverageAreaOfFM101);
        broadcastTable.put("FM102", coverageAreaOfFM102);
        broadcastTable.put("FM103", coverageAreaOfFM103);
        broadcastTable.put("FM104", coverageAreaOfFM104);
    }

3.打印电台信息

 public static void printBroadcastInformation() {
        System.out.println("城市列表:");
        System.out.println("-----------------------------------------");
        for (String e : allArea) System.out.print(" "+e);
        System.out.println("n");
        System.out.println("广播台        覆盖地区");
        System.out.println("---------------------");
        for (Map.Entry> entry : broadcastTable.entrySet()) {
            System.out.println(entry.getKey() + "       " + entry.getValue());
        }
    }

 4.计算每个广播站当前可以覆盖的地区数量

 //计算每个广播站当前可以覆盖的地区数量
    public static Map countAreaCouldCover() {
        List temp;
        Map counts = new HashMap<>();
        for (Map.Entry> entry : broadcastTable.entrySet()) {

    //用广播站可覆盖城市与当前剩余城市做交集,得到的就是当前该广播站可覆盖的区域
            temp = entry.getValue();
            temp.retainAll(allArea);
            counts.put(entry.getKey(),temp.size());
        }
        return counts;
    }

5.得到当前覆盖地区数量最大的广播台名字

//计算当前覆盖地区数量最大的广播台
    public static String maxKey( Map countCovers) {
        int maxCovers=0;
        String maxKey="";
    //利用 4 中得到的 map 很容易求出最大可覆盖区域对应的电台名字
        for (Map.Entry entry : countCovers.entrySet()){
               if(entry.getValue()>maxCovers) {
                   maxKey=entry.getKey();
                   maxCovers= entry.getValue();
               }
        }
        return maxKey;
    }

 6.主程序

 public static void broadcastCoverage() {
        List selection=new ArrayList<>();
        // 1.初始化
        init();
        // 2.查看初始信息
        printBroadcastInformation();
        // 3.选择电台
        while (!allArea.isEmpty()){
            count++;
            //先把广播台名字加入结果中
            selection.add(maxKey(countAreaCouldCover()));
            System.out.println("-----------------------------------------");
            System.out.println("第"+count+"次选择: ");
            System.out.print("选择的电台:"+maxKey(countAreaCouldCover()));
            System.out.println(" , 选择的城市:"+broadcastTable.get(maxKey(countAreaCouldCover())));
            //再把对应的城市删除掉
            allArea.removeAll(broadcastTable.get(maxKey(countAreaCouldCover())));

            System.out.println("剩下的城市:");
            for (String e : allArea) System.out.print(e + " ");
            System.out.println();
        }
        System.out.print("结果为:");
        for(String e:selection) System.out.print(e+" ");
    }
城市列表:
-----------------------------------------
 北京 上海 天津 广州 深圳 成都 杭州 大连

广播台        覆盖地区
---------------------
FM104       [杭州, 大连]
FM102       [成都, 上海, 杭州]
FM103       [上海, 天津]
FM100       [北京, 上海, 天津]
FM101       [广州, 北京, 深圳]
-----------------------------------------
第1次选择: 
选择的电台:FM102 , 选择的城市:[成都, 上海, 杭州]
剩下的城市:
北京 天津 广州 深圳 大连 
-----------------------------------------
第2次选择: 
选择的电台:FM101 , 选择的城市:[广州, 北京, 深圳]
剩下的城市:
天津 大连 
-----------------------------------------
第3次选择: 
选择的电台:FM104 , 选择的城市:[大连]
剩下的城市:
天津 
-----------------------------------------
第4次选择: 
选择的电台:FM103 , 选择的城市:[天津]
剩下的城市:

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

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950891.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号