首页 > 其他 > 详细

贪心总结

时间:2019-07-14 16:00:30      阅读:113      评论:0      收藏:0      [点我收藏+]

一、基本概念

       所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性

 

二、基本思路

1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解,得到子问题的局部最优解。
4.把子问题的局部最优解合成原来解问题的一个解。
 
 

三、适用问题

  贪心策略适用的前提是:局部最优策略能导致产生全局最优解。

 

四、实现框架

从问题的某一初始解出发;
while (能朝给定总目标前进一步)
{
  利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;

五、【总结】:

1、该问题是否能用贪心解决:想要解决这个问题,而这个问题又有许多局部问题,则求出局部最优解,从而推送到全局最优解
2、贪心策略的选择是否正确:要进行适当的验证

 
技术分享图片
 
 
 
技术分享图片
 
技术分享图片
技术分享图片

贪心总结

原文:https://www.cnblogs.com/-citywall123/p/11184316.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!