一、贪心算法介绍 1) 贪婪算法 ( 贪心算法 ) 是指在对问题进行求解时,在每一步选择中都采取最好或者最优 ( 即最有利 ) 的选择,从而希望能够导致结果是最好或者最优的算法 2) 贪婪算法所得到的结果 不一定是最优的结果 ( 有时候会是最优解 ) ,但是都是相对近似 ( 接近 ) 最优解的结果 二、贪心算法最佳应用-集合覆盖 1) 假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台 ,让所有的地区都可以接收到信号
| 广播台 | 覆盖地区 |
| K1 | "北京", "上海", "天津" |
| K2 | "广州", "北京", "深圳" |
| K3 | "成都", "上海", "杭州" |
| K4 | "上海", "天津" |
| K5 | "杭州", "大连" |
| 广播台数量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注: 贪婪算法所得到的结果不一定是 最优的结果 ( 有时候会是最优解 ) ,但是都是 相对近似 ( 接近 ) 最优解的结果



