贪心算法专题总结

贪心算法:

在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。
贪心算法不是从整体考虑问题,而是求局部最优解
求解过程:

(1)候选集合A:为了构造问题的解决方案,有一个候选集合A作为问题的可能解,即问题的最终解均取自于候选集合A。

(2)解集合S:随着贪心选择的进行,解集合S不断扩展,直到构成满足问题的完整解。

(3)解决函数solution:检查解集合S是否构成问题的完整解。

(4)选择函数select:即贪心策略,这是贪心法的关键,它指出哪个候选对象最有希望构成问题的解,选择函数通常和目标函数有关。

(5)可行函数feasible:检查解集合中加入一个候选对象是否可行,即解集合扩展后是否满足约束条件。
适用条件:
问题的求解由一系列步骤组成,每一个步骤都是局部的最优解,可以先求出局部最优解再求总的解
典型的贪心算法:
装载问题,背包问题,延迟调度问题。。。
原文地址:https://www.cnblogs.com/Sikaozhe/p/5329357.html