在求解一个问题的过程中，每次选择都是当前最优解（即局部最优解，而非全局最优解）
贪婪算法使用场景：
1，遇到NP完全问题（没有快速算法的问题，即没有全局最优解）时
2，暂时没有想到更好的解法时，因为贪婪算法思路通常会相对简单
贪婪算法问题如背包问题，教室安排问题，广播问题
NP完全问题：简单定义为是，以难著称的问题，如旅行商人问题和集合覆盖问题。
例：（集合覆盖问题）
假如你需要将一则新闻广播到50个州，每个广播站都能广播一定数量的州，且都需要费用（假设费用相同），因此希望用到的广播站尽可能少。设计算法求出最小广播集合。
算法思路：假定一个州集合。每次选取一个广播，选取原则为当前广播占包含数量最多的未覆盖州。
直到需求州数目为0为止。
贪婪算法即属于近似算法的一种。判断一个近似算法的优劣标准如下：
1，速度有多快
2，得到的近似解和最优解的接近程度
如果能够判断一个问题是NP完全问题，则可以不必寻找最优解，直接使用近似算法即可。
那么，如何判断NP完全问题呢？
代码小工蚁的#《算法图解》#学习笔记-C8贪婪算法C8 贪婪算法greedy algorithms 一、贪婪算法 ...
贪婪算法 贪婪算法，也被称为“贪心算法”。贪婪算法分阶段地工作。在每一个阶段，都可以认为所作决定是好的，而不考虑将...
读书笔记/人生算法之无知、衰朽和贪婪 【标题】人生算法之无知、衰朽和贪婪 【书籍】人生算法 【01】人生算法之无知...
1.贪婪算法: 每一步都采用当前局部的(这里是重点)最优的做法，最终得到全局最优解;这是一种完美算法，要找到最优的...
3.集合覆盖问题 现在有个广播节目，需要让全美50个州的听众收听。每个广播台都覆盖特定的区域，不同广播台覆盖区域可...
1.教室调度问题 一间教室的课程表如上所示，现在如果尽可能在这个教室上最多的课，需要怎么安排课程呢？由于课程之间有...
贪婪算法(Greedy Algorithm)也叫算贪心法,贪婪法.它是一个遵循启发式解决问题的算法范式.它的核心思...
贪婪算法：选择局部最优解达到全局最优 区间调度问题 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不...
假设某节目要覆盖以下省份： 各个电视台的覆盖范围如下： 解决思路： step1： 选出一个覆盖了最多未覆盖省份的电...
在求解一个问题的过程中，每次选择都是当前最优解（即局部最优解，而非全局最优解） 贪婪算法使用场景：1，遇到NP完全...
本文标题：贪婪算法
本文链接：https://www.haomeiwen.com/subject/ncklbqtx.html
网友评论