贪婪算法介绍

2022-04-20 贪婪算法

本文概述

例
实现贪婪算法的步骤是

“贪婪方法可从许多选项中找到, 但你必须选择最佳选项。”
【贪婪算法介绍】在这种方法中, 我们必须从许多现有方法中找出最佳方法/选项。
在这种方法/方法中, 我们专注于第一阶段并确定输出, 而不考虑未来。
此方法可能会或可能不会提供最佳输出。
贪婪算法通过做出在特定时刻看起来最好的最佳选择来解决问题。可以使用贪婪算法确定许多优化问题。某些问题没有有效的解决方案, 但是贪婪算法可能会提供接近最佳的解决方案。如果问题具有以下两个属性, 则贪心算法将起作用：

贪婪选择属性：通过创建局部最优解可以达到全局最优解。换句话说, 可以通过创建“贪婪”选择来获得最佳解决方案。
最优子结构：最优解包含最优子解。换句话说, 最优解子问题的答案是最优的。

例

机器调度
小背包问题
最小生成树
霍夫曼密码
作业排序
活动选择问题

实现贪婪算法的步骤是

可行：这里我们检查它是否满足所有可能的约束条件, 以获得至少一种解决我们问题的方法。
局部最优选择：在这种情况下, 选择应该是从当前可用的最优选择
不可更改：一旦做出决定, 在任何后续步骤中, 该选项都不会更改。

推荐阅读

上一篇：0/1背包问题（动态规划方法）

下一篇：活动选择问题和贪婪算法