贪心(Greed)算法:电台覆盖问题

Dear 丶 2023-02-28 01:27 172阅读 0赞

1,应用场景—集合覆盖问题

  • 假设存在下面需要付费的广播电台,以及广播电台可以覆盖的地区。如何选择最少的电台,能实现区域的全覆盖
    在这里插入图片描述

2,贪心算法介绍

  • 贪心算法(贪婪算法)是指在对问题进行求解时,在每一步的选择中都选择最优解,从而期望能够导致结果是最优解的算法
  • 贪心算法所得到的结果不一定是最优解,但是一定是相对近似最优解的结果

3,贪心算法最佳应用演示—集合覆盖问题

  1. 已知存在多少电台,及电台对应的覆盖城市集合;并且各个电台所覆盖城市存在部分重复,需要最少几部电台可实现全覆盖
  2. 首先汇总需要覆盖的城市,取各个电台对应城市的并集,作为汇总城市,并全部表示为未覆盖城市
  3. 然后遍历各个电台,统计各个电台在未覆盖的城市中可以覆盖几座城市
  4. 统计完成后,取覆盖城市最多的电台为最优解,即为先用电台,添加到选用集合;同时,从未覆盖城市集合中删除该电台覆盖的城市
  5. 再剩余未覆盖的城市中,重复第3和第4步,直到未覆盖城市数为0,即表示城市已经被全部覆盖
  6. 最终返回选用集合,表示最终选择的电台
  7. 注意:此处虽然在每一步取得了最优解,但是最终结果不一定是最优解,这也是贪心算法的特性

4,代码实现

  1. package com.self.datastructure.algorithm.greed;
  2. import org.apache.commons.lang3.StringUtils;
  3. import java.util.*;
  4. /** * 贪心算法_电台覆盖问题 * * 贪心算法是在每一次选择时力求最优解, 最终达到的结果贴近于最优解的算法 * * 对应存在多个电台, 每个电台可以覆盖多个不同的城市, 各个电台间覆盖城市有重合, 最少需要多少电台就可以实现全覆盖 * * 1, 首先汇总还未覆盖的全部城市, 第一次汇总即为全部城市 * * 2, 然后遍历各个电台, 统计该电台在未覆盖的城市中还可以覆盖几个城市 * * 3, 找出可覆盖最多城市的电台作为最优解, 进行电台记录, 作为选择之一 * * 4, 从未覆盖的城市集合中移除该电台可覆盖的城市 * * 5, 重复2,3,4步, 知道未覆盖城市为空 * * 6, 统计记录的电台, 即为最终解, 注意该最终解不一定为最优解 * @author PJ_ZHANG * @create 2020-07-08 17:36 **/
  5. public class Greed {
  6. public static void main(String[] args) {
  7. Map<String, Set<String>> redioMap = new HashMap<>(16);
  8. redioMap.put("K1", new HashSet<>(Arrays.asList("北京", "上海", "天津")));
  9. redioMap.put("K2", new HashSet<>(Arrays.asList("广州", "北京", "深圳")));
  10. redioMap.put("K3", new HashSet<>(Arrays.asList("成都", "上海", "杭州")));
  11. redioMap.put("K4", new HashSet<>(Arrays.asList("上海", "天津")));
  12. redioMap.put("K5", new HashSet<>(Arrays.asList("杭州", "大连")));
  13. System.out.println(greed(redioMap));
  14. }
  15. /** * 贪心算法 * @param redioMap 电台及对应城市 * @return 选择的电台集合 */
  16. private static Set<String> greed(Map<String, Set<String>> redioMap) {
  17. // 首先汇总还未覆盖的全部城市, 第一次汇总即为全部城市
  18. Set<String> lstTotalCities = getTotalCities(redioMap.values());
  19. // 统计选择的电台
  20. Set<String> lstRedio = new HashSet<>(10);
  21. // 统计当前批次匹配到城市最大的电台
  22. String maxKey = null;
  23. int maxCount = 0;
  24. // 进行处理
  25. for (;lstTotalCities.size() > 0;) {
  26. maxKey = null;
  27. maxCount = 0;
  28. // 遍历各个电台, 获取为匹配的城市数量
  29. for (Map.Entry<String, Set<String>> entry : redioMap.entrySet()) {
  30. Set<String> lstCities = entry.getValue();
  31. // 获取匹配的数量
  32. int currCount = getRetainCount(lstTotalCities, lstCities);
  33. // 如果当前匹配数量大于0, 说明匹配到, 有资格进行记录
  34. // 大于当前最大值, 则进行记录
  35. if (currCount > 0 && currCount > maxCount) {
  36. maxKey = entry.getKey();
  37. maxCount = currCount;
  38. }
  39. }
  40. // 一次处理完成后, 统计出需要记录的key进行记录, 并移除匹配的城市
  41. if (StringUtils.isNotEmpty(maxKey)) {
  42. lstRedio.add(maxKey);
  43. lstTotalCities.removeAll(redioMap.get(maxKey));
  44. }
  45. }
  46. return lstRedio;
  47. }
  48. /** * 获取未匹配城市的交集 * @param lstTotalCities * @param lstCities * @return */
  49. private static int getRetainCount(Set<String> lstTotalCities, Set<String> lstCities) {
  50. int count = 0;
  51. for (String city : lstCities) {
  52. if (lstTotalCities.contains(city)) {
  53. count++;
  54. }
  55. }
  56. return count;
  57. }
  58. /** * 获取全部城市 * @param values * @return */
  59. private static Set<String> getTotalCities(Collection<Set<String>> values) {
  60. Set<String> lstTotalCities = new HashSet<>(10);
  61. for (Set<String> lstCurrData : values) {
  62. lstTotalCities.addAll(lstCurrData);
  63. }
  64. return lstTotalCities;
  65. }
  66. }

发表评论

表情:
评论列表 (有 0 条评论,172人围观)

还没有评论,来说两句吧...

相关阅读

    相关 贪心算法-广播台覆盖问题

    我们先看一个问题: 假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有的地区都可以接收到信号 ![在这里插入图片描述][wate

    相关 区间覆盖贪心

    题目描述 给定N个闭区间\[ai,bi\]以及一个线段区间\[s,t\],请你选择尽量少的区间,将指定线段区间完全覆盖。 输出最少区间数,如果无法完全覆盖则输出-1。