贪心法
贪心法是一种不追求最优解,只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况。
在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。
从贪心算法的定义可以看出,贪心算法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法是否可以得到最优解。
利用贪心法求解需要注意以下两点:
(1)贪心法求解是否适合。
用贪心法解题很方便,但它的适用范围很小,判断一个问题是否适合用贪心法求解,需要在平时多加练习,依据解题经验来判断是否适合使用贪心算法。如下边的例子:以找币问题为例,如果一个货币系统有3种币值,面值分别为一角、五分和一分,求最小找币数时,可以用贪心法求解;如果将这三种币值改为一角一分、五分和一分,就不能使用贪心法求解。
(2)选择何种贪心标准才能保证求得最优解。
在选择贪心标准时,要对所选的贪心标准进行验证才能使用,不要被表面上看似正确的贪心标准所迷惑。
贪心法的基本原理是从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
因此,贪心法存在以下问题:
(1)不能保证求得的最后解是最优解;
(2)不能用来求最大或最小解问题;
(3)只能求满足某些约束条件的可行解的问题。
利用贪心法解题,通常的解题思路为:
(1)建立数学模型来描述问题;
(2)把求解的问题分成若干个子问题;
(3)对每一子问题求解,得到子问题的局部最优解;
(4)把子问题的解局部最优解合成原来解问题的一个解
利用贪心法解题,通常的步骤为以下三步:
(1)从问题的某一初始解出发;
(2)循环求解,求出可行解的一个解元素;
(3)由所有解元素组合成问题的一个可行解。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgkcejf
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13