贪婪算法(贪心算法)「建议收藏」

贪婪算法(贪心算法)「建议收藏」贪心算法简介:@anthor:QYX贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。贪心算法每一步必须满足一下条

大家好,又见面了,我是你们的朋友全栈君。

贪心算法简介:

@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账号...

(0)
blank

相关推荐

  • Linux 查看内存使用情况

    Linux 查看内存使用情况

  • CSV超大文件查看器

    CSV超大文件查看器下载地址:CSV查看器超大文本查看器(HkExcel)单文件绿色免安装-WindowsServer文档类资源-CSDN文库几G的文件10多秒就可以打开了,单文件绿色免安装的,下载就可以直接使用仿excel界面展示数据

  • php中的ceil和floo以及round函数「建议收藏」

    php中的ceil和floo以及round函数「建议收藏」php中的ceil和floo以及round函数

  • Matlab读取txt数据的实用方法[通俗易懂]

    Matlab读取txt数据的实用方法[通俗易懂]需求有个朋友需要我帮忙写个matlab脚本读取100个txt文档的实验数据,这些文档的结构相同,分为四列,从第一列到第四列依次是时间、位置、速度、加速度。读取完数据之后需要对数据进行处理,具体的处理方式是:提取以0.002为采样周期的数据,分类存储起来。文件内容是这样的:技术难点技术难点在于,这些文件中的数据是从一个软件中仿真得到的,由于采用的是变步长仿真,因此采样时间不统一,很难采用对…

  • TinyXML2使用教程

    TinyXML2使用教程TinyXML2使用教程原文转自http://blog.csdn.net/K346K346/article/details/487504171.TinyXML2概述TinyXML2是simple、small、efficient开源的C++XML文件解析库,可以很方便的应用到现有的项目之中。非常适合存储简单数据,配置文件,对象序列化等数据量不是很大的操作。TinyXML2详细介绍与源码获取方法详见:TinyXML2官网。2.TinyXML1与TinyXML2对比TinyXML1与TinyXM

  • HTML5实现IP Camera网页输出

    HTML5实现IP Camera网页输出

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号