贪心算法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

(重定向自贪婪算法)

目录

什么是贪心算法

  贪心算法(又称贪婪算法)是一种能够得到某种度量意义下的最优解的分级处理方法,它总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解算法。

贪心算法的特性

  贪心算法可解决的问题通常大部分都有如下的特性:

  ⑴随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。

  ⑵有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

  ⑶还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。

  ⑷选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

  ⑸最后,目标函数给出解的值。

  ⑹为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。

贪心算法的基本思路

  贪心算法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步的进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法成为贪心法。

本条目对我有帮助9
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

Mis铭.

评论(共0条)

提示:评论内容为网友针对条目"贪心算法"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

打开APP

以上内容根据网友推荐自动排序生成

闽公网安备 35020302032707号