首页  /  数据结构教程  /  贪心算法  /  

贪心算法

点击打开在线编译器,边学边练

1.简介

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。


2.思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件,直到把所有数据枚举完。

贪心算法的思想如下:

a)建立数学模型来描述问题;

b)把求解的问题分成若干个子问题;

c)对每一子问题求解,得到子问题的局部最优解;

d)把子问题的解局部最优解合成原来解问题的一个解。

与动态规划不同的是,贪心算法得到的是一个局部最优解(即有可能不是最理想的),而动态规划算法得到的是一个全局最优解(即必须是整体而言最理想的),一个有趣的事情是,动态规划中的01背包问题就是一个典型的贪心算法问题。


3.学习方法

由浅入深,不妨先将动态规划中的01背包问题弄熟悉,再来学习贪心算法的基础思维,其实在很多时候自己并未发觉自己已经是在使用贪心了,当你基本掌握了一些贪心的概念的时候,可以做一些诸如装箱问题,切割问题,区域分配问题的题目,巩固自己的知识。

 

4.相关例题

有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法,最小生成树算法和最短路径算法,甚至是一些暴力求解题目,都是使用了贪心的这种思维。

可以直接从dotcpp网站标签中搜索贪心即可,贪心算法在很多题目中均或多或少有一些思维的应用,因此题目涵盖非常广阔,非常适合逐步练习。


上一课:动态规划思想 下一课:博弈入门
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记