应用场景-集合覆盖问题
贪心算法可以解决很多场景的问题,这里以集合覆盖问题为例。
假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让所有的地区都可以接收到信号?
广播台 | 覆盖地区 |
---|---|
K1 | "北京", "上海", "天津" |
K2 | "广州", "北京", "深圳" |
K3 | "成都", "上海", "杭州" |
K4 | "上海", "天津" |
K5 | "杭州", "大连" |
例如:k4 中有上海、天津,那么我们选择 k1,里面包含了他们,还多了一个地区。
贪心算法介绍
**贪婪算法(贪心算法)(英语:greedy algorithm) **是指在对问题进行求解时,在 每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法
贪婪算法所得到的 结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果
思路分析
如何找出覆盖所有地区的广播台的集合呢,最容易想到的是使用穷举法实现,列出每个可能的广播台的集合,这被称为 幂集。假设总的有 n 个广播台,则广播台的组合总共有 2ⁿ -1
个,假设每秒可以计算 10 个子集, 如图:
广播台数量n | 子集总数2ⁿ | 需要的时间 |
---|---|---|
5 | 32 | 3.2秒 |
10 | 1024 | 102.4秒 |
32 | 4294967296 | 13.6年 |
100 | 1.26*100³º | 4x10²³年 |
由此可见:在进行组合的场景下,使用组合效率是很低的。(注意:子集总数2ⁿ 之所以少了一个减 1,是因为当n很大时,那个减1是可以忽略的)
那么贪心算法的思路如下:
广播台 | 覆盖地区 |
---|---|
K1 | "北京", "上海", "天津" |
K2 | "广州", "北京", "深圳" |
K3 | "成都", "上海", "杭州" |
K4 | "上海", "天津" |
K5 | "杭州", "大连" |
目前并没有算法可以快速计算得到准确的值, 使用贪婪算法,则可以得到非常接近的解,并且效率高。选择策略上,因为需要覆盖全部地区的最小集合,思路如下:
-
将所有需要覆盖的地区找出来(allAreas)
也就是所有电台中的覆盖地区去重后的列表
-
遍历所有的广播电台,找到一个 覆盖了最多未覆盖的地区 的电台
此电台可能包含一些已覆盖的地区,但是没有关系。
比如:k1 中有三个地区,在上面找出来的列表中去判定是否覆盖其中的地区,找到则 k1 为 覆盖了最多未覆盖的地区 的电台。(不懂没关系,往后看)
-
将这个电台加入到一个集合中(如 ArrayList),并想办法把该电台覆盖的地区在下次比较时去掉。
比如:前面 k1 为 覆盖了最多未覆盖的地区,把 k1 加到该集合中,并从把 k1 已经覆盖过的地区从 allAreas 中移除
-
重复第 2 步,直到覆盖了全部的地区
图解
给定的广播电台如下
广播台 | 覆盖地区 |
---|---|
K1 | "北京", "上海", "天津" |
K2 | "广州", "北京", "深圳" |
K3 | "成都", "上海", "杭州" |
K4 | "上海", "天津" |
K5 | "杭州", "大连" |
-
找出所有需要覆盖的地区
// 遍历所有电台的覆盖区域,然后去重,得到如下列表:共需要覆盖 8 个地区 allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
-
遍历广播电台列表:找出一个覆盖了最多地区的电台,重点:如何确定覆盖了最多的电台?
可以这样做:遍历广播台,计算每个电台中覆盖的地区在未覆盖地区列表中,覆盖了几个?
// 所有暂时还未覆盖的地区列表 allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
广播台 覆盖地区 覆盖数量(未覆盖地区的数量) K1 "北京", "上海", "天津" 3 K2 "广州", "北京", "深圳" 3 K3 "成都", "上海", "杭州" 3 K4 "上海", "天津" 2 K5 "杭州", "大连" 2 上图覆盖数量计算,例如:k1 覆盖地区有三个,这三个地区现在都在 未覆盖地区(allAreas),所以:k1 的覆盖数量则是 3
-
找到覆盖数量最大的电台(每一步的选择都选择最优)
// 未覆盖地区 allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
上第 2 步骤中,计算出的覆盖数量,k1 为最大的(k2 也是 3,但是不大于 k1 的覆盖数量),计为
maxKey
,将它添加到 选择列表中,表示该电台已被选择,同时将 k1 中覆盖地区,从 allAreas 列表中去掉,那么现在的情况就如下:// 已选电台 selects = {"k1"} // 未覆盖地区 allAreas = {广州", "深圳", "成都", "杭州", "大连"}
-
重新计算未被选择的电台的覆盖数量
// 已选电台 selects = {"k1"} // 未覆盖地区 allAreas = {广州", "深圳", "成都", "杭州", "大连"}
广播台 覆盖地区 覆盖数量(未覆盖地区的数量) K1 "北京", "上海", "天津" 0 K2 "广州", "北京", "深圳" 2 K3 "成都", "上海", "杭州" 2 K4 "上海", "天津" 0 K5 "杭州", "大连" 2 注意:因为 k1,已经被选择过,可以不重新对它计数,也可以重新计数,对性能影响不太大。
上图覆盖数量计算,例如:
- k1 覆盖地区有三个,这三个地区现在在 未覆盖地区(allAreas)中一个都没有,所以:k1 的覆盖数量则是 0
- k2 覆盖的确有三个,这三个地区现在在 未覆盖地区(allAreas)中有 2 个:广州、深圳,而北京已经被覆盖掉了(k1),所以:k2 的覆盖数量则是 2
-
找到覆盖数量最大的电台
当前状态:
// 已选择电台 selects = {"k1"} // 所有暂时还未覆盖的地区列表 allAreas = {广州", "深圳", "成都", "杭州", "大连"}
此时找到下一个覆盖数量最大的电台后的状态:
```java
// 已选择电台
selects = {"k1","K2"}
// 所有暂时还未覆盖的地区列表
allAreas = {"成都", "杭州", "大连"}
- ... 以此类推,最后完成状态如下
// 所有暂时还未覆盖的地区列表
selects = {"k1","K2","K3","K5"}
allAreas = {}
代码实现
/**
* 贪心算法
*/
public class GreedyAlgorithm {
/**
* 构建广播电台 与 覆盖的地区
*
* k: 电台
* v:覆盖的地区
*
*
* @return
*/
public Map<String, Set<String>> buildBroadcasts() {
Map<String, Set<String>> broadcasts = new HashMap<>();
Set<String> k1 = new HashSet<>();
k1.add("北京");
k1.add("上海");
k1.add("天津");
Set<String> k2 = new HashSet<>();
k2.add("广州");
k2.add("北京");
k2.add("深圳");
Set<String> k3 = new HashSet<>();
k3.add("成都");
k3.add("上海");
k3.add("杭州");
Set<String> k4 = new HashSet<>();
k4.add("上海");
k4.add("天津");
Set<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);
return broadcasts;
}
/**
* 贪心算法: 选择最少的电台,覆盖所有的地区
*
* @param broadcasts 电台信息
* @return 返回选择的电台列表
*/
public Set<String> greedy(Map<String, Set<String>> broadcasts) {
// 构建待覆盖的所有地区
Set<String> allAreas = new HashSet<>();
broadcasts.forEach((k, v) -> {
allAreas.addAll(v);
});
System.out.println("需要覆盖的地区:" + allAreas);
// 存放已选择的电台
Set<String> selects = new HashSet<>();
// 当所有需要覆盖的地区还有时,则可以继续选择
String maxKey = null; // 当次覆盖地区最多的电台
int maxKeyCoverNum = 0; // maxKey 覆盖的数量
Set<String> temp = new HashSet<>(); // 临时变量,用于计算电台中的覆盖地区:在剩余要覆盖地区中 覆盖的数量
while (!allAreas.isEmpty()) {
// 选择出当次还未选择中:覆盖地区最多的电台
for (String key : broadcasts.keySet()) {
Set<String> areas = broadcasts.get(key);
temp.addAll(areas);
//求出temp 和 allAreas 集合的交集, 交集会赋给 temp
temp.retainAll(allAreas);
// 如果:当前尝试选择的电台,覆盖数量比 maxKey 还大,则把它设置为 maxKey
if (temp.size() > 0 && temp.size() > maxKeyCoverNum) {
maxKey = key;
maxKeyCoverNum = temp.size();
}
//注意 要清空temp
temp.clear();
}
if (maxKey == null) {
continue;
}
// 循环完成后,找到了本轮的 maxKey
// 添加到已选择列表中,并且从 未覆盖列表 中删除已经覆盖过的地区
selects.add(maxKey);
allAreas.removeAll(broadcasts.get(maxKey));
// 清空临时变量,方便下次查找
maxKey = null;
maxKeyCoverNum = 0;
}
return selects;
}
@Test
public void fun() {
Map<String, Set<String>> broadcasts = buildBroadcasts();
System.out.println("电台列表" + broadcasts);
Set<String> greedy = greedy(broadcasts);
System.out.println("选择好的电台列表:" + greedy);
}
}
测试输出
电台列表{k1=[上海, 天津, 北京], k2=[广州, 北京, 深圳], k3=[成都, 上海, 杭州], k4=[上海, 天津], k5=[大连, 杭州]}
需要覆盖的地区:[成都, 上海, 广州, 天津, 大连, 杭州, 北京, 深圳]y
选择好的电台列表:[k1, k2, k3, k5]
贪婪算法注意事项
贪婪算法所得到的结果 不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果
比如上题的算法选出的是 K1, K2, K3, K5
,符合覆盖了全部的地区,但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区,如果 K2 的使用成本低于 K1 ,那么我们上题的 K1, K2, K3, K5 虽然是满足条件,但是并不是最优的.
但是笔者觉得上述举例并不是问题:如果加上成本:那么只要在 maxKey 覆盖数量相等的情况下,判定采用成本更低的 key,则可解决这个问题。
总的来说,有需求,必定有解决需求的办法。