贪婪算法

贪心方法是用于解决问题的一种策略，类似于分治法。这种方法用于解决优化问题。优化问题是需要最大化或最小化结果的问题。让我们通过一些术语来理解它。

贪心方法是最简单和直接的方法。它不是一种算法，而是一种技术。这种方法的主要功能是基于当前可用的信息做出决策。无论当前的信息是什么，决策都会做出，而无需担心当前决策在未来的影响。

这种技术主要用于确定可行解，可行解可能或可能不是最优解。可行解是满足给定条件的一个子集。最优解是子集中最好且最有利的解。在可行解的情况下，如果多个解满足给定的条件，那么这些解将被认为是可行的，而最优解是所有解中最好的解。

贪心方法的特点

以下是贪心方法的特点

• 为了以最佳方式构造解决方案，该算法创建了两个集合，其中一个集合包含所有选定的项目，另一个集合包含被拒绝的项目。
• 贪心算法在希望解决方案是可行或最优的情况下做出良好的局部选择。

贪心算法的组成部分

可以在贪心算法中使用的组成部分是

• 候选集：从集合中创建的解决方案称为候选集。
• 选择函数：此函数用于选择可以添加到解决方案中的候选者或子集。
• 可行性函数：此函数用于确定候选者或子集是否可以用于对解决方案做出贡献。
• 目标函数：一个函数，用于为解决方案或部分解决方案分配值。
• 解决方案函数：此函数用于告知是否已达到完整函数。

贪心算法的应用

• 它用于寻找最短路径。
• 它用于使用 Prim 算法或 Kruskal 算法找到最小生成树。
• 它用于具有截止日期的作业排序。
• 此算法还用于解决分数背包问题。

贪心算法的伪代码

以上是贪心算法。最初，解决方案被赋值为零值。我们传递数组和贪心算法中的元素数量。在for循环内部，我们逐个选择元素，并检查解决方案是否可行。如果解决方案是可行的，那么我们执行并集。

让我们通过一个例子来理解。

假设有一个问题'P'。我想从 A 到 B 旅行，如下所示

P：A → B

问题是我们必须从 A 到 B 穿越这段旅程。从 A 到 B 有各种各样的解决方案。我们可以通过步行、汽车、自行车、火车、飞机等方式从 A 到 B。旅程中有一个约束条件，我们必须在 12 小时内完成这段旅程。如果我乘火车或飞机，那么我只能在 12 小时内覆盖这段距离。此问题有很多解决方案，但只有两个解决方案满足约束条件。

如果我们说我们必须以最低的成本完成旅程。这意味着我们必须尽可能以最低的成本穿越这段距离，所以这个问题被称为最小化问题。到目前为止，我们有两个可行的解决方案，即一个乘火车，另一个乘飞机。由于乘火车旅行将导致最低成本，因此它是一个最优解。最优解也是可行解，但提供最好的结果，因此该解是最优解，成本最低。将只有一个最优解。

需要最小或最大结果的问题称为优化问题。贪心方法是用于解决优化问题的策略之一。

使用贪心算法的缺点

贪心算法根据每个阶段可用的信息做出决策，而不考虑更广泛的问题。因此，贪心解可能无法为每个问题提供最佳解。

它遵循每个阶段的局部最优选择，目的是找到全局最优解。让我们通过一个例子来理解它。

考虑下面给出的图

我们必须以最低的成本从源头到目的地旅行。由于我们有三个可行的解决方案，其成本路径分别为 10、20 和 5。5 是最低的成本路径，因此它是一个最优解。这是局部最优，通过这种方式，我们可以在每个阶段找到局部最优解，以计算全局最优解。