首页 > 编程语言 >贪心算法思想

贪心算法思想

时间:2024-02-23 17:26:48浏览次数:29  
标签:候选 思想 算法 当前 集合 最优 贪心

贪心算法

每一步都找到当前局部最优解,短视,但是有思考 贪心算法(Greedy Alogorithm)又叫登山算法,它的根本思想是逐步到达山顶,即逐步获得最优解,是解决最优化问题时的一种简单但是适用范围有限的策略。 贪心算法没有固定的框架,算法设计的关键是贪婪策略的选择。 每一步都找到最优解,由于其短视性,不一定能找到总体最优解,但通常能找到还不错的近似解 局部最优 推导 整体最优 举不出反例时,就可以用贪心算法

使用前提

贪心策略要无后向性,也就是说某状态之后的过程不会影响以前的状态,只于当前状态有关。 走的每一步都是既定事实,不会因为之后的选择而更改  

常用组成部分

1.候选集合C

待扩展节点 为了构造问题的解决方案,有一个候选集合C作为问题的可能解,问题的最终解均取自于候选集合C。

2.当前解

随着贪心选择的进行,解集合不断扩展,直到构成一个满足问题的完整解。

3.解决判断函数solution

判断当前解是否达成问题的完整解

4.选择函数select

贪心策略,这是贪心算法的关键,它指出哪个候选对象有希望构成成问题的解。 例如如寻路中计算下一个格子到终点的距离,然后选择距离最小的格子来走

5.判断可行函数feasible

判断解中加入一个候选对象是否可行,即解集合扩展后是否满足约束条件。  

贪心与A*(纯个人理解,可能有误)

A* = 贪心 + 启发估计 A*算法也用了贪心(逐步最优解)思想,但是加入了启发式信息H(x),通过已有信息得到一种对未来预期的估算策略

A*关键:启发函数

F = G + H G = 从起点A走到当前格的距离 H = 从当前格走到终点 B 的估计距离,例如当前格到终点的曼哈顿距离 G来源于已知点信息,H来源于对未知点信息的估计,F为选择下一个将遍历节点的依据。 将计算出的F最小的格子,优先进行扩展(当前局部最优解)——贪心思想  

A*到Dijkstra

当启发函数h(n)始终为0,则将只由起点到当前格距离g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法(最短路径贪心算法)。  

标签:候选,思想,算法,当前,集合,最优,贪心
From: https://www.cnblogs.com/jk-2048/p/18029990

相关文章

  • 单调栈算法
     定义栈内元素单调按照递增(递减)顺序排列的栈。主要用于找到每一个元素左边或右边,第一个比它大或小的数时,可使用单调栈算法。时间复杂度由于每个元素最多各自进出栈一次,复杂度是O(n)功能递增单调栈:在一个队列中针对每一个元素从它右边找到第一个比它小的元素在一个......
  • Java锁的思想和区别
    乐观锁VS悲观锁乐观锁和悲观锁是两种处理并发访问的不同策略,用于确保多个操作不会同时修改同一资源而导致数据不一致的问题。它们的区别在于处理并发时的思想和实现方式:乐观锁:思想:认为在大多数情况下,读操作远远多于写操作,因此假设在绝大多数情况下并发冲突是不会发生的,直到出......
  • 排序算法-归并排序
    时空复杂度时间复杂度:O(nlogn)空间复杂度:O(n)使用了分治思想优势1.稳定归并的时空复杂度非常稳定的,不论是在哪种情况下,归并算法的时间复杂度都不变,2.高效归并算法计算效率相比其他算法也是非常快的 思路图解分把一个有n个元素的数组,分成n个有1个元素的数组然后边比较......
  • [几何算法]任意多边形求面积
    求任意平面多边形的面积通过鞋带定理,在已知多边形各顶点的情况下,可以快速计算出其面积问题分析设一个多边形顶点按逆时针或顺时针顺序为$$P_1(x_1,y_1),P_2(x_2,y_2),\ldots,P_n(x_n,y_n)$$,其中$$P_1=P_{n+1}$$(首尾相连形成闭合多边形)。根据鞋带定理,该多边形的......
  • 基于yolov2深度学习网络的车辆行人检测算法matlab仿真
    1.算法运行效果图预览   2.算法运行软件版本MATLAB2022a 3.算法理论概述      近年来,深度学习在计算机视觉领域取得了显著成果,特别是在目标检测任务中。YOLO(YouOnlyLookOnce)系列算法作为其中的代表,以其高效和实时的性能受到广泛关注。YOLOv2,作为YOL......
  • 基于WIFI指纹的室内定位算法matlab仿真
    1.算法运行效果图预览  2.算法运行软件版本matlab2022a 3.算法理论概述        随着移动互联网和物联网技术的飞速发展,位置服务(LBS)已成为许多应用的核心功能,如导航、社交网络和智能物流等。室外定位技术,如全球定位系统(GPS),已相当成熟并广泛应用。然而,由于建......
  • 洛谷题单指南-贪心-P1478 陶陶摘苹果(升级版)
    原题链接:https://www.luogu.com.cn/problem/P1478题意解读:题目的本质是任务安排问题,有n件任务,每件任务耗时不同,在一定的时间内,如何安排任务使得完成的任务越多越好。解题思路:对于这类问题,贪心策略是优先完成容易的。回到摘苹果问题,要优先摘耗费力气小的,如果高度够不着,就跳过,......
  • 类欧几里得算法
    要求类似于这样的东西:\[\begin{align*}f(n,a,b,c)&=\sum\limits_{i=0}^n{\left\lfloor\frac{ai+b}{c}\right\rfloor}\\g(n,a,b,c)&=\sum\limits_{i=0}^n{\left\lfloor\frac{ai+b}{c}\right\rfloor}^2\\h(n,a,b,c)&=\sum\limits_{i=0}^......
  • day41 动态规划part3 代码随想录算法训练营 96. 不同的二叉搜索树
    题目:96.不同的二叉搜索树我的感悟:这题,考的概率不大,听一遍,过一遍就行。理解难点:二叉搜索树定义为什么是累加的听课笔记:代码示例:classSolution:defnumTrees(self,n:int)->int:dp=[0]*(n+1)#创建一个长度为n+1的数组,初始化为0d......
  • day40 动态规划part3 代码随想录算法训练营 343. 整数拆分
    题目:343.整数拆分我的感悟:题目很难,但我动力十足!!理解难点:如何拆分为什么要保留dp[i]听课笔记:代码示例:classSolution:defintegerBreak(self,n:int)->int:#思路:#dp[i]是到目前为止能拆分取的最大值#dp[i]可以拆成j*(集合)......