【算法】一文详解贪心法

一、概述

贪心法将一个复杂问题分解为一系列较为简单的局部最优解,每一步都是对当前解的一个扩展,直到获得问题的完全解。贪心法的典型应用时求解最优化问题,而且即使是非最优解,最终得出的解也和最优解比较近似

1.1 贪心法设计思想

贪心法在解决问题的策略目光上比较短浅(笑),只会根据当前的信息做出最优的选择,而不会管未来发生了什么。贪心法并不是从整体最优考虑的,他所做出的选择只是局部上的最优,这种局部最优选择并不总能获得整体最优解,但是通常可以获得近似最优解。如果一个问题的最优解只能使用穷举获得,那么贪心法是一个牺牲精度换取时间的寻找问题近似最优解的较好方法

二、图问题的贪心法

2.1 TSP问题

描述:

TSP问题是指旅行家要旅行n个城市,要求各个城市经历并且只经历一次然后回到出发城市,并且要求所走的路径最短。

解法1:

TSP问题的贪心策略可以采用最近临近点策略:从任一城市出发,在与之相邻并且没有到达的城市中选择最近的一个,直到经过了所有城市后回到初始出发城市。这种方法同时也使用在了图求单源最短路径的普利姆算法上。

分析:
算法的时间性能为O(n2),因为执行了n-1次贪心选择,每一次贪心选择都需要查找满足贪心条件的最短边。使用该算法求解TSP问题所得结果不一定是最优解,更加多情况是一种近似解。

解法2:

思路:
TSP问题的贪心策略还可以采用最短链接策略:每次在整个图的范围内选择最短边加入解集合中,但是要保证加入解集合中的边最终新城一个哈密顿回路。在有n个结点的图中,该算法刚开始会将图的所有边都去除,变成无边的非连通图T,每个节点都是一个连通分量。算法首先使用一个线性表存储边的信息(包括连接哪两个节点,边的权值信息),然后从小到大排序。算法会按权值从大到小遍历该线性表,不断选取当前未被选取并且权值最小的边,如果这个边连接的两个顶点落在两个不同的连通分量上的时候,证明该边可以沟通两个连通分量,将两个连通分量变成一个连通分量,那么就将这个边加入到T中;否则跳过继续遍历下一个边。以此类推直到所有节点都在一个连通分量上。最后只需要将度只有1的顶点和起始顶点连接,就得出了最终解。

分析:
该算法执行了n-1次贪心选择,在每一次贪心选择中,如果顺序查找最短边,那么时间复杂度为O(n^2)。如果采用堆排序的方法对未选择的边建立小顶堆,那么可以将时间复杂度提高到O(n*long2n)。

2.2 图着色问题

问题:
给定无向连通图G=(V,E),图着色问题要求使用k种颜色对图G中的顶点进行着色,需要使任意两个相邻的顶点颜色不同,求k的最小值是多少。
示例:一个k=3的图着色问题的解
思想:
假设k个颜色的集合为{1,2…k},一种贪心算法是选择一种颜色,然后使用改颜色尽可能多地将顶点着色,也就是选择颜色1,遍历图中未被着色的各个顶点,如果某定点可以用颜色1着色,也就是它相邻的顶点颜色都不是颜色1,那么就将它着色。一次遍历后再选择颜色2重复上述过程,直到所有的顶点都已经被着色。

分析:
该方法需要试探k种颜色,每种颜色都需要遍历所有顶点进行冲突测试,设图有n个结点,那么他的时间复杂度为O(k*n)。需要说明的是,贪心法求解图着色问题得到的不一定是最优解,在二部图中,当i为奇数的时候,顶点i和除了顶点i+1之外的所以顶点相连;当i为偶数的时候顶点i和除了顶点i-1之外的所有顶点相连。这样的图称之为二部图,在二部图中,顶点可以被划分为两个集合:编号为奇数的顶点划分到集合v,编号为偶数的顶点划分到集合u。

二部图举例
显然,二部图只需要两种颜色就可以完成着色,但是按照贪心着色法,需要使用n种颜色进行着色。

2.3 最小生成树问题

详情请见数据结构中的克鲁斯卡尔算法和普利姆算法
https://blog.csdn.net/weixin_45434953/article/details/127459188

三、组合问题中的贪心法

3.1 背包问题

问题描述:
给定n种物品和一个背包,物品i的重量为wi,其价值为vi,背包容量为C,如何选入装入背包的物品,使得装入背包中物品的总价值最大?

思想:
用贪心法求解背包问题的关键是如何确定贪心策略,使得按照一定次序选择装入物品,直到背包装满。常用的贪心策略有三种:

  1. 选择价值最大的物品,但是可能会导致背包容量消耗过快
  2. 选择重量最轻的物品
  3. 综合以上两种策略,选择性价比最高的物品,也就是使用价值/重量,选出单位价值最大的物品。

贪心策略3往往是最容易得出近似最优解的策略,而策略3的主要时间消耗来自于需要将各物品按照单位重量价值进行排序,因此其时间复杂度为O(n*log2n),贪心法无法得出0-1背包问题的最优解,因为物品不允许分割,部分闲置的背包容量浪费了,因此0-1背包问题的最佳解法还是使用动态规划法

3.2 活动安排问题

问题:
设有n个活动集合E={1,2…n},其中每个活动都要求使用统一资源,而同一时间内只有一个活动能够使用该资源,每个活动i都有一个起始时间si和一个结束时间fi,如果选择了将资源分配给活动i,那么活动i将会在 [ s i , f i ) [s_i,f_i) [si,fi内占用该资源。如果两个活动的时间区间不相交,则称两个活动是相容的。活动安排问题要求在所给出的活动中选出最大的相容活动子集,也就是尽可能安排更多的活动

思想:
贪心法求解活动安排问题的关键是如何选择贪心策略,使得按照一定顺序选择相容活动,并且能够安排尽量多的活动,一般使用的贪心策略是:贪心地选择最早结束的活动,这样可以使得下一个活动尽早开始。这种贪心选择的目的是使得剩余时间最大化,以便安排尽可能多的相容活动。为了在每一次贪心选择时快速查找具有最早结束时间相容活动,可以将n个活动按照结束时间非减续排列。

算法分析:
各个活动按照结束时间从小到大排序,使用快速排序其时间代价是O(nlog2n)。然后依次考察活动的代价是O(n),因此总的时间复杂度为O(nlog2n)。

3.3 多机调度问题

问题:
设有n个独立作业{1,2…n},由m台相同的机器{M1,M2,…Mm}进行加工处理,作业i所需的处理时间为ti,每个作业都可以在任何一机器上,但是不可以间断和拆分。多机调度问题要求是的所给的n个作业在尽可能短的时间内使用m台机器加工完成。

想法:
贪心法求解多机调度问题的贪心策略是最长处理时间作业优先,也就是将处理时间最长的作业分配给最先空闲的机器,这样可以保证处理时间长的作业优先处理,从而在整体上获取尽可能短的处理时间。

分析:
首先使用快排进行排序,时间性能为O(nlog2n),然后完成前m个作业,时间性能为m。通常时间复杂度为O(nxm)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3216.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【多线程】常见的锁策略

✨个人主页:bit me👇 ✨当前专栏:Java EE初阶👇 ✨每日一语:老当益壮,宁移白首之心;穷且益坚,不坠青云之志。 目 录🏳️一. 乐观锁 vs 悲观锁🏴二. 普通的互斥…

清晰概括:进程与线程间的区别的联系

相关阅读: 🔗通俗简介:操作系统之进程的管理与调度🔗如何使用 jconsole 查看Java进程中线程的详细信息? 目录 一、进程与线程 1、进程 2、线程 二、进程与线程之间的区别和联系 1、区别 2、联系 一、进程与线程 …

程序员接私活一定要知道的事情,我走的弯路你们都别走了

文章目录前言一、程序员私活的种类1.兼职职位众包2.自由职业者驻场3.项目整包二、这3种私活可以接1.有熟人2.七分熟的项目3.需求明确的项目三、这3种私活不要接1.主动找上门的中介单2.一味强调项目简单好做3.外行人给你拉的项目四、接单的渠道1.线下渠道2.线上渠道3.比较靠谱的…

计网之HTTP协议和Fiddler的使用

文章目录一. HTTP概述和fidder的使用1. 什么是HTTP2. 抓包工具fidder的使用2.1 注意事项2.2 fidder的使用二. HTTP协议格式1. HTTP请求格式1.1 基本格式1.2 认识URL1.3 方法2. 请求报头关键字段3. HTTP响应格式3.1 基本格式3.2 状态码一. HTTP概述和fidder的使用 1. 什么是HTT…

cpu中缓存简介

一级缓存是什么: 一级缓存都内置在CPU内部并与CPU同速运行,可以有效的提高CPU的运行效率。一级缓存越大,CPU的运行效率越高,但受到CPU内部结构的限制,一级缓存的容量都很小。 CPU缓存(Cache Memory&#xf…

【设计模式】23种设计模式之七大原则

【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…

冲击蓝桥杯-并查集,前缀和,字符串

目录 前言 一、并查集 1、并查集的合并(带路径压缩) 2、询问是否为同一个集合 3、例题 二、前缀和 1 、前缀和是什么 2、经典题目 三- 字符串处理 1、字符串的插入 2、字符串转化为int类型 3、字符反转 前言 并查集合前缀,字符串…

Python让ChatGPT全自动改写生成文章教程

ChatGPT是一个在自然语言处理领域非常先进的文本生成模型,它能够产生高质量、连贯的文章。它受到了广泛的关注,因为它可以自动生成大量的文本,从而减轻了人工写作的负担。怎么使用chatgpt批量改写文章?最简单的方式就是找到一家接…

「Vue面试题」vue要做权限管理该怎么做?如果控制到按钮级别的权限怎么做?

文章目录一、是什么二、如何做接口权限路由权限控制菜单权限方案一方案二按钮权限方案一方案二小结参考文章一、是什么 权限是对特定资源的访问许可,所谓权限控制,也就是确保用户只能访问到被分配的资源 而前端权限归根结底是请求的发起权,…

刷题之最长公共/上升子序列问题

目录 一、最长公共子序列问题(LCS) 1、题目 2、题目解读 ​编辑 3、代码 四、多写一题 五、应用 二、最长上升子序列问题(LIS) 1、题目 2、题目解读 3、代码 四、多写一道 Ⅰ、题目解读 Ⅱ、代码 一、最长公共子序列问题&…

刷题训练营之栈与队列

文章目录前言一、用队列实现栈1.题目介绍2.思路3.代码二、用栈实现队列1.题目介绍2.思路3.代码前言 本题是在栈与队列的基础上,为巩固两者而出的题,所以基本是在实现了栈与队列的基础上做的,如果没有栈与队列的基础,请看我之前的…

Nginx的漏洞浮现

本文参考https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/环境搭建均是采用docker拉取环境请移步到参考。一、Nginx的配置错误案列1. CRLF注入漏洞配置错误文件error1.confrootubuntu-virtual-machine:/vulhub/vulhub-master/nginx/insecure-configurati…

数据结构中的堆

一、树的重要知识点 节点的度:一个节点含有的子树的个数称为该节点的度(有几个孩子)叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I...等节点为叶节点(0个孩子)非终端节点或分支节点…

css实现炫酷充电动画

先绘制一个电池&#xff0c;电池头部和电池的身体 这里其实就是两个div&#xff0c;使用z-index改变层级&#xff0c;电池的身体盖住头部&#xff0c;圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…

.NET Core 实现Excel的导入导出

.NET Core 使用NPOI实现Excel的导入导出前言NPOI简介一、安装相对应的程序包1.1、在 “管理NuGet程序包” 中的浏览搜索&#xff1a;“NPOI”二、新建Excel帮助类三、调用3.1、增加一个“keywords”模型类&#xff0c;用作导出3.2、添加一个控制器3.3、编写导入导出的控制器代码…

一本通 3.2.1 队列的基本应用

1332&#xff1a;【例2-1】周末舞会 【题目描述】 假设在周末舞会上&#xff0c;男士们和女士们进入舞厅时&#xff0c;各自排成一队。跳舞开始时&#xff0c;依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同&#xff0c;则较长…

【数据结构】树和二叉树的介绍

文章目录前言一、树1.1 树的概念1.2 树的相关概念1.3 树的表示1.4 树的用途二、二叉树2.1 二叉树的概念2.2 两种特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储方式总结前言 树是一种让程序员们既爱又恨的数据结构。它就像是一棵大树&#xff0c;让你可以轻松地摘取其中的果实…

【10】核心易中期刊推荐——模式识别与机器学习

🚀🚀🚀NEW!!!核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广,核心期刊发表论文是国内很多作者晋升的硬性要求,并且在国内属于顶尖论文发表,具有很高的学术价值。在中文核心目录体系中,权威代表有CSSCI、CSCD和北大核心。其中,中文期刊的数…

【C++进阶】C++11(中)左值引用和右值引用

文章目录左值引用左值引用的概念左值引用的使用右值引用右值引用的概念右值引用的使用左右值相互引用左值引用对右值进行引用右值引用对左值进行引用右值引用使用场景和意义左值引用的优势左值引用的短板右值引用的优势完美转发模板万能引用完美转发实际运用场景左值引用 左值…

vue3+ts 开发效率提升

1、vite pnpm项目初始化 pnpm&#xff1a; 比npm或yarn快10倍 pnpm与其他包管理器&#xff08;如npm和Yarn&#xff09;的不同之处在于它使用一种称为“硬链接”的独特安装方法。当你使用PNPM安装一个包时&#xff0c;它并不会将包的文件复制到每个项目的node_modules目录中&a…