DSA 贪心算法

贪心算法

贪心算法在每一步都只根据当前情况做出决策，而不考虑整个问题的整体情况。

换句话说，贪心算法在每一步都做出局部最优选择，希望最终能找到全局最优解。

例如，在 Dijkstra 算法 中，下一步要访问的顶点始终是当前到源点距离最短的未访问顶点，这是从当前已访问顶点组中看到的。

所以 Dijkstra 算法是贪心的，因为它选择下一个要访问的顶点仅仅基于当前可用的信息，而不考虑整体问题，或者这个选择如何影响未来的决策或最终的最短路径。

选择贪心算法是一种设计选择，就像 动态规划 是另一种算法设计选择一样。

本教程中的大多数问题，例如排序数组，或 在图中找到最短路径，都具有这些属性，因此这些问题可以通过贪心算法解决，例如 选择排序 或 Dijkstra 算法。

但是像 旅行商问题 或 0/1 背包问题 这样的问题不具备这些属性，因此不能使用贪心算法来解决。这些问题将在后面进一步讨论。

此外，即使一个问题可以用贪心算法解决，也可以用非贪心算法解决。

非贪心算法

以下是非贪心算法，意味着它们不只依赖于每一步都做出局部最优选择

• 归并排序：不断地将数组分成两半，然后将数组部分重新合并，从而得到一个已排序的数组。这些操作不是贪心算法那样的一系列局部最优选择。
• 快速排序：选择主元，围绕主元排列元素，以及递归调用对主元左右两侧执行相同操作——这些操作不依赖于做出贪心选择。
• BFS 和 DFS 遍历：这些算法在不通过每一步的局部选择来决定如何继续遍历的情况下遍历图，因此它们不是贪心算法。
• 使用记忆化查找第 n 个斐波那契数：此算法属于一种称为 动态规划 的问题解决方法，它解决重叠子问题，然后将它们重新组合起来。记忆化在每一步中用于优化整体算法，这意味着在此算法的每一步中，它不仅考虑局部最优解是什么，而且还考虑到在此步骤中计算出的结果可能会在后续步骤中使用。

0/1 背包问题

如前所述，0/1 背包问题 不能用贪心算法解决，因为它不满足贪心选择性质和最优子结构性质。

这个问题不能用贪心算法解决，因为每一步选择价值最高、重量最轻或价值重量比最高的物品（局部最优解，贪心）并不能保证得到最优解（全局最优）。

假设您的背包限重 10 公斤，而您面前有这三件宝物

通过先取价值最高的物品——价值 600 美元的马雕，做出贪心选择，意味着您不能再携带其他任何物品而不超过重量限制。

因此，通过贪婪的方式解决此问题，您最终得到一个价值 600 美元的金属马。

但在此情况下最佳解决方案是携带盾牌和陶罐，将背包的总价值最大化为 800 美元，同时仍低于重量限制。

总是选择重量最轻的宝物呢？或者总是选择价值重量比最高的宝物呢？

虽然遵循这些原则实际上可以让我们在特定情况下找到最佳解决方案，但我们不能保证这些原则在示例中的值和重量改变时也能奏效。

这意味着 0/1 背包问题无法用贪心算法解决。

在此处 阅读更多关于 0/1 背包问题的信息。

旅行商问题

旅行商问题 是一个著名的问题，也不能用贪心算法解决，因为它不满足前面提到的贪心选择性质和最优子结构性质。

旅行商问题陈述您是一名推销员，需要拜访若干个城市或城镇进行销售。

使用贪心算法，您将总是前往离当前所在城市最近的下一个未访问城市。但这种情况在大多数情况下并不能为您带来最短总路径的最优解。

下面的模拟显示了当贪心算法尝试解决旅行商问题时的样子。

运行模拟时，算法的缺陷可能并非总是显而易见，但您可能会注意到有时线条会交叉，形成更长的总距离，而这显然是不必要的。

虽然运行旅行商问题的贪心方法有时可以提供最短路线的相当不错的近似值，但贪心算法通常无法解决旅行商问题。

旅行商问题不满足贪心算法可解所需的性质。

在此处 阅读更多关于旅行商问题的信息。