< 返回新闻公告列表

什么是贪婪算法及其优缺点

发布时间:2020-03-29 17:17:14    来源: 知鸟云

贪婪算法又称“贪心算法”( Greedy Algorithm)是一种特殊类型的算法,用于通过导出特定实例的最大值或最小值来解决优化问题。该算法选择与当前结果无关的当前场景可行的最佳结果。贪婪算法通常针对特定条件的方案实施。该算法用于解决优化问题,最大化问题和最小化问题。并且提供可行或优化的解决方案。可能最适合贪婪算法的一些问题场景,例如霍夫曼编码,使用Prim或Kruskal算法的最小生成树图以及在图的两个顶点之间找到最短路径。

什么是贪婪算法?

贪婪算法是一种算法策略,用于在很小的阶段做出最佳选择,同时最终输出全局最优解。该算法在不考虑任何后果的情况下,选择了当时可行的最佳解决方案。贪婪方法说,应该分阶段解决问题,在这种情况下,应考虑到每个输入都是可行的。由于这种方法只关注即时结果,而没有考虑更大的局面,因此被认为是贪婪的。

定义核心概念

到现在为止,我们知道什么是贪心算法,为什么要这样命名。下面的指针将使您更好地理解贪婪算法。到现在为止,非常清楚的是,贪婪算法仅在出现问题时才起作用。但是,仅当我们对该问题有条件或约束时,此方法才适用。

问题类型

最小化问题:只要满足所有条件,就可以轻松解决问题。但是,当此问题要求最低要求时,则称为最小化问题。最大化问题:要求最大结果的问题称为最大化问题。优化问题:当问题需要最小或最大结果时,该问题称为优化问题。

解决方案类型

可行的解决方案: 现在,当出现问题时,我们有许多可行的解决方案。但是,考虑到该问题的条件,我们选择满足给定条件的解决方案。可以帮助我们获得满足给定条件结果的解决方案称为“可行解决方案” 。最佳解决方案: 如果解决方案已经可行并达到问题的目的,则称为最佳解决方案。最好的结果。该目标可以是最小结果,也可以是最大结果。这里要注意的一点是,任何问题都只有一个最佳解决方案。

以下示例将使您轻松理解贪婪方法。假设有人想购买市场上最好的汽车。选择这款车的方法之一是分析市场上所有的车。现在,这很耗时,要让人们轻松从他们有兴趣投资的那些特定品牌中选择汽车即可。进一步分类后,人们将再次根据其功能选择所需的车型。因此,此处使用的方法很贪心,因为在考虑所有因素都对您有利的同时,此解决方案是您的最佳解决方案。

贪婪算法的核心组成部分

现在,当我们对这种机制有了更好的了解时,让我们探索贪婪算法的核心组成部分,该算法将其与其他进程区分开来:

候选集:从该集合中创建一个答案。选择功能:选择要包含在解决方案中的最佳候选者。可行性函数:此部分计算是否可以使用候选人为解决方案做出贡献。目标函数:它为完整或部分解决方案分配一个值。解决方案功能:用于指示是否满足适当的解决方案。

贪婪算法在哪里最有效?

贪婪算法可以应用于下面提到的问题。

可以使用Greedy方法使用Prim或Kruskal算法找到最小生成树图找到两个顶点之间的最短路径是另一个可以使用贪婪算法解决的问题。将Dijkstra算法和贪婪算法一起应用将为您提供最佳解决方案。霍夫曼编码

优点

与其他算法相比,贪婪算法的最大优点是在大多数情况下易于实现且非常高效。

缺点

贪婪算法基本上是逐个部分地建立解决方案,然后选择下一部分,以便立即产生当前问题的最佳解决方案。结果,无需考虑或担心当前决定的后果。从来没有重新考虑以前的选择,尽管贪婪算法给出了接近最优的解决方案,但它未能产生最优的解决方案。背包问题和旅行商问题是贪婪算法无法产生最佳解决方案的问题示例。

背包问题:背包问题最广为人知,是许多人每天都面临的问题。说,我们有一组项目,每个项目要填充到容器中的重量和价值(利润)都不同,或者应该以总重量小于或等于容器重量的方式收集,同时使总利润最大化。

总结

当需要实时解决方案且近似答案“足够好” 时,贪婪算法最适用。显然,贪心算法可在确保产生最佳解决方案的同时最大程度地减少时间,因此更适用于需要较少时间的情况。阅读这篇文章后,可能对贪婪算法有一个不错的主意。此外,本文还解释了为什么将其视为可解决几乎所有编程难题并帮助您在给定时间点确定最佳解决方案的最佳框架。

但是,从粗略的方面来说,要应用贪婪算法的理论,人们必须更加努力地了解正确的问题。尽管这是具有逻辑的科学概念,但也具有创造力的本质。


相关推荐