[toc]
贪心算法
1. 应用场景-集合覆盖问题
假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有的地区都可以接收到信号;
2. 贪心算法介绍
- 贪婪算法(贪心算法)是指在对问题进行求解时,
在每一步选择中都采取最好或者最优( 即最有利) 的选择,从而希望能够导致结果是最好或者最优的算法。
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果
。
3. 贪心算法最佳应用-集合覆盖
思路分析:
- 如何找出覆盖所有地区的广播台的集合呢,使用
穷举法
实现,列出每个可能的广播台的集合,这被称为幂集
。假设总的有 n 个广播台,则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算 10 个子集
, 如图:
使用贪婪算法,效率高:
- 目前并没有算法可以快速计算得到准备的值, 使用贪婪算法,则可以得到非常接近的解,并且效率高。选择策略上,因为需要覆盖全部地区的最小集合。
- 遍历所有的广播电台,
找到一个覆盖了最多未覆盖的地区的电台
(此电台可能包含一些已覆盖的地区,但没有关系)
将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
- 重复第 1 步 直到覆盖了全部的地区。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
| package cn.itbuild.greedy;
import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set;
public class GreedyAlgorithm {
public static void main(String[] args) { Map<String, HashSet<String>> broadcasts = 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("大连");
broadcasts.put("K1", hashSet1); broadcasts.put("K2", hashSet2); broadcasts.put("K3", hashSet3); broadcasts.put("K4", hashSet4); broadcasts.put("K5", hashSet5); List<String> greedyResult = getGreedyResult(broadcasts); for(String result : greedyResult) { System.out.print(result + " "); } }
public static List<String> getGreedyResult(Map<String,HashSet<String>> map){ HashSet<String> allAreas = new HashSet<String>(); Set<String> keySet = map.keySet(); for(String key: keySet) { HashSet<String> hashSet = map.get(key); for(String value: hashSet) { allAreas.add(value); } } List<String> selects = new ArrayList<String>(); HashSet<String> tempSet = new HashSet<String>(); String maxKey = null; while(allAreas.size() != 0) { maxKey = null; for(String key:keySet) { tempSet.clear(); HashSet<String> areas = map.get(key); tempSet.addAll(areas); tempSet.retainAll(allAreas); if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > map.get(maxKey).size())) { maxKey = key; } } if (maxKey != null) { selects.add(maxKey); allAreas.removeAll(map.get(maxKey)); } } return selects; } }
|
4. 贪心算法注意事项和细节
- 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。
比如上题的算法选出的是 K1, K2, K3, K5,符合覆盖了全部的地区。
但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区,如果 K2 的使用成本低于 K1,那么我们上题的 K1, K2, K3,K5 虽然是满足条件,但是并不是最优的。
☆