贪心算法
算法 贪心
2023-09-14 08:58:39 时间
贪心算法
一、基本概念:
所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路:
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解,得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
实际上,贪心算法适用的情况很少。
一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。
四、贪心算法的实现框架
从问题的某一初始解出发;
while (能朝给定总目标前进一步)
{
利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。
六、例题分析
下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析:
目标函数: ∑pi最大
约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
(2)每次挑选所占重量最小的物品装入是否能得到最优解?
(3)每次选取单位重量价值最大的物品,成为解本题的策略。
值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。
贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。
可惜的是,它需要证明后才能真正运用到题目的算法中。
一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
(1)贪心策略:选取价值最大者。反例:
W=30
物品:A B C
重量:28 12 12
价值:30 20 20
根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
(2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
(3)贪心策略:选取单位重量价值最大的物品。反例:
W=30
物品:A B C
重量:28 20 10
价值:28 20 10
根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
转自:http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html
相关文章
- 经典算法题每日演练——第四题 最长公共子序列
- Java实现 蓝桥杯VIP 算法训练 字符串逆序
- Java实现 蓝桥杯VIP 算法训练 筛选号码
- Java 蓝桥杯 算法训练(VIP) 最大体积
- 数据结构与算法之美-13 贪心 分治 回溯 [MD]
- 算法导论第九章中位数和顺序统计量(选择问题)
- Delaunay三角网生成算法
- AI:模型蒸馏/知识蒸馏(Knowledge Distilling,KD)算法的简介、案例应用之详细攻略
- 【无人机】基于灰狼优化算法的无人机路径规划问题研究(Matlab代码实现)
- 【路径规划】基于拓展随机树(RRT)算法的路径规划问题(Matlab代码实现)
- 传感器|基于改进贪心算法的最佳传感器位置选择(Matlab代码实现)
- 区间DP与贪心算法的联系(uav Cutting Sticks && poj Fence Repair(堆的手工实现))
- 1481. 不同整数的最少数目-快速排序+贪心算法
- 1371. 每个元音包含偶数次的最长子字符串-贪心算法-状态保存
- 1827. 最少操作使数组递增-贪心算法-原地修改数组
- 2304. 网格中的最小路径代价-动态规划+贪心算法
- 1899. 合并若干三元组以形成目标三元组-c语言-贪心算法+标记数组
- 455. 分发饼干-排序加贪心算法
- 670. 最大交换-动态规划+贪心算法-力扣最快算法
- 【Linux 内核 内存管理】引导内存分配器 bootmem ③ ( bootmem 引导内存分配器算法 | 低端内存映射 | 内存记录位图 | 最先适配算法 | 内存分配记录 | 内存操作函数 )
- 算法基础--贪心算法
- 五类常见算法小记 (递归与分治,动态规划,贪心,回溯,分支界限法)
- 贪心算法——状态不重复,无法使用dp优化的时候就要考虑了
- 使用SoC-ML检测Azure Sentinel中的威胁—— 这个SOC-ML就是一些分析异常的规则啊!!!和ML有毛关系?!难道是自己内置的异常检测算法你可以调整参数上报异常事件???
- Keras之MLPR:利用MLPR算法(3to1【窗口法】+【Input(3)→(12+8)(relu)→O(mse)】)实现根据历史航空旅客数量数据集(时间序列数据)预测下月乘客数量问题
- 试题 算法训练 乘法表
- m基于遗传优化的凸松弛算法完成从二维人体图像中提取三维姿态的matlab仿真
- 史上最清楚的BP算法详解
- 数据结构和算法 二十一、贪心算法