Java使用贪心算法解决电台覆盖问题(示例详解)

java使用贪心算法解决电台覆盖问题

代码实现

/**

* 贪心算法实现集合覆盖

*/

public class Demo {

public static void main(String[] args) {

// 创建电台和地区集合

HashMap> broadcasts = new HashMap<>();

// 创建各个电台

HashSet k1 = new HashSet<>();

k1.add("北京");

k1.add("上海");

k1.add("天津");

HashSet k2 = new HashSet<>();

k2.add("广州");

k2.add("北京");

k2.add("深圳");

HashSet k3 = new HashSet<>();

k3.add("成都");

k3.add("上海");

k3.add("杭州");

HashSet k4 = new HashSet<>();

k4.add("上海");

k4.add("天津");

HashSet 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);

// 建立各个地区的集合

HashSet allAreas = new HashSet<>();

for (Map.Entry> entry : broadcasts.entrySet()) {

HashSet value = entry.getValue();

allAreas.addAll(value);

}

// 创建选择的电台的集合

ArrayList broadSelect = new ArrayList<>();

// 定义一个临时的集合

HashSet tempSet = new HashSet<>();

// 定义一个指针，用于指向当前最优

String maxKey = null;

while (allAreas.size() > 0) {

// 重置置空

maxKey = null;

// 遍历

for (String key : broadcasts.keySet()) {

// 重置置空

tempSet.clear();

HashSet value = broadcasts.get(key);

tempSet.addAll(value);

// 求出temp和allAreas的交集

tempSet.retainAll(allAreas);

// 如果当前选择有覆盖地区

if (tempSet.size() > 0 &&

// 此时，如果maxKey还没有指向就指向

(maxKey == null ||

// 如果maxKey已经有指向就比较谁最优解

(tempSet.size() > (broadcasts.get(maxKey).size())))) {

maxKey = key;

}

}

if (maxKey != null) {

// 将maxKey加入

broadSelect.add(maxKey);

// 并将allAreas去掉maxKey能覆盖的地区

allAreas.removeAll(broadcasts.get(maxKey));

// 打印结果

System.out.println(broadSelect);

}

}

补充：下面看下贪心算法解决集合覆盖问题

贪心算法：指在对问题求解时，在每一步都选择最好的选择，从而希望得到最好的结果。

解决集合覆盖问题

比如有5个广播台，每个广播台覆盖的区域不一样，怎么选择最少的广播台，让所有区域都覆盖上如 k1广播台覆盖的区域有：北京、上海、天津k2广播台覆盖的区域有：北京、山东、深圳k3广播台覆盖的区域有：成都、上海、杭州k4广播台覆盖的区域有：上海、天津k5广播台覆盖的区域有：杭州、武汉

步骤：

1. 遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台2. 将这个电台加入到集合中，想办法将该电台覆盖的地区下次比较时去掉3. 重复第1步，直到覆盖了全部区域

图解

所有区域：{北京、上海、天津、山东、深圳、成都、杭州、武汉};选择的电台：{}

第一步：遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台k1(北京、上海、天津),k2(北京、山东、深圳),k3(成都、上海、杭州)在所有区域({北京、上海、天津、山东、深圳、成都、杭州、武汉})中覆盖的个数为3k4(上海、天津),k5(杭州、武汉)在在所有区域({北京、上海、天津、山东、深圳、成都、杭州、武汉})中覆盖的个数为2选择最大覆盖数k1加入到选择的电台{k1}，第二步：将k1（北京、上海、天津）从所覆盖的区域从所有区域中移除，所有区域更新为：{山东、深圳、成都、杭州、武汉};

第三步：重复第一步，遍历所有广播k1(北京、上海、天津)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为0k2(北京、山东、深圳)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2k3(成都、上海、杭州)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2k4(上海、天津)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为0k5(杭州、武汉)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2选择最大覆盖数k2加入到选择的电台{k1,k2}将k2(北京、山东、深圳)从所覆盖的区域从所有区域中移除，所有区域更新为：{成都、杭州、武汉};k1(北京、上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0k2(北京、山东、深圳)在所有区域({成都、杭州、武汉})中覆盖的个数为0k3(成都、上海、杭州)在所有区域({成都、杭州、武汉})中覆盖的个数为2k4(上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0k5(杭州、武汉)在所有区域({成都、杭州、武汉})中覆盖的个数为2

选择最大覆盖数k3加入到选择的电台{k1,k2,k3}将k3(成都、上海、杭州)从所覆盖的区域从所有区域中移除，所有区域更新为：{武汉};k1(北京、上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0k2(北京、山东、深圳)在所有区域({成都、杭州、武汉})中覆盖的个数为0k3(成都、上海、杭州)在所有区域({成都、杭州、武汉})中覆盖的个数为0k4(上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0k5(杭州、武汉)在所有区域({成都、杭州、武汉})中覆盖的个数为1

选择最大覆盖数k5加入到选择的电台{k1,k2,k3,k5}完成

代码实现：

package azhong.greedy_algo;

import java.util.*;

/**

* 贪心算法

* 在对问题求解时，在每一步都选择最好的选择，从而希望得到最好的结果。

*/

public class GreedyAlgoDemo {

public static void main(String[] args) {

lLEsoF //每个电台覆盖的区域

Map> allStations = initRadioStation();

//需要覆盖的所有区域

HashSet allAreas = getAllAreas(allStations);

//存放选择的电台

List selectedStations = new ArrayList<>();

while (allAreas.size()>0) {

//遍历所有广播台，找到了个覆盖了最多未覆盖的地区的电台

int maxIndex=0;

String maxK=null;

HashSet areaInMaxK=null;

lLEsoF for (Map.Entry> entry : allStations.entrySet()) {

final String k = entry.getKey();

HashSet values = entry.getValue();

//当前电台在所有区域覆盖的个数

int c = testIntersectionOfSet(values, allAreas);

System.out.println(k + " 在所有区域覆盖的个数: " + c);

if(c>maxIndex){

maxIndex=c;

maxK=k;

areaInMaxK=values;

}

}

if(maxK!=null){

//选择最大覆盖数k1加入到选择的电台{k1}，

selectedStations.add(maxK);

//将k1（北京、上海、天津）从所覆盖的区域从所有区域中移除，所有区域更新为：{山东、深圳、成都、杭州、武汉};

allAreas.removeAll(areaInMaxK);

//重置，进入下一次循环

maxIndex=0;

maxK=null;

areaInMaxK=null;

System.out.println("****************************");

}

System.out.println(selectedStations);

}

/**

* 测试：求两个集合的交集

* A{北京、上海、天津}

* B{北京、上海、天津、山东、深圳、成都、杭州、武汉}

* A.retainAll(B); 得到A{北京、上海、天津} 个数为3

*/

private static int testIntersectionOfSet(HashSet A,HashSet B){

//将存在于集合A中但不存在于集合B中的元素移除。

A.retainAll(B);

return A.size();

* 初始化电台

* k1广播台覆盖的区域有：北京、上海、天津

* k2广播台覆盖的区域有：北京、山东、深圳

* k3广播台覆盖的区域有：成都、上海、杭州

* k4广播台覆盖的区域有：上海、天津

* k5广播台覆盖的区域有：杭州、武汉

* @return Map>类型电台集合

private static Map> initRadioStation(){

Map> allStations = new HashMap>();

HashSet k1 = new HashSet<>();

k1.add("北京");

k1.add("上海");

k1.add("天津");

HashSet k2 = new HashSet<>();

k2.add("北京");

k2.add("山东");

k2.add("深圳");

HashSet k3 = new HashSet<>();

k3.add("成都");

k3.add("上海");

k3.add("杭州");

HashSet k4 = new HashSet<>();

k4.add("上海");

k4.add("天津");

HashSet k5 = new HashSet<>();

k5.add("杭州");

k5.add("武汉");

allStations.put("k1",k1);

allStations.put("k2",k2);

allStations.put("k3",k3);

allStations.put("k4",k4);

allStations.put("k5",k5);

return allStations;

private static HashSet getAllAreas(Map> allStations){

Hashhttp://Set allAreas = new HashSet<>();

Collection> stations = allStations.values();

for(HashSet station:stations){

Iterator areas = station.iterator();

//操泥玛，写成了if

while (areas.hasNext()){

allAreas.add(areas.next());

return allAreas;

}

运行结果为：

k1 在所有区域覆盖的个数: 3k2 在所有区域覆盖的个数: 3k3 在所有区域覆盖的个数: 3k4 在所有区域覆盖的个数: 2k5 在所有区域覆盖的个数: 2****************************k1 在所有区域覆盖的个数: 0k2 在所有区域覆盖的个数: 2k3 在所有区域覆盖的个数: 2k4 在所有区域覆盖的个数: 0k5 在所有区域覆盖的个数: 2****************************k1 在所有区域覆盖的个数: 0k2 在所有区域覆盖的个数: 0k3 在所有区域覆盖的个数: 2k4 在所有区域覆盖的个数: 0k5 在所有区域覆盖的个数: 2****************************k1 在所有区域覆盖的个数: 0k2 在所有区域覆盖的个数: 0k3 在所有区域覆盖的个数: 0k4 在所有区域覆盖的个数: 0k5 在所有区域覆盖的个数: 1****************************[k1, k2, k3, k5]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。