DSA 贪心算法

贪心算法

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

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

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

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

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

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

但是，诸如 旅行推销员问题 或 0/1 背包问题 之类的问题，不具有这些性质，因此无法使用贪心算法来解决它们。这些问题将在下面进一步讨论。

此外，即使问题可以通过贪心算法解决，它也可以通过非贪心算法解决。

非贪心算法

以下是并非贪心算法的算法，这意味着它们不仅仅依赖于在每一步中做出局部最优选择

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

0/1 背包问题

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

这个问题无法通过贪心算法解决，因为在每一步中选择价值最高的物品、重量最低的物品或价值与重量之比最高的物品（局部最优解，贪心）并不能保证最优解（全局最优解）。

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

首先选择价值最高的物品，即价值 600 美元的马雕像，意味着如果不超过重量限制，你就无法带任何其他物品。

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

但是，在这种情况下，最好的解决方案是拿盾牌和花瓶，将背包中的总价值最大化为 800 美元，同时仍然在重量限制内。

总是拿重量最轻的宝藏怎么样？或者总是拿价值与重量之比最高的宝藏？

虽然遵循这些原则实际上会让我们在这个特定案例中找到最佳解决方案，但我们不能保证这些原则在更改此示例中的价值和权重时也能奏效。

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

阅读有关 0/1 背包问题的更多信息 这里。

旅行推销员问题

旅行推销员问题 是一个著名的问题，它也无法通过贪心算法解决，因为它不满足贪心选择性质和最优子结构性质，如前所述。

旅行推销员问题指出，你是一名推销员，你需要访问一些城市或城镇来销售你的商品。

在这里使用贪心算法，你将始终前往与你当前所在城市最近的下一个未访问城市。但这在大多数情况下不会让你找到总路径最短的最优解。

下面的模拟展示了贪心算法尝试解决旅行推销员问题时的样子。

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

虽然对旅行推销员问题运行贪婪方法有时会让我们获得最短路线的相当好的近似值，但贪心算法通常无法解决旅行推销员问题。

旅行推销员问题不满足能够通过贪心算法解决所需的性质。

了解更多关于旅行商问题的知识 这里。