基本概念
贪心策略是指从问题的初始状态出发,通过若干次贪心选择得出最优值(或较优解)的一种解法
其实,从“贪心策略”一词可以看出,贪心策略总是做出在当前看来最优的选择。也就是说,贪心策略并不是从整体上
考虑问题,他所作的选择只是在某种意义上的局部最优解,而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或
较优解。
例如:在n行m列的矩阵中找一个最大的数可以用贪心。选n次,找出其最大值即可。
再如:设有n台处理机p1,p2,....pn,和m个作业j1,j2,j3,....jm,处理机可并行工作,作业未完成不能中断,作业ji在处理机上的时间是ti,求最佳解决方案,使得完成时间最短。
本题就不能用贪心策略。理由是:若n=3,m=6,则6个作业的时间分别是11,7,5,5,4,7,
用贪心策略(每次将作业加到空闲的机器上)时间为15,而搜索策略最优解为14,但是贪心策略提供了一个线索,那就是
每台处理时间不超过15,为搜索提供了方便。
总之,贪心算法不能保证求得的解是最佳的解,一般用来求某些最大最小解的问题,能确定某些问题的可行解的范围,特别是给
搜索算法提供了依据。
贪心算法的特点如下:
1)贪心选择的性质:所谓贪心选择的性质是指应用同一规划,将原问题变为一个相似的但规模更小的子问题,而后做出的
每一步选择都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出 的选择。从全局来看,运用贪心解决的问题在程序运行过程中无回溯过程。
2)局部最优解:局部最优解是贪心的数学描述。
例题可看我的贪心分类
推荐 田忌赛马:https://blog.csdn.net/qq_41603898/article/details/81190083