贪心算法的思想

2017年5月13日 4点热度 0条评论 来源: 凉哈哈

贪心算法的思想

贪心算法的基本思想是找出整体当中每个小的局部的最优解,并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质:

1.整体的最优解可以通过局部的最优解来求出;

2.一个整体能够被分为多个局部,并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。

 在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。

特别注意: 若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!

以经典的活动安排为例:

1、若AE的最优解,那么E-A 也是问题的最优解,在余下的问题里,继续拿最早结束的;

2、拿可以开始的最早结束。(所以要按结束时间排序一次,然后把可以开始的选择上,然后继续向后推)

贪心子结构是独立的(往往用标志判断而已),不同于动态规划(后面每一边的计算要用到前一步的值,另外开辟空间来保存)

 贪心算法的基本步骤

1、从问题的某个初始解出发。

2、采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。

3、将所有部分解综合起来,得到问题的最终解。

    原文作者:凉哈哈
    原文地址: https://blog.csdn.net/lz161530245/article/details/71908343
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。