大家好,又见面了,我是你们的朋友全栈君。
贪心算法简介:
@anthor:QYX
贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。
贪心算法每一步必须满足一下条件:
1、可行的:即它必须满足问题的约束。
2、局部最优:他是当前步骤中所有可行选择中最佳的局部选择。
3、不可取消:即选择一旦做出,在算法的后面步骤就不可改变了。
贪心算法的定义:
贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
解题的一般步骤是:
1.建立数学模型来描述问题;
2.把求解的问题分成若干个子问题;
3.对每一子问题求解,得到子问题的局部最优解;
4.把子问题的局部最优解合成原来问题的一个解。
如果大家比较了解动态规划,就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法,我们自底向上构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。
使用贪婪算法求解如下问题:
代码:
package com.qyx.Tree; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; 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>>(); //将电台存入map中 HashSet<String> hashSet=new HashSet<String>(); hashSet.add("北京"); hashSet.add("天津"); hashSet.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", hashSet); broadcasts.put("K2", hashSet2); broadcasts.put("K3", hashSet3); broadcasts.put("K4", hashSet4); broadcasts.put("K5", hashSet5); //存放所有的地区 Set<String> allAreas=new HashSet<String>(); allAreas.add("北京"); allAreas.add("天津"); allAreas.add("大连"); allAreas.add("成都"); allAreas.add("广州"); allAreas.add("上海"); allAreas.add("杭州"); allAreas.add("深圳"); //创建ArrayList,存放选择的电台集合 List<String> selects=new ArrayList<String>(); //定义一个临时的集合,在遍历过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集 Set<String> tempSet=new HashSet<String>(); //定义maxKey,保存在一次遍历过程中,能够覆盖最大未覆盖地区对应的电台的key //如果maxKey 不为null,则会加入到 selects String maxKey=null; while(allAreas.size()!=0) { //每进行一次while,都需要将maxKey置空,将tempSet清空 maxKey=null; //如果allAreas不为0.则表示还有覆盖到所有地区 //遍历 broadcasts,取出对应的Key int size=0; for(String key:broadcasts.keySet()) { //当key能覆盖的地区 tempSet.clear(); HashSet<String> set=broadcasts.get(key); tempSet.addAll(set); //取交集,求出tempSet和allAreas的交集,交集会赋给tempSet tempSet.retainAll(allAreas); //如果tempSet集合包含的未覆盖地区比maxKey还要多,则更新maxKey if(tempSet.size()>0&& (maxKey==null||tempSet.size()>size)) { maxKey=key; size=tempSet.size(); } } //将maxKey加入到selects集合中 if(maxKey!=null) { selects.add(maxKey); //将maxKey指向的广播电台覆盖的地区,从allAreas去掉 allAreas.removeAll(broadcasts.get(maxKey)); } } System.out.print(selects); } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155072.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...