💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
- 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
- 导航
- 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
- 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
- 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
- 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
- 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂
非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨
博客目录
- 一.介绍
- 1.什么是贪心算法?
- 2.步骤
- 3.应用
- 2.贪心模版
- 二.贪心的例子
- 1.Dijkstra
- 2.Prim
- 3.Kruskal
- 4.其它贪心的例子
- 5.常见问题及解答
一.介绍
1.什么是贪心算法?
贪心算法(Greedy Algorithm)是一种常见的问题求解策略,通常用于优化问题。贪心算法的核心思想是在每一步都做出当前看起来最优的选择,而不考虑全局最优解。贪心算法通常适用于那些具有贪心选择性质的问题,即局部最优解也是全局最优解的一部分。
称之为贪心算法或贪婪算法,核心思想是
- 将寻找最优解的问题分为若干个步骤
- 每一步骤都采用贪心原则,选取当前最优解
- 因为没有考虑所有可能,局部最优的堆叠不一定让最终解最优
2.步骤
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题,如最小生成树、背包问题等。
以下是贪心算法的一般特点和步骤:
-
选择策略:从问题的所有可行选择中,选择当前看起来最优的一个。这个选择通常基于一定的规则或者评估函数。
-
可行性检验:检查所做的选择是否合法,即是否满足问题的约束条件。
-
局部最优性:贪心算法只关注当前步骤的最优解,而不考虑整体问题的最优解。这是贪心算法与动态规划等其他算法的主要不同之处。
-
迭代:重复执行步骤 1 和步骤 2,直到达到问题的结束条件或者找到一个近似的解。
3.应用
贪心算法的应用范围广泛,可以用于解决许多优化问题,如:
最小生成树问题
:如 Kruskal 算法和 Prim 算法用于构建最小生成树。最短路径问题
:如 Dijkstra 算法和 Bellman-Ford 算法用于寻找最短路径。调度问题
:如任务调度、会议安排等。背包问题
:给定一组物品和一个背包,每个物品有一定的重量和价值,要求在不超过背包容量的情况下,尽可能多地装入物品。活动选择问题
:在一个活动集合中,每次只能参加一个活动,问如何安排时间以最大化所有活动的收益。编辑距离问题
:给定两个字符串,求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。网络流问题
:给定一张有向图和一些起点和终点,求最大流量。找零问题
:给定一定数量的硬币和需要找零的金额,求使用最少的硬币数。
贪心算法的优点在于它们通常比其他复杂算法更快,因为它们不需要考虑所有可能的解决方案。然而,贪心算法的局限性在于它们不能保证一定找到全局最优解,因此在某些情况下可能会得到次优解或者不可行解。因此,在使用贪心算法时,需要仔细分析问题的特性,以确定它是否适合使用贪心策略。有时候,贪心算法可以与其他算法结合使用,以获得更好的结果。
2.贪心模版
下面是一个使用 Java 编写的通用贪心算法模板,你可以根据具体问题进行适当的修改和扩展:
import java.util.Arrays;public class GreedyAlgorithm {public static void main(String[] args) {// 在这里输入问题的输入数据// 例如,如果是一个数组或者列表,可以这样初始化:int[] inputArray = {5, 2, 1, 9, 3};// 调用贪心算法函数int result = greedyAlgorithm(inputArray);// 输出结果System.out.println("最终结果: " + result);}public static int greedyAlgorithm(int[] input) {// 在这里实现贪心算法的逻辑// 请根据问题的具体要求编写贪心策略// 以下是一个简单的示例:找到数组中的最小元素int minElement = input[0];for (int i = 1; i < input.length; i++) {if (input[i] < minElement) {minElement = input[i];}}return minElement;}
}
这个模板中,你可以将问题特定的输入数据放在main
函数中,然后调用greedyAlgorithm
函数来执行贪心算法。在greedyAlgorithm
函数中,你需要根据问题的特性编写相应的贪心策略。
请注意,这只是一个基本的模板,实际上,贪心算法的实现会根据具体问题的不同而有所不同。你需要根据问题的需求来设计合适的贪心策略,并根据具体情况修改模板。
二.贪心的例子
1.Dijkstra
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}
- 没找到最短路径的例子:负边存在时,可能得不到正确解
- 问题出在贪心的原则会认为本次已经找到了该顶点的最短路径,下次不会再处理它(curr.visited = true)
- 与之对比,Bellman-Ford 并没有考虑局部距离最小的顶点,而是每次都处理所有边,所以不会出错,当然效率不如 Dijkstra
2.Prim
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}
3.Kruskal
// ...
while (list.size() < size - 1) {// 选取当前【距离最短】的边Edge poll = queue.poll();// 判断两个集合是否相交int i = set.find(poll.start);int j = set.find(poll.end);if (i != j) { // 未相交list.add(poll);set.union(i, j); // 相交}
}
4.其它贪心的例子
-
选择排序、堆排序
-
拓扑排序
-
并查集合中的 union by size 和 union by height
-
哈夫曼编码
-
钱币找零,英文搜索关键字
- change-making problem
- find Minimum number of Coins
-
任务编排
-
求复杂问题的近似解
5.常见问题及解答
- 贪心算法一定会找到最优解吗?
答:不一定。贪心算法只保证在每一步选择中都是最优的,但并不能保证整个问题的最优解。例如,背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。 - 如何判断一个问题是否适合用贪心算法解决?
答:一个问题如果可以用递归的方式分解成若干个子问题,且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用贪心算法解决。 - 贪心算法的时间复杂度是多少?
答:贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说,对于规模较小的问题,贪心算法的时间复杂度可以达到 O(nlogn)或 O(n^2);对于规模较大的问题,可能需要 O(n^3)或更高。
觉得有用的话点个赞
👍🏻
呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍
🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙