3.贪心算法

发布日期:2020-12-26 09:11:14 来源:网络转载

1.简介

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

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


2.思想

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

贪心算法的思想如下:

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

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

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

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

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


3.学习方法

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

 

4.相关例题

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

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


关键词 :
网站违法和不良信息举报邮箱:23139485@qq.com
CopyRight@2020-2030 www.haoapp8.cn All Rights Reserved.C语言学习网版权所有 粤ICP备15061369号
免责声明:本站内容来源于用户自行提供或网络收集,其真实性、准确性和合法性,www.haoapp8.cn不提供任何保证,亦不承担任何法律责任.而产生的法律关系及法律纠纷,由您自行协商解决。