贪心算法(Greedy Algorithm)

在算法设计和分析中,学习界的各位前辈总结出了许多算法思想,学习这些算法思想对于我们学习、分析、应用算法有些非常重要的作用。

1. 分治思想

分支思想指的是在解决大型复杂问题的时候,将问题进行分解,拆分成若干较小的问题,将小的问题解决,使得整个问题得到解决,它的步骤如下:

  1. 分解问题:将原问题分解为一系列的子问题;
  2. 解决问题:解决各个子问题;
  3. 合并结果:将子问题的结构合并得到原问题的解。

比如归并排序算法,将序列拆分成多个包含 1 个元素的有序序列,然后合并排序结果,使得整个序列有序。

2. 贪心算法

在解决多阶段决策问题时,立足于当前阶段做出最优选择,从而得到全局最优解。当然,贪心思想并不能保证在所有问题上都能得到全局最优解。

贪心与动态规划的相同点:都通过递推的方式,由局部最优解推导出全局最优解。不同点:贪心算法不保留每一步的最优结果,而且每一步的结果都不能改变,其每一步的最优解包含上一步的最优解。动态规划的每一步最优解不一定包含上一步的最优解。

未经允许不得转载:一亩三分地 » 贪心算法(Greedy Algorithm)