贪心算法相关知识
目录
基础
定义
工作原理
步骤一:分解问题
步骤二:确定贪心策略
步骤三:求解子问题
步骤四:合并结果
适用场景
活动安排问题
找零问题
哈夫曼编码
局限性
高级
与动态规划的对比
决策方式
最优性保证
时间复杂度和空间复杂度
算法实现要点
贪心策略的证明
数据结构的选择
更多的实际应用示例
资源分配问题
文件压缩中的行程长度编码(RLE)改进
股票买卖问题(简单情况)
贪心算法的优化方向
贪心算法的挑战与应对
贪心算法的未来发展趋势
进阶
贪心算法的数学基础与理论拓展
贪心算法在复杂系统中的应用
贪心算法的性能分析与改进方法
基础
定义
- 贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下看起来是最好的选择的算法策略。也就是说,它不从整体最优上加以考虑,而是在局部最优解的基础上,希望通过一系列局部最优的选择来达到全局最优。
工作原理
-
步骤一:分解问题
- 将一个复杂的问题分解为一系列的子问题。例如,在找零问题中,要将找零的总金额分解为各种面额组合的子问题。
-
步骤二:确定贪心策略
- 针对每个子问题,确定一种贪心的选择策略。在活动安排问题中,贪心策略是每次选择结束时间最早的活动,这样可以在有限的时间内安排尽可能多的活动。
-
步骤三:求解子问题
- 按照贪心策略,依次对每个子问题进行求解,不考虑整体的最优解情况。如在哈夫曼编码问题中,贪心策略是每次选择频率最低的两个节点合并,不断构建哈夫曼树。
-
步骤四:合并结果
- 将各个子问题的解合并起来得到最终的解。在任务调度问题中,按照每个任务的某种贪心属性(如最短处理时间等)安排任务顺序后,最终得到整体的任务调度方案。
适用场景
-
活动安排问题
- 有一系列活动,每个活动都有开始时间和结束时间。要在有限的时间内安排尽可能多的活动。贪心算法按照活动结束时间的先后顺序对活动进行排序,然后依次选择不与已选活动冲突的活动,这样可以得到最多的活动安排数量。
-
找零问题
- 给定一个需要找零的金额,以及有限种类的硬币面额(如 1 元、5 角、1 角等)。贪心算法的策略是每次选择尽可能大面额的硬币,直到凑够找零金额。这种算法在硬币面额满足特定条件(如任意大面额都是小面额的整数倍)时能得到最优解。
-
哈夫曼编码
- 对于一组字符及其出现的频率,要构建一种编码方式使得总编码长度最短。贪心算法通过每次选择频率最低的两个子树合并来构建哈夫曼树,最终得到每个字符的哈夫曼编码。
局限性
- 贪心算法并不总是能得到全局最优解。例如在旅行商问题(Travelling Salesman Problem,TSP)中,要找到一个旅行商经过所有城市且每个城市只经过一次的最短路径。如果采用贪心算法,比如每次选择距离当前城市最近的未访问城市作为下一个目标,这样得到的路径往往不是全局最短路径。因为贪心算法只考虑了当前的局部最优选择,而忽略了后续选择可能产生的影响。
高级
与动态规划的对比
-
决策方式
- 贪心算法在每一步只做出当前看起来最优的决策,而不考虑这一决策对未来步骤的影响。例如在任务调度问题中,如果贪心策略是选择执行时间最短的任务先执行,它不会去考虑这个任务执行完之后对其他任务的连锁影响是否会导致整体最优性被破坏。
- 动态规划则会考虑整个问题的所有子问题以及它们之间的相互关系。动态规划会通过记录子问题的解来避免重复计算,在做决策时会综合考虑各个子问题的最优解组合来得到全局最优解。例如在最长公共子序列问题中,动态规划会通过填充一个二维数组来记录不同长度的子序列之间的公共子序列长度,最后通过回溯这个数组得到最长公共子序列,而不是像贪心算法那样只考虑局部的最优选择。
-
最优性保证
- 贪心算法不一定能保证得到全局最优解,只有在问题具有特定的结构性质(如拟阵结构等)时才能保证。例如在部分背包问题中,因为物品可以分割,贪心算法(按照单位价值最高优先选择物品)可以得到最优解;但在 0 - 1 背包问题中,每个物品要么全选要么不选,贪心算法就不能保证得到最优解。
- 动态规划如果正确地定义了状态和状态转移方程,是能够保证得到全局最优解的。
-
时间复杂度和空间复杂度
- 贪心算法通常具有较低的时间复杂度和空间复杂度。由于它只需要进行一次扫描或者有限次数的操作就能得到解,其时间复杂度往往是多项式级别的,如或者等,空间复杂度也比较低,很多时候只需要常数级或者与输入规模线性相关的空间。例如在找零问题中,贪心算法的时间复杂度主要取决于对硬币面额的排序时间(如果需要排序的话),通常为(假设 n 是硬币面额的种类数),空间复杂度为。
- 动态规划的时间复杂度和空间复杂度相对较高。因为它需要存储所有子问题的解,时间复杂度可能是多项式的高次幂或者指数级别的,空间复杂度也可能很高。例如在矩阵链乘法问题中,动态规划的时间复杂度是,空间复杂度是,其中 n 是矩阵的个数。
算法实现要点
-
贪心策略的证明
- 在使用贪心算法之前,最好能够证明贪心策略的正确性。对于一些简单的问题,可以通过直观的分析和反证法来证明。例如在活动安排问题中,可以假设存在一个最优解不是按照贪心策略(按活动结束时间最早排序选择)得到的,然后通过调整活动顺序可以证明这个最优解可以转换为按照贪心策略得到的解,从而证明贪心策略的正确性。
- 对于复杂的问题,可能需要借助一些数学工具,如数学归纳法、拟阵理论等。例如,对于具有拟阵结构的问题,可以利用拟阵的性质来证明贪心算法的正确性。
-
数据结构的选择
- 根据贪心策略和问题的特点选择合适的数据结构。在找零问题中,如果硬币面额是固定的,并且不需要排序,可能只需要一个简单的数组来存储面额信息就可以了。
- 在活动安排问题中,为了方便按照活动结束时间排序并选择活动,可以使用排序算法(如快速排序)先对活动的时间区间进行排序,这时候就需要用到数组或者链表等数据结构来存储活动信息。在哈夫曼编码问题中,构建哈夫曼树时通常会用到优先队列(最小堆或者最大堆)来高效地选择频率最低的节点进行合并操作。
更多的实际应用示例
-
资源分配问题
- 假设有多个任务和有限的资源(如 CPU 时间、内存等),每个任务需要一定的资源量并且有相应的收益。贪心算法可以根据不同的贪心策略来分配资源,例如按照单位资源的收益最高来分配资源给各个任务。如果资源是可分割的,这种贪心策略可能会得到较好的结果,但如果资源不可分割(如每个任务只能分配完整的 CPU 核心),贪心算法可能无法保证全局最优。
-
文件压缩中的行程长度编码(RLE)改进
- 在基本的行程长度编码中,它通过连续重复字符的个数和字符本身来表示数据。可以使用贪心算法对其进行改进,例如在对图像数据进行编码时,不是简单地按照顺序统计重复字符个数,而是根据图像的局部特征(如颜色块的分布等)采用贪心策略来选择更合适的编码单元,可能会提高压缩效率。
-
股票买卖问题(简单情况)
- 如果只能进行一次股票买入和卖出操作,并且已知股票在未来一段时间内每天的价格。贪心算法的策略可以是记录最低价格,然后在价格高于最低价格时卖出,这样可以获得最大的利润。但这种情况是比较简单的,对于更复杂的股票买卖规则(如多次买卖、手续费等情况),贪心算法可能需要更复杂的策略或者可能不再适用。
贪心算法的优化方向
- 结合其他算法:贪心算法可以与其他算法结合使用,以提高求解问题的效率和准确性。例如,可以将贪心算法与模拟退火、遗传算法等启发式算法相结合,在贪心算法得到一个局部最优解的基础上,通过启发式算法进行进一步的搜索和优化,以期望找到更接近全局最优的解。
- 动态调整贪心策略:在一些复杂的问题中,固定的贪心策略可能无法适应不同的情况。可以根据问题的特点和求解过程中的反馈信息,动态地调整贪心策略。例如,在网络路由问题中,可以根据网络的拥塞情况和链路质量的变化,动态地调整路由选择的贪心策略,以提高网络的性能和可靠性。
- 多阶段贪心算法:对于一些可以分为多个阶段的问题,可以设计多阶段的贪心算法。在每个阶段,根据当前的情况选择局部最优的决策,然后在后续的阶段中根据前面阶段的决策结果进行调整和优化。例如,在项目规划问题中,可以将项目分为多个阶段,每个阶段都采用贪心算法进行资源分配和任务安排,同时考虑前一阶段的结果对后续阶段的影响。
贪心算法的挑战与应对
- 局部最优陷阱:贪心算法的主要挑战之一是可能陷入局部最优解而无法得到全局最优解。为了避免这种情况,可以采用多种方法进行尝试。例如,可以使用不同的初始状态进行贪心算法的求解,然后选择其中最好的结果;或者在贪心算法的求解过程中,引入一定的随机性,以增加跳出局部最优解的可能性。
- 问题的复杂性:对于一些复杂的问题,很难确定一个合适的贪心策略。在这种情况下,可以通过对问题进行分析和简化,找到问题的关键特征和约束条件,从而设计出有效的贪心策略。同时,可以通过实验和分析,评估贪心算法在不同情况下的性能和效果,以便进行进一步的优化和改进。
- 数据的不确定性:在实际应用中,数据往往存在不确定性,这可能会影响贪心算法的性能和结果。为了应对数据的不确定性,可以采用一些鲁棒性的贪心策略,例如在选择决策时考虑多种可能的情况,并选择最稳定的决策;或者使用一些数据预处理技术,如数据清洗、数据平滑等,以减少数据的不确定性对贪心算法的影响。
贪心算法的未来发展趋势
- 自适应贪心算法:随着人工智能和机器学习技术的发展,未来可能会出现自适应的贪心算法,能够根据问题的特点和求解过程中的反馈信息,自动调整贪心策略和参数,以提高算法的性能和适应性。
- 并行贪心算法:对于大规模的问题,并行计算可以显著提高算法的效率。未来可能会出现并行的贪心算法,能够利用多核处理器、分布式计算等技术,同时对多个子问题进行求解,以加快算法的求解速度。
- 贪心算法与深度学习的结合:深度学习在图像识别、自然语言处理等领域取得了巨大的成功。未来可能会出现贪心算法与深度学习相结合的方法,利用深度学习的强大特征提取能力和贪心算法的高效求解能力,解决复杂的实际问题。例如,可以使用深度学习模型对问题进行建模和预测,然后使用贪心算法进行优化和决策。
进阶
-
贪心算法的数学基础与理论拓展
- 拟阵理论:拟阵是一种抽象的数学结构,它为贪心算法提供了坚实的理论基础。在拟阵中,独立集的性质类似于贪心算法中的局部最优选择。通过判断一个问题是否可以建模为拟阵,可以确定贪心算法是否能得到全局最优解。例如,在图的最小生成树问题中,可以通过将图的边集看作拟阵的元素,利用贪心算法(Kruskal 算法和 Prim 算法)有效地求解最小生成树。
- 博弈论视角下的贪心算法:在某些情况下,可以将贪心算法看作一种博弈过程。每个决策步骤可以看作是参与者在博弈中的行动,而目标是在这个博弈中达到最优的结果。通过分析博弈的均衡状态和参与者的策略,可以更好地理解贪心算法的性能和局限性。例如,在资源分配问题中,不同的参与者可能会根据自己的利益进行决策,而贪心算法可以看作是一种逐步逼近均衡状态的过程。
-
贪心算法在复杂系统中的应用
- 复杂网络分析:在复杂网络中,贪心算法可以用于节点重要性评估、社区发现等任务。例如,在评估节点重要性时,可以采用贪心算法选择具有最高度、介数等特征的节点,这些节点往往在网络的信息传播、稳定性等方面起着关键作用。在社区发现问题中,可以通过贪心算法逐步合并相似的节点或子社区,以得到网络的社区结构。
- 供应链管理:在供应链管理中,贪心算法可以用于优化库存管理、物流路径规划等问题。例如,在库存管理中,可以根据贪心策略(如最小化库存成本、最大化服务水平等)来确定最佳的库存水平和补货策略。在物流路径规划中,可以采用贪心算法选择最短路径、最小化运输成本等目标下的最优路径。
-
贪心算法的性能分析与改进方法
- 性能分析指标:除了传统的时间复杂度和空间复杂度外,还可以使用其他指标来评估贪心算法的性能。例如,可以考虑算法的近似比,即贪心算法得到的解与最优解之间的比例关系。如果一个贪心算法的近似比是有界的,那么它可以在一定程度上保证得到接近最优解的结果。此外,还可以分析算法的稳定性和鲁棒性,即在输入数据存在噪声或不确定性时,算法的性能表现。
- 改进方法:为了提高贪心算法的性能,可以采用多种改进方法。例如,可以结合局部搜索、模拟退火等启发式算法,在贪心算法得到的解的基础上进行进一步的优化。还可以采用并行计算、分布式计算等技术,加快贪心算法的求解速度。另外,通过对问题进行更深入的分析和建模,设计更合适的贪心策略和数据结构,也可以提高算法的性能。
相关文章:
贪心算法相关知识
目录 基础 定义 工作原理 步骤一:分解问题 步骤二:确定贪心策略 步骤三:求解子问题 步骤四:合并结果 适用场景 活动安排问题 找零问题 哈夫曼编码 局限性 高级 与动态规划的对比 决策方式 最优性保证 时间复杂度和…...

济南比较出名的人物颜廷利:全球最具影响力的思想家起名大师
颜廷利教授是一位在思想、哲学、教育、易学、国学、心理学、命名学等多个领域具有深远影响的学者。他被誉为“世界点赞第一人”,在国内外享有极高的声誉,被认为是现代易经三大泰斗之首。山东目前比较厉害的名人颜廷利教授的学术成就和影响力横跨哲学、思…...

第100+27步 ChatGPT学习:概率校准 Temperature Scaling
基于Python 3.9版本演示 一、写在前面 最近看了一篇在Lancet子刊《eClinicalMedicine》上发表的机器学习分类的文章:《Development of a novel dementia risk prediction model in the general population: A large, longitudinal, population-based machine-learn…...
Python知识点:如何应用Python工具,使用NLTK进行语言模型构建
开篇,先说一个好消息,截止到2025年1月1日前,翻到文末找到我,赠送定制版的开题报告和任务书,先到先得!过期不候! 如何使用NLTK进行语言模型构建 在自然语言处理(NLP)中&a…...

深入浅出MySQL
深入浅出MySQL 以下内容参考自 《MySQL是怎样运行的:从根儿上理解MySQL》一书,强烈推荐 存储引擎 对于不同的表可以设置不同的存储引擎 CREATE TABLE tableName (xxxx ) ENGINE 引擎名称; # 修改 ALTER TABLE tableName ENGINE xxx; 编码格式 my…...

【WRF工具】cmip6-to-wrfinterm工具概述:生成WRF中间文件
cmip6-to-wrfinterm工具概述 cmip6-to-wrfinterm工具安装cmip6-to-wrfinterm工具使用快速启动(Quick start)情景1:MPI-ESM-1-2-HR(默认):情景2:BCMM情景3:EC-Earth3 更改使用&#x…...
大厂面试真题:阿里经典双重检测DCL对象半初始化问题
阿里面试题中提到的双重检测DCL(Double-Checked Locking)对象半初始化问题,是Java多线程编程中一个经典的问题。以下是对这一问题的详细解析: 一、双重检测锁(DCL)概述 双重检测锁是一种用于实现单例模式…...

20款奔驰CLS300升级原厂抬头显示HUD 23P智能辅助驾驶 触摸屏人机交互系统
以下是为您生成的一份关于 18 款奔驰 CLS 老款改新款的改装文案: 18 款奔驰 CLS 老款改新款:科技升级,畅享极致驾驶体验 在汽车改装的世界里,每一次的升级都是对卓越的追求。今天,让我们一同探索 18 款奔驰 CLS 老款改…...

GoogleNet原理与实战
在2014年的ImageNet图像识别挑战赛中,一个名叫GoogLeNet 的网络架构大放异彩。以前流行的网络使用小到11,大到77的卷积核。本文的一个观点是,有时使用不同大小的卷积核组合是有利的。 回到他那个图里面你会发现,这里的一个通过我们最大的池化…...

MongoDB 数据库服务搭建(单机)
下载地址 下载测试数据 作者:程序那点事儿 日期:2023/02/15 02:16 进入下载页,选择版本后,右键Download复制连接地址 下载安装包 wget https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel70-5.0.14.tgz …...

基于springboot+小程序的智慧物业平台管理系统(物业1)
👉文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1、项目介绍 智慧物业平台管理系统按照操作主体分为管理员和用户。 1、管理员的功能包括报修管理、投诉管理管理、车位管理、车位订单管理、字典管理、房屋管理、公告管理、缴费管理、维修指派管理、…...

[SpringBoot] 苍穹外卖--面试题总结--上
前言 1--苍穹外卖-SpringBoot项目介绍及环境搭建 详解-CSDN博客 2--苍穹外卖-SpringBoot项目中员工管理 详解(一)-CSDN博客 3--苍穹外卖-SpringBoot项目中员工管理 详解(二)-CSDN博客 4--苍穹外码-SpringBoot项目中分类管理 详…...

[C#]使用onnxruntime部署yolov11-onnx实例分割模型
【官方框架地址】 https://github.com/ultralytics/ultralytics.git 【算法介绍】 在C#中使用ONNX Runtime部署YOLOv11-ONNX实例分割模型,涉及到模型的加载、数据预处理、模型推理和后处理几个关键步骤。 首先,需要确保已经安装了ONNX Runtime的NuGe…...
Polars的Config
Config Config 内容使用示例设置并行执行设置日志详细程度指定null值设置推断schema的行数启用低内存模式获取当前配置选项的值 在Polars的Python API中,Config部分提供了配置选项,允许用户自定义Polars的行为。以下是一些可配置的选项及其使用示例&…...
【面试官】 多态连环问
以下是一些关于封装的常见面试题及答案: 封装 1. 什么是封装? 答案:封装是面向对象编程的三大特性之一,它是将数据和操作数据的方法绑定在一起,并且通过访问修饰符限制对数据的直接访问,只提供特定的方法来…...

Vue 路由设置
为了防止遗忘,记录一下用Vue写前端配置路由时的过程,方便后续再需要用到时回忆。 一、举个例子 假如需要实现这样的界面逻辑: 在HomePage中有一组选项卡按钮用于导航到子页面,而子页面Page1中有一个按钮,其响应事件是…...

力扣110:判断二叉树是否为平衡二叉树
利用二叉树遍历的思想编写一个判断二叉树,是否为平衡二叉树 示例 : 输入:root [3,9,20,null,null,15,7] 输出:true思想: 代码: int getDepth(struct TreeNode* node) {//如果结点不存在,返回…...
Chromium 中JavaScript Fetch API接口c++代码实现(一)
Fetch API主要暴露了三个接口一个方法。 三个接口 Request(资源请求)Response(请求的响应)Headers(Request/Response头部信息)一个方法 fetch()(获取资源调用的方法更多介绍参考 Fetch API - Web API | MDN (mozilla.org) 一、 来看一段前端代码 <!DOCTYPE html> <h…...

ARM(5)内存管理单元MMU
一、虚拟地址和物理地址 首先,计算机系统的内存被组成一个由M个连续的字节大小组成的数组。每字节都会有一个唯一的物理地址。CPU访问内存最简单的方式就是使用物理地址。如下图: 图 1 物理地址,物理寻址 而现在都是采用的都是虚拟寻址的方法。CPU生成一…...
文件上传漏洞原理
原理:\n应用中存在上传功能,但是上传的文件没有经过严格的合法性检验或者检验函数存在缺陷,导致可以上传木马文件到服务器,并且能够执行其中的恶意代码。\n\n危害:\n服务器的网页篡改,网站被挂马࿰…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...