响应式网站建设品牌全网天下,建筑工程师培训学校,广州网站优化平台,中国建设银行校园招聘网站#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 一.介绍1.什么是贪心算法?2.步骤3.应用2.贪心模版 二.贪心的例子1.Dijkstra2.Prim3.Kruskal4.其它贪心的例子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 problemfind Minimum number of Coins 任务编排 求复杂问题的近似解
5.常见问题及解答
贪心算法一定会找到最优解吗 答不一定。贪心算法只保证在每一步选择中都是最优的但并不能保证整个问题的最优解。例如背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。如何判断一个问题是否适合用贪心算法解决 答一个问题如果可以用递归的方式分解成若干个子问题且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用贪心算法解决。贪心算法的时间复杂度是多少 答贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说对于规模较小的问题贪心算法的时间复杂度可以达到 O(nlogn)或 O(n^2);对于规模较大的问题可能需要 O(n^3)或更高。 觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
