贪心算法有哪些

发布时间：2025-09-21 04:44:40 阅读量： 0 来源： 互联网转载

贪心算法有：1.有一个以优异方式来解决的问题。2.随着算法的进行，将积累起其它两个***；3.有一个函数来检查一个候选对象的***是否提供了问题的解答。该函数不考虑此时的解决方法是否优异；4.还有一个函数检查是否一个候选对象的***是可行的，也即是否可能往该***上添加更多的候选对象以获得一个解；5.选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解；6.目标函数给出解的值。

一、概念

贪婪算法(Greedy algorithm)是一种对某些求优异解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作优异选择，而不考虑各种可能的整体情况，它省去了为找优异解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个优异解，虽然每一步上都要保证能获得局部优异解，但由此产生的全局解有时不一定是优异的，所以贪婪法不要回溯。

贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分优异解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下优异解的分级处理方法称为贪婪算法。

二、基本思路

⒈建立数学模型来描述问题。

⒉把求解的问题分成若干个子问题。

⒊对每一子问题求解，得到子问题的局部优异解。

⒋把子问题的解局部优异解合成原来解问题的一个解。

实现该算法的过程:

从问题的某一初始解出发;

while 能朝给定总目标前进一步 do

求出可行解的一个解元素;

由所有解元素组合成问题的一个可行解。

三、备注

贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。