算法设计思想之贪心


基本思想

贪心算法是一种稳扎稳打的算法,它从问题的某一个角度出发,在每一个阶段都根据相应的贪心策略做出当前最优决策,逐步逼近最终目标,尽可能快地求出最优解。贪心算法可以理解为局部最优,最后达到全局最优。贪心算法的核心思想就是“今朝有酒今朝醉”,只考虑当前面临的问题,不考虑接下来会发生什么。

特点

  • 1.贪心算法每个决策一旦做出,不可撤回,即贪心不允许回溯。
  • 2.贪心是根据贪心策略来逐步构造问题的,所选贪心策略不同,其具体算法实现也会不同,算法质量也不同。因此,算法的好坏在于贪心策略的选择。
  • 3.贪心算法就有高效性和不稳定性,因为它可以迅速地得到一个解,但不一定是最优解,但无论是不是最优解,它一定是最优解的一个近似值。

基本要素

1.最优子结构

当一个问题的最优解一定包含其子问题的最优解时,此问题具有最优解性质。即一个问题能分成若干个子问题,通过对子问题的最优解的推导(数学归纳),可以得到原问题的最优解。只有问题的子问题具有最优解时,才能保证贪心可以求得原问题的最优解。

2.贪心选择性质

贪心选择性质是指通过一系列的逐步局部最优选择,使得最终的选择是最优的,其次,每次做的选择依赖于前一次的选择,但不依赖于下一次的选择。贪心所做的是一个非线性的子问题处理(一个子问题不依赖于另一个子问题,但又有严格的处理顺序要求)。

贪心法的解题步骤

  • 1.将问题分为若干个互相独立的子问题。
  • 2.制定贪心策略并选择最合适的策略
  • 3.对于每个阶段,依据贪心策略进行贪心选择,并求出最优解。
  • 4.将各个子问题的解,合并为原问题的一个解。

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 算法设计思想之贪心


Just For Fun...